규모 있는 프로그램을 만들다보면 데이터의 조직화가 필수가 되기도 합니다. 데이터의 조직화는 다루려고 하는 데이터의 특성과, 해결하려는 작업의 현상적이고 형식적인 면을 생각해서 그 특징에 맞는 자료구조를 선택해야 합니다. 스택은 LIFO(Last In First Out) 또는 후입선출적인 자료구조로, 여러 원소들을 차곡차곡 쌓아두는 구조로 도식화가 되는데, 차곡차곡 쌓여진 층(stack)에서 제일 위에 있는 또는 제일 나중에 쌓아진 원소가 제일 먼저 꺼내집니다. 이 특징에 해당하는 작업의 하나로 하노이의 탑과 같은 것이 있는데, 이는 글 중반에 다루기로 하겠습니다. 아래 도식은 LIFO가 되는 과정을 예시한 것으로 Add와 Delete 두 개의 오퍼레이션으로 구성되어 있습니다.
우선 비어있는 스택에 20을 집어넣으면 20이 제일 위가 되고 거기에 33을 집어넣으면 33이 제일 위가 됩니다. 47을 넣으면 47이 제일 위가 되므로 하나를 지우면 LIFO라, 47이 먼저 지워집니다. 이런 작업을 반복하는 것이 스택을 운용할때 하는 대표적인 오퍼레이션입니다.
스택의 용어로 바꿔보면 원소를 집어넣는 것(Add)는 push라고 하고, 원소를 빼내는 것(Delete)는 pop이라 합니다. 스택이 비어있으면 스택 언더플로우(stack underflow), 꽉 차 있으면 스택 오버플로우(stack overflow)라고 합니다. top은 제일 위에 있는 원소의 위치를 가리킵니다.
스택은 크게 두가지로 구현할 수 있습니다.
(1) 배열로 구현 (정적 메모리 할당)
(2) 포인터로 구현 (동적 메모리 할당)
(1)로 하면 사용할 메모리 크기를 미리 알아야 하고 원소가 배열변수 크기보다 그 수가 작거나 많으면 낭비나 부족이 되게 됩니다. 보통 예제에서는 알고리즘 이해가 우선이므로 배열로 보이는 것이 이해가 간편합니다.
push 알고리즘은 의사코드로 아래처럼 흐름을 갖습니다.
(1) STACK[스택크기]
(2) TOP = 스택크기 – 1이면 언더플로우 표시후 종료
(3) TOP = TOP + 1
(4) STACK[TOP] = 집어넣을 데이터
(5) 종료
pop 알고리즘은 아래와 같습니다.
(1) STACK[스택크기]
(2) TOP = 0 이면 오버플로우 표시후 종료 아니면 제일 위의 데이터 삭제
(3) DATA = STACK[TOP]
(4) TOP = TOP – 1
(5) 종료
일단 구조체를 쓰는 방법을 소개합니다. 배열로 하는 것은 구조체 안의 변수들을 밖으로 끄집어내서 선언하는 것이 차이점입니다. 포인터도 안써도 되구요.
구현 예:
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<stdio.h> #define STACK_MAX_SIZE 100 // 배열이므로 대략 100개 저장 가능하게 선언 struct stack { int stack[STACK_MAX_SIZE]; // 배열로 데이터 저장 int Top; // 제일 위인지 가리키는 값 }; typedef struct stack NODE; void push(NODE *pu, int item) { if (ptr->Top == STACK_MAX_SIZE – 1) { printf(“\n스택이 꽉 찼습니다.”); } else { pu->stack[++ptr->Top] = item; // 제일 위에 item 추가 } } int pop(NODE *po) { int item; if (po->Top == -1) printf(“\n스택이 비어있습니다.”); else { return item = po->stack[po->Top--]; // 꺼내온 데이터를 리턴하고 Top을 하나 줄임 } } void main(void) { NODE *ps; ps->Top = –1; push(ps, 1982); push(ps, 8202); printf("%d", pop(ps)); // 8202 추출 } |