Introduction To Data Structures Using C

Presentation on theme: "Introduction To Data Structures Using C"— Presentation transcript:

1 Introduction To Data Structures Using C
스택(stack)

2 1. 스택 스택(stack) 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조
스택에 저장된 원소는 top으로 정한 곳에서만 접근 가능 top의 위치에서만 원소를 삽입하므로, 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이는 구조 마지막에 삽입(Last-In)한 원소는 맨 위에 쌓여 있다가 가장 먼저 삭제(First- Out)됨 ☞ 후입선출 구조 (LIFO, Last-In-First-Out)

3 1. 스택 후입선출 구조의 예1 : 연탄 아궁이 연탄을 하나씩 쌓으면서 아궁이에 넣으므로 마지막에 넣은 3번 연탄이 가장 위에 쌓여 있다. 연탄을 아궁이에서 꺼낼 때에는 위에서부터 하나씩 꺼내야 하므로 마지막 에 넣은 3번 연탄을 가장 먼저 꺼내게 된다.

4 1. 스택 스택의 연산 스택에서의 삽입 연산 : push 스택에서의 삭제 연산 : pop

5 1. 스택 스택에서의 원소 삽입/삭제 과정 [그림 6-6]공백 스택에 원소 A, B, C를 순서대로 삽입하고 한번 삭제하는 연산과정 동안의 스택 변화

6 2. 추상 자료형 스택 ADT Stack 데이터 : 0개 이상의 원소를 가진 유한 순서 리스트 연산 :
    데이터 :  0개 이상의 원소를 가진 유한 순서 리스트     연산 :           S ∈ Stack; item ∈ Element;           createStack(S) ::= create an empty stack S;                 // 공백 스택 S를 생성하는 연산           push(S, item) ::= insert item onto the top of Stack S;                 // 스택 S의 top에 item(원소)을 삽입하는 연산           isEmpty(S) ::= if (S is empty) then  return  true                              else  return  false;                 // 스택 S가 공백인지 아닌지를 확인하는 연산           pop(S) ::= if (isEmpty(S)) then return error                         else { delete and return the top item of Stack S};                 // 스택 S의 top에 있는 item(원소)을 스택 S에서 삭제하고 반환하는 연산           delete(S) ::= if (isEmpty(S)) then return error                          else delete the top item of Stack S;                 // 스택 S의 top에 있는 item(원소)을 삭제하는 연산           peek(S) ::= if (isEmpty(S)) then return error                          else  return  (the top item of  the Stack S);                 // 스택 S의 top에 있는 item(원소)을 반환하는 연산 End  Stack

7 2. 추상 자료형 스택 스택의 push 알고리즘 top ← top+1; S(top) ← x;
스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면 먼저 top의 위치를 하나 증가 만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 오버플로우(overflow)상태가 되므로 삽입 연산을 수행하지 못하고 연산 종료 S(top) ← x; 오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입

8 2. 추상 자료형 스택 스택의 pop 알고리즘 return S(top); top ← top-1;

9 3. 스택의 구현: 순차 자료구조를 이용한 스택 구현
순차 자료구조를 이용한 스택의 구현 순차 자료구조인 1차원 배열을 이용하여 구현 스택의 크기 : 배열의 크기 스택에 저장된 원소의 순서 : 배열 원소의 인덱스 인덱스 0번 : 스택의 첫번째 원소 인덱스 n-1번 : 스택의 n번째 원소 변수 top : 스택에 저장된 마지막 원소에 대한 인덱스 저장 공백 상태 : top = -1 (초기값) 포화 상태 : top = n-1

10 3. 스택의 구현: 순차 자료구조를 이용한 스택 구현
크기가 5인 1차원 배열의 스택에서 [그림 6-6]의 수행과정

11 3. 스택의 구현: [예제 6-1] 순차 자료구조를 이용한 스택 프로그램 01 #include <stdio.h>
02 #include <stdlib.h> 03 #define STACK_SIZE 100 04 05 typedef int element; // int를 스택 element의 자료형으로 정의 06 element stack[STACK_SIZE]; 07 int top= -1; // 스택의 top의 초기값을-1로 설정 08 09 void push(element item) // 스택의 삽입 연산 10 { 11 if(top >= STACK_SIZE-1) { // 스택이 이미 Full인 경우 printf("\n\n Stack is FULL ! \n"); return; 14 } else stack[++top]=item; 16 } 17 18 element pop() // 스택의 삭제 후 반환 연산 19 { 20 if(top==-1) { // 현재 스택이 공백인 경우 printf("\n\n Stack is Empty!!\n"); return 0; 23 } 24 else return stack[top--]; 25 }

12 3. 스택의 구현: [예제 6-1] 27 void del() // 스택의 삭제 연산 28 {
28 { 29 if(top==-1) { // 현재 스택이 공백인 경우 printf("\n\n Stack is Empty !\n"); exit(1); 32 } 33 else top--; 34 } 35 36 element peek() // 스택의 top 원소 검색 연산 37 { 38 if(top==-1){ // 현재 스택이 공백인 경우 printf("\n\n Stack is Empty !\n"); exit(1); 41 } 42 else return stack[top]; 43 } 44 45 void printStack() // 스택 내용 출력 연산 46 { 47 int i; 48 printf("\n STACK [ "); 49 for(i=0; i<=top; i++) printf("%d ",stack[i]); 51 printf("] "); 52 } 53

13 3. 스택의 구현: [예제 6-1] 54 void main(void) 55 { 56 int item;
55 { 56 int item; 57 printStack(); 58 push(1); 59 printStack(); 60 push(2); 61 printStack(); 62 push(3); 63 printStack(); 64 65 item = peek(); 66 printStack(); 67 printf("peek top => %d", item); 68 69 del(); 70 printStack(); 71

14 3. 스택의 구현: [예제 6-1] 72 item = pop(); 73 printStack();
74 printf("\t pop top => %d", item); 75 76 item = pop(); 77 printStack(); 78 printf("\t pop top => %d", item); 79 80 pop(); 81 82 getchar(); 83 }

15 3. 스택의 구현: [예제 6-1] 실행 결과 >

16 3. 스택의 구현 순차 자료구조로 구현한 스택의 장점 순차 자료구조로 구현한 스택의 단점
순차 자료구조인 1차원 배열을 사용하여 쉽게 구현 순차 자료구조로 구현한 스택의 단점 물리적으로 크기가 고정된 배열을 사용하므로 스택의 크기 변경 어려움 순차 자료구조의 단점을 그대로 가지고 있다.

17 3. 스택의 구현 : 연결 자료구조를 이용한 스택 구현
연결 자료구조를 이용한 스택의 구현 단순 연결 리스트를 이용하여 구현 스택의 원소 : 단순 연결 리스트의 노드 스택 원소의 순서 : 노드의 링크 포인터로 연결 push : 리스트의 마지막에 노드 삽입 pop : 리스트의 마지막 노드 삭제 변수 top : 단순 연결 리스트의 마지막 노드를 가리키는 포인터 변수 초기 상태 : top = null

18 3. 스택의 구현 : 연결 자료구조를 이용한 스택 구현
단순 연결 리스트의 스택에서 [그림6-6]의 연산 수행과정 ① 공백 스택 생성 : createStack(S); ② 원소 A 삽입 : push(S, A); ③ 원소 B 삽입 : push(S, B);

19 3. 스택의 구현 : 연결 자료구조를 이용한 스택 구현
④ 원소 C 삽입 : push(S, C); ⑤ 원소 삭제 : pop(S);

20 3. 스택의 구현 : [예제 6-2] 단순 연결 리스트를 이용한 스택 프로그램
001 #include <stdio.h> 002 #include <stdlib.h> 003 #include <string.h> 004 005 typedef int element; // int를 스택 element의 자료형으로 정의 006 007 typedef struct stackNode { // 스택의 노드 구조 정의 008 element data; 009 struct stackNode *link; 010 }stackNode; 011 012 stackNode* top; // 스택의top 노드를 지정하기 위한 포인터 top 선언 013 014 void push(element item) // 스택 삽입 연산 015 { 016 stackNode* temp=(stackNode *)malloc(sizeof(stackNode)); 017 temp->data = item; 018 temp->link = top; 019 top = temp; 020 } 021

21 3. 스택의 구현 : [예제 6-2] 022 element pop() // 스택의 삭제 후 반환 연산 023 {
023 { 024 element item; 025 stackNode* temp=top; 026 027 if(top == NULL) { // 현재 스택이 공백 리스트인 경우 printf("\n\n Stack is empty !\n"); return 0; 030 } 031 else{ // 현재 스택이 공백 리스트가 아닌 경우 item = temp->data; top = temp->link; free(temp); return item; 036 } 037 } 038

22 3. 스택의 구현 : [예제 6-2] 052 void del() // 스택의 삭제 연산 053 {
053 { 054 stackNode* temp; 055 if(top == NULL) { // 현재 스택이 공백 리스트인 경우 printf("\n\n Stack is empty !\n"); 057 } 058 else { // 현재 스택이 공백 리스트가 아닌 경우 temp = top; top = top->link; free(temp); 062 } 063 } 064 065 void printStack() // 스택의 내용 출력 연산 066 { 067 stackNode* p=top; 068 printf("\n STACK [ "); 069 while(p){ printf("%d ",p->data); p = p->link; 072 } 073 printf("] "); 074 } 075

23 3. 스택의 구현 : [예제 6-2] 076 void main(void) 077 { 078 element item;
077 { 078 element item; 079 top = NULL; 080 printStack(); 081 push(1); 082 printStack(); 083 push(2); 084 printStack(); 085 push(3); 086 printStack(); 087 088 item = peek(); 089 printStack(); 090 printf("peek top => %d", item); 091 092 del(); 093 printStack(); 094

24 3. 스택의 구현 : [예제 6-2] 095 item = pop(); 096 printStack();
printf("\t pop top => %d", item); 098 099 item = pop(); 100 printStack(); 101 printf("\t pop top => %d", item); 102 103 pop(); 104 105 getchar(); 106 }

25 3. 스택의 구현 : [예제 6-2] 실행 결과 >

26 element peek() //스택의 top 원소 검색 연산
{ element item; if(top == NULL) { //현재 스택이 공백 리스트인 경우 printf("\n\n Stack is empty !\n"); return 0; } else { //현재 스택이 공백 리스트가 아닌 경우 item = top->data; return item;

27