2. 스택 (Stack)

1. 개요

후입선출(後入先出, Last In First Out; LIFO) 의 자료구조로, 상자의 형태를 한 자료구조이다.
데이터의 삽입을 Push, 데이터의 출력을 Pop이라고 하며,
스택을 크게 두 가지로 나누면
Ascending Stack VS Descending Stack으로 나눌 수 있다.

스택은 배열과 링크드 리스트로 구현할 수 있는데, 여기서는 링크드리스트를 이용한 스택을 구현해 보겠다.

2. 코드 구현

2-1 ) 구조체 구현

typedef struct _stacknode Snode; struct _stacknode { DataType data; Snode *next; }; typedef struct _stack { Snode *head; Snode *tail; Snode *cur; }Stack;

각 스택 노드는 데이터와 다음 노드를 가리키는 노드포인터로 구성돼있고,
스택관리구조체 Stack은 링크드리스트 구조체처럼 head와 tail을 고정적으로 가리키는 노드포인터와 현재 노드를 가리키는 cur 포인터로 이루어져있다.

---

2-2 ) 스택 생성 및 초기화

void initStack(Stack *sPtr) { sPtr->head = (Snode *)malloc(sizeof(Snode)); //헤드 노드 생성 assert(sPtr->head!=NULL); sPtr->tail = (Snode *)malloc(sizeof(Snode)); //테일 노드 생성 assert(sPtr->tail!=NULL); /*헤드노드가 테일노드를, 테일노드가 헤드노드를 가리키게 함*/ sPtr->head->next=sPtr->tail; sPtr->tail->next=sPtr->tail; sPtr->cur = NULL; return ; }

헤드노드와 테일노드를 메모리 할당해주고 서로 가리키게 해준다

---

2-3 ) 데이터 삽입 (Push)

int push(Stack *sPtr, DataType inData) /* stack에 데이터 저장하기 */ { sPtr->cur = (Snode *)malloc(sizeof(Snode)); //새로운 노드 생성 if(sPtr->cur==NULL) // 메모리 할당 실패하면 push실패 { return FALSE; } //노드를 헤드노드 바로 뒤에 노드 추가 sPtr->cur->next=sPtr->head->next; sPtr->head->next=sPtr->cur; sPtr->cur->data = inData; //데이터 복사 return TRUE; }

전달인자로 스택구조체의 주소와 삽입할 데이터를 받는다.
새 노드를 할당하기위해 메모리를 할당하고 위로 쌓이는 것이므로 (처음 삽입하는경우) 헤드노드 바로 뒤에 노드를 추가해주는데, 두 번째 삽입부터는 노드가 이미 하나있기때문에 그 노드의 뒤로 삽입을 해야한다. 따라서, 새로 할당받은 노드의 다음주소에 그 이전 노드를 가리키게 하고 이전 노드는 새로 할당받은 노드를 가리키게 한다. 

---

2-4 ) 데이터 출력 (Pop)

int pop(Stack *sPtr, DataType *popData) { if(sPtr->head->next == sPtr->tail) // stack이 비어있으면 pop실패 { return FALSE; } *popData = sPtr->head->next->data; sPtr->cur = sPtr->head->next; sPtr->head->next = sPtr->head->next->next; free(sPtr->cur); return TRUE; }

전달인자로 스택구조체의 주소와 출력할 데이터의 주소값을 받는다.
제일 위에있는게 먼저 나가야하므로 popData에 가장 위에있는 노드의 data를 넣어주고,
제일 위에 있는 노드에 이어져 있는 선을 끊어주고 다음 노드와 이어주게 한다. 그리고 메모리 해제