[C언어와 함께 자료구조를] 연결리스트로 스택 구현

스택 개념 다시보기

스택(Stack)은 단어의 뜻에서 의미하듯 쌓아 놓는 구조로 매우 간단합니다. 예를 들면, 책 10권을 차례대로 쌓았다고 하면 책을 치우기 위해서 맨 위에서 부터 차례차례 치워나가는 방식이라고 할까요? 가장 나중에 쌓은 책이 먼저에 치워지니 LIFO(First-In Last-Out)이라고도 하고 가장 먼저 쌓은 책이 나중에 치워지니 FILO(First-In Last-Out)이라고도 부를 수 있겠네요.

스택을 조작하는 연산은 딱 두가지만 기억하자고 했는데. 스택에 집어넣는 연산 push와 스택에서 빼내는 연산 pop입니다.

연결리스트로 스택 구현하기

스택의 구현은 배열을 사용하던 연결리스트(Linked list)를 사용하던 상관없지만, 이전 포스팅에서는 연결리스트를 이용한 스택을 구현해 보겠습니다.

배열을 이용한 스택의 구조에서는 스택의 크기를 정의하고 top이라는 변수가 스택의 마지막 데이터가 들어가 있는 위치인 배열 인덱스를 가리키도록 정의 했었는데요. 연결리스트를 이용하면 스택의 크기를 따로 정의할 필요가 없습니다. 또한 마지막 데이터가 들어있는 위치도 연결리스트의 마지막데이터를 읽으면 되니 따로 선언하지 않아도 됩니다.

우선 연결리스트를 아래와 같이 정의를 해볼께요.

typedef struct _node {
    int key;
    struct _node *next;
} node;

node *head, *tail;
node *data;

다음으로 스택을 초기화 하는 함수를 만들텐데, 우선 두개의 노드 head와 tail을 만들어 초기화 하겠습니다. 여기서는 tail이 스택의 바닥이고 head다음 노드에서 데이터가 입출력이 발생한다고 가정합니다.

void init_stack ()
{
	head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    
    head->next = tail;
    tail->next = tail;
}

다음으로 스택의 연산인 push와 pop을 정의하겠습니다. push 연산은 데이터를 쌓는 연산인데, head 다음에 노드를 하나 insert하는 링크드 리스트 연산을 정의 하겠습니다.

int push (int val)
{
    data = (node *)malloc(sizeof(node));
    data->key = val;
    data->next = head->next;
    head->next = data;
}

pop연산은 데이터를 빼내는 연산인데 head 다음 노드의 데이터를 읽은 후 노드를 삭제하면 됩니다. 배열과 달리 스택의 크기 제한이 없기 때문에 push연산에서는 stack overflow를 확인할 필요가 없었지만, pop연산에서는 데이터가 하나도 없는 stack underflow를 체크할 필요가 있습니다.

int pop ()
{
    int key;
    data = head->next;
    if (data == tail) {
        printf ("\n  Stack Underflow\n");
        return -1;
    }
    head->next = head->next->next;
    key = data->key;
    free (data);
    
    return key;
}

다음은 전체 소스와 실행 결과입니다. 배열을 이용한 스택 구현과 동일한 함수 이름을 사용했으니 참고하시기 바랍니다.

연결리스트를 이용한 스택도 별거 없었죠? 

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


typedef struct _node {
    int key;
    struct _node *next;
} node;

node *head, *tail;
node *data;

void init_stack ()
{
	head = (node *)malloc(sizeof(node));
    tail = (node *)malloc(sizeof(node));
    
    head->next = tail;
    tail->next = tail;
}

int push (int val)
{
    data = (node *)malloc(sizeof(node));
    data->key = val;
    data->next = head->next;
    head->next = data;
}

int pop ()
{
    int key;
    data = head->next;
    if (data == tail) {
        printf ("\n  Stack Underflow\n");
        return -1;
    }
    head->next = head->next->next;
    key = data->key;
    free (data);
    
    return key;
}

void print_stack ()
{
    node *sp;
    printf ("\n Stack From Top-----> To Bottom\n");

    for (sp = head->next; sp != tail; sp = sp->next)
        printf("%-6d", sp->key);
}

void main ()
{
    int i;
    init_stack ();

    printf("\nPush 5, 4, 7, 8, 2, 1");
    push(5);
    push(4);
    push(7);
    push(8);
    push(2);
    push(1);
    print_stack();
    
    printf("\nPop");
    i = pop();
    print_stack();
    printf("\n  popped value is %d\n", i);
    
    printf("\nPop");
    i = pop();
    print_stack();
    printf("\n  popped value is %d\n", i);

    printf("\nPush 3, 2, 5, 7, 2");
    push(3);
    push(2);
    push(5);
    push(7);
    push(2);
    print_stack();
    
    printf("\nInitialize stack");
    init_stack();
    print_stack();
    
    printf("\nNow Stack is empty, pop");
    i = pop();
    print_stack();
    printf("\n  popped value is %d\n", i);

}

실행결과입니다...

PS C:\CS> .\linkedlist_stack.exe

Push 5, 4, 7, 8, 2, 1
 Stack From Top-----> To Bottom
1     2     8     7     4     5
Pop
 Stack From Top-----> To Bottom
2     8     7     4     5
  popped value is 1

Pop
 Stack From Top-----> To Bottom
8     7     4     5
  popped value is 2

Push 3, 2, 5, 7, 2
 Stack From Top-----> To Bottom
2     7     5     2     3     8     7     4     5
Initialize stack
 Stack From Top-----> To Bottom

Now Stack is empty, pop
  Stack Underflow

 Stack From Top-----> To Bottom

  popped value is -1

 

다음에는 연결리스트를 이용하여 큐를 구현하도록 할께요. 안녕~