스택과 큐

개요

기본적인 자료구조는 객체를 모아 놓은 것입니다. 예를들어 집합(set)은 값의 모음이고, 관련된 연산으로는 값을 추가하고, 삭제하고, 집합내부에 값이 있는지 조사하는 것이 있을 수 있습니다. 이러한 객체를 모아 놓은 기본 자료구조로는 큐와 스택이 있습니다. 이 둘은 간단하면서 널리 사용되기 때문에 유용합니다. 이 두 자료구조를 C 언어를 이용하여 구현해보도록 하겠습니다.

스택

LIFO (Last In First Out) 정책에 기반한 자료구조입니다. 출입구를 한쪽으로만 제한한 자료구조입니다. 가장 마지막에 자료구조로 삽입된 아이템이 가장 먼저 밖으로 빠져나오는 구조입니다. 실생활에서는 먼저 엘리베이터에 탑승한 사람이 엘리베이터의 안쪽으로 밀려 들어가기 때문에 가장 나중에 내리게 되는 현상을 통해서 LIFO 가 어떠한 것인지 감을 잡을 수 있습니다.

연산자

기본적으로 스택과 관련하여 아래의 2개의 연산이 필요합니다.

• void push(Item item) : 스택에 아이템을 추가합니다.
• Item pop() : 스택에서 가장최근에 추가한 아이템을 제거합니다.

구현

아래와 같이 간단히 구현해 볼 수 있습니다.

// main.c

#define STACKSIZE   256
#include <stdio.h>

typedef struct {
    int top;
    int items[STACKSIZE];
} Stack;

void init(Stack *s) {
    s->top = 0;
}

void push(Stack *s, int i) {
    s->items[s->top++] = i;
}

int pop(Stack *s) {
    return s->items[--s->top];
}

int main (void) {
    Stack s;
    init(&s);

    push(&s, 7);
    push(&s, 0);
    push(&s, 6);
    push(&s, 2);
    push(&s, 9);
    
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));
    printf("%d\n", pop(&s));

    return 0;
}

큐

FIFO (First In First Out)정책에 기반한 자료구조입니다.

연산자

큐 역시 기본적으로 아래의 2개의 연산이 필요합니다.

• void EnQueue(Item item) // 큐에 Item 을 넣습니다.
• Item DeQueue(); // 큐에서 가장처음에 추가한 Item 을 제거합니다.

구현

스택과 마찬가지로 큐 역시 아래와 같이 배열을 사용하여 구현할 수 있습니다.

// main.c 

#define QUEUESIZE   256
#include <stdio.h>

typedef struct {
    int head, tail;
    int items[QUEUESIZE];
} Queue;

void fnInit (Queue *q) {
    q->head = q->tail = -1;
}

void fnEnque(Queue *q, int i) {
    q->items[++q->tail] = i;
}

int fnDequeue(Queue *q) {
    return q->items[++q->head];
}

int main (void) {
    Queue q;
    fnInit(&q);

    fnEnque(&q, 7);
    fnEnque(&q, 0);
    fnEnque(&q, 6);
    fnEnque(&q, 2);
    fnEnque(&q, 9);
    
    printf("%d\n", fnDequeue(&q));
    printf("%d\n", fnDequeue(&q));
    printf("%d\n", fnDequeue(&q));
    printf("%d\n", fnDequeue(&q));
    printf("%d\n", fnDequeue(&q));

    return 0;
}

이들의 동작을 그림으로 살펴보면 다음과 같습니다.

fnInit()

    H, T         
     ↓
(out) □ □ □ □ □ □ (in) @ QUEUESIZE(=6)

fnEnqueue(7)

    H T         
    ↓ ↓
(out) ■ □ □ □ □ □ (in) @ QUEUESIZE(=6)

fnEnqueue(0)

    H   T         
    ↓   ↓
(out) ■ ■ □ □ □ □ (in) @ QUEUESIZE(=6)

…

fnDequeue()

      H         T         
      ↓         ↓
(out) □ ■ ■ ■ ■ ■ (in) @ QUEUESIZE(=6)

fnDequeue()

        H       T         
        ↓       ↓
(out) □ □ ■ ■ ■ ■ (in) @ QUEUESIZE(=6)

완성된 소스코드의 동자글 확인해보면, 스택과 달리 규는 저장공간을 1회만 사용하는 것을 알 수 있습니다. 때문에 이 구현 예에서는 256(QUEUESIZE) 회의 Enqueue 연산 이후, 해당큐는 더 이상 데이터를 집어 넣을 수 없습니다. 때문에 이를 그대로 사용하기에는 일반적으로 문제가 있습니다.

이에 대한 개선 방법은 가장 마지막 저장공간과 가장 처음 저장공간을 연결하는 원형큐를 사용하는 것이 있을 수 있습니다.

또한, 연결 리스트를 사용하여 임의의 메모리에 데이터를 저장하는 방법이 있을 수 있습니다.