자료구조 - 스택과 큐(Stack and Queue), 링버퍼(Ring buffer)

스택(Stack)

---

스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다(가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.).

 

스택에 데이터를 넣는 작업을 푸시(push)라고 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다.

이때, 푸시와 팝을 하는 위치를 꼭대기(top)이라고 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다.

스택(Stack) 구조

 

스택의 push와 pop은 꼭대기 top자리에서만 이루어지므로 복잡도는 O(1)이다.

 

큐(Queue)

---

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조이다. 스택과 다르게 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, Fisrt In Fisrt Out) 구조로 되어있다. 생활에서 볼 수 있는 큐의 예는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 예로 들 수 있다.

 

큐에 데이터를 넣는 작업을 인큐(enqueue)라고 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다.

이때, 데이터를 꺼내는 쪽으로 프런트(front)라고 하고, 데이터를 넣는 쪽을 리어(rear)라고 한다.

 

큐(Queue) 구조

 

인큐는 rear의 자리에 새로운 데이터를 저장하기만 하면 되기 때문에 이 처리의 복잡도는 O(1)이다.

하지만 디큐는 데이터를 꺼낸 후 그 뒤의 요소들이 앞으로 옮겨가야한다. 따라서  이 처리의 복잡도는 O(N)이며 데이터를 꺼낼때마다 이런 처리를 하게 되면 효율이 떨어진다.

 

링버퍼 (Ring Buffer)

링버퍼는 배열 요소를 앞쪽으로 옮기지 않는 큐를 구현한 자료 구조이다. 링버퍼는 아래 그림과 같이 배열의 처음과 끝이 연결되어 있다고 보는 자료구조이다. 여기서 논리적으로 어떤 요소가 첫번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수가 프런트(front)와 리어(rear)이다.

 

• 프런트(front): 맨 처음 요소의 인덱스(데이터를 디큐할 위치)
• 리어(rear): 맨 끝 요소의 하나 뒤의 인덱스(다음 요소를 인큐할 위치를 미리 지정)

링버퍼(Ring buffer) 구조

위의 그림을 예시로, 디큐 / 인큐할 경우를 살펴보자.

위의 그림에서는 front = 0, rear = 5이다.

 

• 디큐할 경우: 36(que[0])을 디큐한 후 front값을 que[1]로 없데이트해준다. 
• 인큐할 경우: que[5]의 자리에 64를 저장한다. 그리고 나서 rear값을 que[0]으로 업데이트해준다.(저장공간이 6이기 때문에 index 5에서 0으로 업데이트된다. 만약 저장공간이 6보다 컸다면, 인덱스 값을 1만큼 증가시켜서 다음 인큐할 데이터는 que[6]에 저장될 것이다.)

이렇게 큐를 구현하면 프런트와 리어 값을 업데이트하면서 인큐와 디큐를 수행하기 때문에 앞의 큐에서 발생했던 요소 이동 문제를 해결할 수 있다. 물론 처리의 복잡도는 O(1)이다.