스택(Stack)과 큐(Queue)

선형 자료구조인 스택과 큐의 개념 및 특징을 이해하고 배열과 링크드리스트로 구현 시 어떤 장단점이 있는지 알아보자

여기서 선형구조란 데이터가 순차적으로 나열되어 있는 구조를 뜻한다.

스택(Stack)

스택은 데이터의 삽입 삭제가 한 쪽에서 이루어지는 후입선출(Last In First Out) 자료구조이다.

따라서 가장 최근에 들어온 데이터의 위치를 뜻하는 Top을 유지해야 한다.

Push(), Pop()으로 삽입 삭제가 이루어진다.

배열과 링크드리스트로 구현할 수 있다.

배열로 구현시 스택의 크기가 정해지기 때문에 스택 용량을 초과하는 삽입연산이 이루어질 수 없어서 비효율적이다.

이러한 문제는 링크드리스트로 해결할 수 있다. 데이터가 삽입될 때마다 tail에 연결시켜주고 tail을 업데이트 해서 Top을 뜻하게 하면 된다.

큐(Queue)

큐는 데이터의 삽입 삭제가 서로 다른 방향에서 이루어지는 선입선출(First In First Out) 자료구조이다.

가장 먼저 들어온 데이터 뒤에, 그 다음에 들어온 데이터들이 위치하게 된다.

따라서 가장 앞에 있는 데이터, 맨 뒤에 있는 데이터를 가리키는 정보를 가지고 있어야 하며 이는 front와 rear를 사용한다.

Enqueue() 삽입, Dequeue() 삭제, Capacity() 큐의 크기를 뜻한다.

큐가 가득 찼을 때 삽입할 수 없으며 큐가 비어있을 때 삭제할 수 없다.

큐도 스택과 마찬가지로 배열과 링크드리스트로 구현할 수 있다.

큐를 배열로 구현

스택과 마찬가지로 큐를 배열로 구현했을 때 큐의 크기가 정해진다는 문제점이 있지만 이와 더불어 삽입 삭제 연산이 이루어지면서 front와 rear의 위치가 뒤로 점점 밀려나면서 앞 쪽에는 데이터가 들어올 수 있는 공간이 있지만 rear가 배열 인덱스에 가장 마지막을 가리키고 있다면 enqueue했을 때 실제로 큐에 공간이 있음에도 불구하고 삽입할 수 없는 문제가 생기게 된다. 즉 삭제가 이루어졌을 때 나머지 데이터가 앞쪽으로 이동하지 않으면 공간의 낭비가 생기게 된다. 이것이 큐를 배열로 구현했을 때 생기는 문제점이며 환형배열을 통해 해결한다.

환형배열이란 물리적으론 선형배열이지만, 처음과 끝을 이어 배열의 구조를 원형으로 보는 것이다.

아래 그림은 환형배열로 구현한 큐이며 삽입될 때마다 rear가 어떻게 바뀌는지 보여주고 있다.

그러나 환형배열의 문제점은 데이터가 비어있을 때와 데이터가 가득 찼을 때 두 상태를 구분할 수 없다는 문제점이 있다. 즉 위의 그림에서 첫번째와 마지막을 보면 분명 서로 다른 상태(큐가 비어있는 경우, 가득 찬 경우)지만 front와 rear가 같은 위치를 가리키고 있기 때문에 문제가 생긴다.

이 문제를 해결하기 위해선 더미공간으로 하나의 공간을 사용하지 않으면 된다. 위에선 배열의 크기가 4였고 4개의 모든 공간을 사용하였다. 이제 우리는 배열의 크기는 4지만 실제론 3개만 사용할 것이다. 즉 배열의 크기가 n일 때 n-1개의 공간만 사용하겠다는 뜻이다. 아래 그림을 보자

빨간색 X가 있는 공간은 실제로 존재하지만 존재하지 않는 공간으로 가정하고 사용하지 않겠다는 뜻이다. 이러면 처음에 발생했던 문제를 해결할 수 있다. 즉 큐가 비어있는 경우와 가득 차있는 경우 각각 front와 rear의 위치가 서로 다르기 때문에 우리는 두 상태를 이제 구분할 수 있다.

그렇다면 실제 구현에서 어떻게 처리해줘야 할까?

환형배열에선 인덱스 n-1의 다음 인덱스는 0이 되어야 하므로 mod연산을 이용한다.

삽입(Enqueue)은    rear = (rear + 1) % n

삭제(Dequeue)는    front = (front + 1) % n임을 기억하자.

여기서 n은 배열의 크기이므로 4로 가정한다.

초기엔 front, rear 0일 것이다.

데이터가 삽입되면 rear = (0 + 1) % 4,    rear = 1이 되어 한 칸 이동한다. 이런 식으로 mod연산을 통해 논리적인 환형배열을 사용하는 것이다.

큐가 이미 가득 차있을 때 삽입하려는 경우를 보자

우선 rear가 3이라는 것은 큐가 가득 찬 상태를 뜻한다.

여기서 삽입을 하면 rear = (3 + 1) % 4,   rear = 0이 되어 front와 같은 값을 가지게 되므로 큐가 이미 가득 차있을 때 삽입하려는 문제를 막을 수 있다.

즉, rear = (rear + 1) % n의 값이 front와 같다면 현재 큐는 가득 찼기 때문에 삽입을 못하게 하면 된다.

다음으로 큐가 비어있을 때 삭제하려는 경우를 살펴보자

큐가 비어있다는 것은 front와 rear의 값이 같은 경우이다.

여기서 Dequeue 연산을 할 때 front와 rear 값이 같은지 먼저 확인해주고 만약 같다면 큐가 비어있는 상태이므로 삭제를 못하게 하면 된다.

환형배열로 큐를 구현하면 연산이 더 빠르다는 장점이 있지만 어찌됐든 배열이기 때문에 크기가 이미 정해져있다는 한계가 있다.

링크드리스트를 이용하여 큐를 구현하는 경우를 생각해보자

head와 tail이 큐의 front와 rear의 역할을 하게끔 하여 링크드리스트로 큐를 구현하면 무척 쉽게 만들 수 있다.

맨 앞, 맨 뒤의 정보를 가지고 있기 때문에 삽입과 삭제가 O(1)에 이루어진다.