C - 스택(Stack)

1. 스택이란?

스택, 위키백과 출처

스택이란 LIFO(Last In First Out) 즉, 후입선출 구조를 가진 자료구조이다.

쓰레기통을 생각하면 가장 편하게 떠올릴 수 있으며, 게임을 좋아하는 사람이라면 스택이란 용어가 익숙할 것이다.

 

2. 스택의 구현

스택의 구현을 어떻게 할까?

구현 방법에 대해서는 이미 우리는 알고 있다.

앞에서 배운 배열과 링크드리스트 중 하나를 선택하는 것이다.

 

2-1. 배열을 이용한 스택의 구현

// stack_array.c

#define MAX_LEN 5

#include<stdio.h>

int count = 0;
int array[MAX_LEN];

void push(int num);
void pop();
void show();

int main(void){
        int i;

        for(i=0; i<MAX_LEN; i++)
                push(i);
        show();
        for(i=0; i<MAX_LEN; i++)
                pop();

        show();
        return 0;
}

void push(int num){
        for(int i=count; i>0; i--)
                array[i] = array[i-1];

        array[0] = num;
        printf("push : %d\n", num);
        count++;
}

void pop(){
        printf("pop : %d\n", array[0]);
        for(int i=0; i<count-1; i++)
                array[i] = array[i+1];
        array[--count] = -1;
}

void show(){
        printf("ARRAY INFO\n");
        printf("COUNT : %d\n", count);
        for(int i=0; i<MAX_LEN; i++)
                printf("%d -> ", array[i]);
        printf("\n");
}

 

 

이번 구현은 편하게 전역변수를 이용했다.

구현에 있어서 중요한 요소들은 다음과 같다.

 

• 전역변수 int count : 현재 스택에 있는 데이터의 갯수
• int array[MAX_LEN] : 스택의 역할을 할 배열
• #define MAX_LEN 5 : 배열의 길이인 5를 선언
• push, pop, show 함수 : 각각 스택에 값을 저장, 꺼내기, 스택을 보여주기 역할을 하는 함수

 

 

먼저 main함수에서의 동작은 다음과 같다.

1. 스택에 반복문을 이용하여 0~4의 값을 push
2. show()를 통하여 현재 상태 출력
3. 반복문을 이용하여 pop()을 5번 호출
4. show()를 통하여 현재 상태를 출력

다음은 push 함수의 동작을 도식화 해보았다.

 

push의 과정

 

배열을 활용한 스택의 경우, 각 원소들을 뒤로 한칸씩 계속 밀어줘야한다.

맨 마지막 배열의 4가 들어간 곳을 쓰레기통의 입구라고 생각하고, 0이 저장된 곳이 쓰레기통의 바닥이라고 생각하면 편하다.

pop의 경우, 원소들이 미뤄지는 방향만 바꾼것이라고 생각하면 편하다.

 

pop의 과정

pop에서는 이렇게 빠져나간 자리에는 -1을 대입하여서 빠져나갔음을 표시해 주었다.

 

프로그램을 실행하면 다음과 같이 동작한다.

배열을 활용한 stack의 출력

 

2-2. 링크드 리스트를 이용한 스택의 구현

// stack_linkedList.c

#define INPUT_LEN 5

#include<stdio.h>
#include<stdlib.h>

typedef struct Node{
        int data;
        struct Node *next;
}node;

void push(int num);
void pop();
void show();

node* head = NULL;

int main(void){
        int i;
        for(i=0; i<INPUT_LEN; i++)
                push(i);

        show();

        for(i=0; i<INPUT_LEN; i++)
                pop();
        show();
        return 0;
}

void push(int num){
        node* new_node = (node*)malloc(sizeof(node));
        new_node->data = num;
        new_node->next = head;
        head = new_node;
        printf("push %d\n", head->data);
}

void pop(){
        node* temp = head;
        printf("pop %d\n", head->data);
        head = head->next;
        free(temp);

}

void show(){
        node* temp = head;
        if(temp == NULL) printf("NO STACK!");
        while(temp != NULL){
                printf("%d ->", temp->data);
                temp = temp->next;
        }
        printf("\n");

}

 

 

링크드 리스트를 활용한 스택의 구현 또한 쉽게 만들어 봤다.

코드의 길이는 길어졌을 지 모르겠으나 링크드 리스트를 이용한 구현이 더욱 편리하다.

링크드리스트에서 필요한 필수 요소는 다음과 같다.

• 스택 접근을 위한 전역변수 head
• push, pop, show 함수

 

 

배열보다 훨씬 간단하지 않은가?

 

main 함수의 구성은 array로 구현했을때와 동일하다.

 

그럼 링크드 리스트를 활용한 각 동작을 도식화한 사진을 보면서 이해해보도록 하겠다.

링크드 리스트의 push 과정

새로운 값을 가진 노드를 이전 head와 연결해주고, 새로운 노드를 다시 head로 지정해주면 끝난다.

녹색 상자를 살펴보면, 배열에 비해 얼마나 간단한지 알 수 있다.

 

배열의 경우 새로운 값이 들어오게 된다면 나머지 요소들을 다 뒤로 한칸씩 미뤄줘야 했다.

허나 링크드리스트를 사용한다면 노드의 연결과정과 head의 재설정만 해주면 끝난다.

 

배열과 linked list의 비교

 

좌측이 배열을 사용한 push 과정이고 우측이 linked list를 이용한 push 과정이다.

얼마나 linked list가 간단한지 한눈에 보이지 않는가?

 

pop 과정 또한 역시 free()를 활용하여 노드의 메모리 할당을 해제해주고 head를 기존 head의 next로 설정해주기만 하면 끝이다.

 

3. 정리

배열과 링크드리스트를 활용하여 스택을 구현해보았다.

아직까지는 큰 어려움이 없는 자료구조라고 생각한다.

 

하지만 링크드리스트를 공부한지 얼마 안된 사람들이라면 링크드 리스트의 강력함을 알았으면 좋겠고 배열보다는 노드구조를 활용하여 구현하는 것에 익숙해졌으면 좋겠다.