stack 개념
밑이 막힌 긴 통에 비유
: 먼저 들어간(Push) 것이 아래에 있게 되고 나중에 들어간 것이 위에 있게 된다. 따라서 제일 나중에 들어간 것이 제일 먼저 나온다(POP).
이 때문에 stack을 LIFO(Last In Firsto Out) 구조라고 한다.
위의 그림과 같이 stack에 값을 집어넣는 것을 Push, 값을 빼내는 것을 Pop이라고 한다.
자료구조에서의 Stack
배열로 구현
stack이 완전히 빈 경우는 top Index가 -1의 값을 가진다.
1 2 3 4 5 6 7 8 9 10 | #define MAX 3 int stack[MAX]; int stackTop; void init_stack(void) { printf("\n -> Initialize stack.\n"); stackTop = -1; } | cs |
stack의 바닥은 배열의 index 0이 된다. 마지막에 저장된 데이터 위치가 top이 된다.
push 연산은 아래와 같이 정리된다.
- push : Top을 위로 한칸 올리고, Top이 가리키는 위치에 데이터 저장
1 2 3 4 5 6 7 8 9 10 | int push(int top) { if (stackTop >= MAX - 1) // 스택이 꽉 찬 상태는 MAX -1 (배열의 마지막 index) { printf("\n -> Stack overflow."); return -1; } stack[++stackTop] = top; // stackTop 한칸 올린 위치에 값(top)을 저장 return top; } | cs |
pop 연산은 아래와 같이 정리된다.
- pop : Top이 가리키는 데이터 반환 후, Top 위치를 한칸 내림
pop 연산시에는 stack이 텅 비어있는 경우를 가정해야 한다. 텅 빈 stack을 pop하면 Stack Underflow가 일어나게 된다.
1 2 3 4 5 6 7 8 9 | int pop(void) { if (stackTop < 0) // stack이 비어있다면 { printf("\n -> Stack underflow."); return -1; } return stack[stackTop--]; // top 한칸 내림 } | cs |
마지막으로 stack에 저장된 값을 출력하는 함수를 정의한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | void print_stack(void) { int i; if (stackTop < 0) // stack이 비어있다면 { printf("\n -> Stack is Empty.\n"); return -1; } printf("\n===== Stack에 저장된 값 ===== \n"); for (i = stackTop; i >= 0; i--) { printf("%d ", stack[i]); } printf("\n\n"); } | cs |
위 함수를 토대로 main함수를 정의하고 출력결과를 살펴 본다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <stdio.h> void main(void) { int i; init_stack(); printf("push 1, 2, 3"); push(1); push(2); push(3); print_stack(); i = pop(); printf("pop 3"); print_stack(); printf("push 4, 5"); push(4); push(5); // stack overflow print_stack(); init_stack(); print_stack(); printf("pop"); pop(); return 0; } | cs |
Output :
-> Initialize stack.
push 1, 2, 3
===== Stack에 저장된 값 =====
3 2 1
pop 3
===== Stack에 저장된 값 =====
2 1
push 4, 5
-> Stack Overflow.
===== Stack에 저장된 값 =====
4 2 1
-> Initialize stack.
-> Stack is Empty.
pop
-> Stack underflow.
stack 구조에 맞게 push와 pop이 진행되고 overflow와 underflow가 일어나는 모습도 볼 수 있다.
연결리스트를 이용한 stack
연결리스트 초기화
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | typedef struct node { int Ldata; struct node *next; }Node; Node *head, *tail; void init_stack(void) { head = (Node*)malloc(sizeof(Node)); tail = (Node*)malloc(sizeof(Node)); head->next = tail; tail->next = tail; } | cs |
push 함수
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int push(int data) { Node *nN; if ((nN = (Node*)malloc(sizeof(Node))) == NULL) { printf("\n -> Out of memory."); // 동적할당 실패(NULL)할시 출력 return -1; } nN->Ldata = data; nN->next = head->next; // 새 노드를 머리와 연결 head->next = nN; return data; } | cs |
head->next가 stack의 상단이 된다.
pop 함수
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int pop(void) { Node *delN; int ret; if (head->next == tail) // stack이 비어있다면 { printf("\n -> Stack underflow.\n"); return -1; } delN = head->next; ret = delN->Ldata; head->next = delN->next; free(delN); return ret; } | cs |
pop의 과정은 다음과 같다. delN가 가리키는 노드의 data를 ret에 저장해두었다 노드의 해제와 함께 return한다.
stack이 비어있을 때는 underflow 에러를 띄우고 -1을 return하도록 한다.
clear_stack 함수
배열을 이용한 stack은 top을 -1로 초기화해줬지만 연결리스트는 모든 노드를 메모리에서 해제할 필요가 있다.
dN과 d가 처음 head->next를 가리키게 된다.
dN이 다음 노드로 이동하고 d가 가리키는 노드가 해제된다. 이 과정을 dN이 tail을 가리킬 때까지 반복하게 된다.
그리고 head->next가 tail을 가리키면서 초기화 형태로 돌아가게 된다.
1 2 3 4 5 6 7 8 9 10 11 12 | void clear_stack(void) { Node *dN, *d; dN = head->next; while (dN != tail) { d = dN; dN = dN->next; free(d); } head->next = tail; } | cs |
마지막으로 stack의 데이터들을 보여주기 위한 함수이다.
1 2 3 4 5 6 7 8 9 10 11 12 | void print_stack(void) { Node *prt; prt = head->next; printf("\n 스택의 데이터 : \n"); while(prt != tail) { printf("%d ", prt->Ldata); prt = prt->next; } printf("\n"); } | cs |
위 함수를 토대로 main함수를 정의하고 출력결과를 살펴 본다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | #include <stdio.h> #include <stdlib.h> int main(void) { int i; init_stack(); printf("\n push 1, 2, 3, 4, 5"); push(1); push(2); push(3); push(4); push(5); print_stack(); i = pop(); printf("pop"); print_stack(); printf("push 6, 7, 8"); push(6); push(7); push(8); print_stack(); printf("\n 스택 비움"); clear_stack(); // stack 모두 비움 print_stack(); printf("pop"); pop(); return 0; } | cs |
Output :
push 1, 2, 3, 4, 5
스택의 데이터 :
5 4 3 2 1
pop
스택의 데이터 :
4 3 2 1
push 6, 7, 8
스택의 데이터 :
8 7 6 4 3 2 1
스택 비움
-> Stack is Empty.
pop
-> Stack underflow.
stack의 개념에는 peek이라고 해서 맨 위의 개체를 반환하되 제거는 하지 않는 것도 있지만 따로 함수로 구현하진 않았다.
그리고 배열의 경우에도 동적할당을 사용해볼 수 있으나 연결리스트에 비해 큰 이점이 없으므로 필요에 따라 선택하는게 좋을 듯 하다.
'Data Structure' 카테고리의 다른 글
| stack으로 구현하는 계산기 프로그램 (0) | 2016.11.07 |
|---|---|
| 연결리스트와 파일 입출력 (0) | 2016.11.02 |
| 이진 트리의 구현과 순회(Traversal) (0) | 2016.09.12 |
| Binary Tree (0) | 2016.09.12 |
| Doubly Linked List (0) | 2016.09.09 |
