자료 구조 - Stack

stack 개념

밑이 막힌 긴 통에 비유

: 먼저 들어간(Push) 것이 아래에 있게 되고 나중에 들어간 것이 위에 있게 된다. 따라서 제일 나중에 들어간 것이 제일 먼저 나온다(POP). 

이 때문에 stack을 LIFO(Last In Firsto Out) 구조라고 한다.

위의 그림과 같이 stack에 값을 집어넣는 것을 Push, 값을 빼내는 것을 Pop이라고 한다.

자료구조에서의 Stack

배열로 구현

stack이 완전히 빈 경우는 top Index가 -1의 값을 가진다. 

#define MAX    3
 
int stack[MAX];
int stackTop;        
 
void init_stack(void)
{
    printf("\n -> Initialize stack.\n");
    stackTop = -1;
}

아래는 데이터를 추가(Push)하는 과정이다.

stack의 바닥은 배열의 index 0이 된다. 마지막에 저장된 데이터 위치가 top이 된다.

push 연산은 아래와 같이 정리된다.

 - push : Top을 위로 한칸 올리고, Top이 가리키는 위치에 데이터 저장

int push(int top)
{
    if (stackTop >= MAX - 1) // 스택이 꽉 찬 상태는 MAX -1 (배열의 마지막 index)
    {
        printf("\n -> Stack overflow.");
        return -1;
    }
    stack[++stackTop] = top;     // stackTop 한칸 올린 위치에 값(top)을 저장
    return top;
}

pop 연산은 아래와 같이 정리된다.

- pop : Top이 가리키는 데이터 반환 후, Top 위치를 한칸 내림

pop 연산시에는 stack이 텅 비어있는 경우를 가정해야 한다. 텅 빈 stack을 pop하면 Stack Underflow가 일어나게 된다.

int pop(void)
{
    if (stackTop < 0)    // stack이 비어있다면
    {
        printf("\n -> Stack underflow.");
        return -1;
    }
    return stack[stackTop--];    // top 한칸 내림
}

마지막으로 stack에 저장된 값을 출력하는 함수를 정의한다.

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");
}

위 함수를 토대로 main함수를 정의하고 출력결과를 살펴 본다.

#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;
}

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

연결리스트 초기화

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;
}

push 함수

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;
}

head->next가 stack의 상단이 된다.

pop 함수

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;
}

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을 가리키면서 초기화 형태로 돌아가게 된다.

void clear_stack(void)
{
    Node *dN, *d;
    dN = head->next;
    while (dN != tail)
    {
        d = dN;
        dN = dN->next;
        free(d);
    }
    head->next = tail;
}

마지막으로 stack의 데이터들을 보여주기 위한 함수이다.

void print_stack(void)
{
    Node *prt;
    prt = head->next;
    printf("\n 스택의 데이터 : \n");
    while(prt != tail)
    {
        printf("%d ", prt->Ldata);
        prt = prt->next;
    }
    printf("\n");
}

위 함수를 토대로 main함수를 정의하고 출력결과를 살펴 본다.

#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;
}

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이라고 해서 맨 위의 개체를 반환하되 제거는 하지 않는 것도 있지만 따로 함수로 구현하진 않았다.

그리고 배열의 경우에도 동적할당을 사용해볼 수 있으나 연결리스트에 비해 큰 이점이 없으므로 필요에 따라 선택하는게 좋을 듯 하다.