04. 자료구조론 - 스택, 큐 (Stack, Queue)

스택 (Stack)

스택은 순서가 있는 리스트의 한 종류입니다. 그리고 리스트 아이템의 삽입과 삭제가 모두 리스트의 한쪽에서 일어납니다.

스택에서 수행할 수 있는 연산은 Push, Pop, Top 이 있습니다.

스택에서 삽입은 push, 삭제는 pop이 됩니다.

위와 같이 스택에 X를 push하면 무조건 리스트의 맨 위에 쌓이게되고, pop을 하면 맨 위에 있는 아이템이 리스트에서 제거됩니다.

그리고 top 연산자는 리스트 맨 위의 아이템을 리턴하지만, 해당 아이템을 리스트에서 제거하지는 않습니다. 

스택은 일반적인 배열을 통해 구현할 수도 있고, 앞선 게시물의 linked list를 이용하여 구현할 수도 있습니다.

Array 를 이용한 Stack 구현

typedef struct _Stack {
    int capacity;
    int top_index;
    int* array;
} Stack;

우선 위와 같이 스택을 의미하는 구조체를 만듭니다.

배열을 이용하므로 스택의 최대사이즈는 처음에 지정될 수 밖에 없기 때문에 해당 최대사이즈가 capacity에 들어갑니다. 그리고 배열내에서 스택의 최상위 아이템의 인덱스가 top_index에 들어갑니다. top_index 이후의 아이템들은 의미없는 아이템들이 됩니다.

그리고 array는 실제 스택배열이 되게됩니다.

스택에서 수행하는 operation들은 다음과 같이 구현할 수 있습니다.

스택 생성

Stack* CreateStack(int max_size) {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    if (s == NULL) {
    	return NULL; // ERROR: Out of space
    }
    s->array = malloc(sizeof(int) * max_size);
    if (s->array == NULL) {
    	return NULL; // ERROR: Out of space
    }
    s->capacity = max_size;
    s->top_index = -1 // 스택이 비어있음을 의미
}

Push(S, X)

bool IsFull(Stack* S) {
	return S->top_index+1 == S->capacity
}

void Push(Stack* S, int x) {
    if (IsFull(s)) {
        return; // ERROR: 스택이 꽉 차서 더이상 Push가 불가능함
    } else {
        s->array[++(s->top_index)] = x;
    }
}

스택에 새로운 아이템 x를 push 하려면 top_index가 하나 증가하고 array의 유효한 아이템의 최상단에 x를 넣어주면 됩니다.

Pop(S)

bool IsEmpty(Stack* s) {
	return s->top_index == -1
}

void Pop(Stack* s) {
    if (IsEmpty(s)) {
        return; // Error: 스택이 비어 pop할 수 없음
    } else {
        s->top_index--;
    }
}

배열을 이용해 스택을 만들면, pop을 구현할 때 실제 값을 지워줄 필요 없이 top_index를 하나 내려주면 됩니다.

Top(S)

int Top(Stack* s) {
    if (IsEmpty(s)) {
        // do something for error handling
        return -1;
    }
    return s->array[s->top_index];
}

Top의 경우는 스택의 array에서 맨 위 아이템을 리턴해주기만 하면됩니다. 맨위 아이템은 스택의 top_index를 통해 접근할 수 있습니다.

Linked List를 이용한 Stack 구현

typedef struct _Node {
	int element, 
	struct _Node next;
} Node;

typedef Node* Stack;

앞선 게시물의 linked list와 동일하게 스택을 구현할 수 있으며, 아이템의 삽입과 삭제가 맨 앞쪽(헤더노드의 바로 뒤)에서만 일어나도록 하면 됩니다.

스택 생성

Stack CreateStack() {
    Stack s = malloc(sizeof(Node));
    if (s == NULL) {
        // do something for error handling
    }
    s->next = NULL;
    return s;
}

Push(S, X)

void Push(Stack s, int x) {
	Node* newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        // do something for error handling
    } else {
        newNode->element = x;
        newNode->next = s->next;
        s->next = newNode;
    }
}

다음 그림과 같이 헤더노드의 바로 뒤에 새로운 노드가 들어가도록 링크를 연결해줍니다.

Pop(S)

bool IsEmpty(Stack s) {
	return s->next == NULL;
}

void Pop(Stack s) {
    Node* firstNode;
    if (IsEmpty(s)) {
        // do something for empty stack exception handling
    } else {
        firstNode = s->next;
        s->next = firstNode->next;
        free(firstNode);
    }
}

Pop시에는 헤더노드 바로 뒤의 노드를 연결고리에서 끊어주고 해당 노드의 메모리를 할당해제해줍니다.

Top(S)

int Top(Stack s) {
    if (!IsEmpty(s)) {
    	return s->next->element;
    }
    // do something for empty stack exception handling
    return -1;
}

---

큐 (Queue)

큐도 스택과 마찬가지로 순서가 있는 리스트이지만, 삽입과 삭제가 리스트의 반대 방향에서 일어납니다. 한쪽에서 삽입을 하면 삭제를 할때는 반대쪽의 아이템이 삭제됩니다.

큐에서 삽입은 enqueue, 삭제는 dequeue 가 됩니다.

그리고 삽입이 일어나는 한쪽 끝을 rear, 삭제가 일어나는 한쪽 끝을 front라고 합니다.

큐는 배열을 이용해 만들 수 있습니다. 다음과 같이 배열에 아이템들을 저장해놓고 front와 rear에 해당하는 인덱스 또한 저장해놓습니다.

그리고 이 인덱스를 옮겨가며 enqueue와 dequeue를 수행할 수 있습니다. 

#define MAX_SIZE 100

typdef struct _Element {
	int value;
} Element;

Element queue[MAX_SIZE];
int rear = -1;
int front = 0;

Enqueue

void Enqueue(Element* queue, Element item) {
    if (rear == MAX_SIZE-1) {
        // do something for full queue exception handling
    } else {
        queue[++rear]= item;
    }
}

rear는 큐가 비었을 때를 제외하면 항상 큐의 마지막 아이템의 인덱스를 담고 있으므로, rear가 최대 사이즈-1 (인덱스는 0부터 시작하므로) 와 같으면 큐가 꽉 찬 것이어서 더이상 Enqueue를 수행할 수 없습니다.

큐가 꽉차지 않았다면 rear를 하나 증가시키고 해당 자리에 새로운 아이템을 넣어주면됩니다.

Dequeue

Element Dequeue(Element* queue) {
    if (front > rear) {
        // do something for empty queue error handling
    } else {
        return queue[front++];
    }
}

front는 배열이 비었을 때를 제외하면 항상 배열의 첫번째 요소를 가리키고 있습니다. 그런데 배열이 비게되면 front가 rear보다 1만큼 더 큰 상태가 되게됩니다. 따라서 front > rear 이라는 부등식을 통해 배열이 비었을 때를 탐지할 수 있습니다.

배열이 비지 않았다면 front가 배열의 첫번째 아이템을 가리키고 해당 요소가 지워져야할 아이템이므로, 해당 값을 리턴해주고 front는 1만큼 더해주면 dequeue가 되게됩니다.

하지만 이렇게 구현하면 다음과 같이 큐에 MAX_SIZE만큼 enqueue가 일어난 후에는 다른 아이템이 dequeue되어 배열에 빈 부분이 생기더라도 더이상 enqueue를 진행할 수 없게됩니다. 

Circular Queue

위의 문제를 해결하기 위한 방법으로 Circular queue가 있습니다. Circular queue에서는 front나 rear가 배열의 끝에 도달하면 그 이후에 다시 index가 0으로 돌아가서 앞의 빈 배열의 재사용하게 됩니다.

typedef struct _Queue {
    int capacity;
    int front;
    int rear;
    int size;
    int* array;
} Queue;

Queue* CreateQueue(int max_size) {
    Queue* queue = malloc(sizeof(Queue));
    queue->capacity = max_size;
    queue->front = 1;
    queue->rear = 0;
    queue->size = 0;
    queue->array = (int*)malloc(sizeof(int)*max_size);
    
    return queue;
}

그리고 Circular Queue의 경우에는 rear와 front의 위치 순서로 큐의 사이즈를 알 수 없기 때문에 큐의 사이즈를 저장하는 변수를 추가적으로 저장하고 있어야합니다.

Enqueue

static int getNextIndex(int capacity, int index) {
    if (++index == capacity) index = 0;
    return index;
}

bool IsFull(Queue* q) {
	return q->size == capacity-1;
}

void Enqueue(Queue* q, int x) {
    if (IsFull(q)) {
        // do something for full queue exception handling
    } else {
        q->size++;
        q->rear = getNextIndex(q->rear, q->capacity);
        q->array[q->rear] = x;
    }
}

위와 같이 인덱스가 배열의 마지막에 도달하면 0으로 돌려주는 getNextIndex를 이용하여 rear를 이동시켜 enqueue를 구현할 수도 있고,

void Enqueue(Queue* q, int x) {
    if (IsFull(q)) {
        // do something
    } else {
        q->size++;
        q->rear = (q->rear + 1) % q->capacity;
        q->array[q->rear] = x;
    }
}

%를 이용한 나머지 연산을 통해 인덱스를 순환시킬 수도 있습니다. 

Dequeue

int Dequeue(Queue* q) {
    if (q->size == 0) {
    	// do something for empty queue exception handling
    } else {
        q->size--;
        int dequeue_item = q->array[q->front]
        q->front = (q->front + 1) % q->capacity;

        return dequeue_item;
    };
}

 dequeue의 경우에는 지울 아이템을 리턴하기 위해 미리 저장해놓고 front를 한칸 땡겨주면 됩니다.