[자료구조] 스택, 큐,덱 | Stack, Queue, Deque

스택은 "쌓다"라는 의미처럼, 가장 나중에 들어온 값이 가장 먼저 나가는(LIFO,Last In First Out) 형태의 자료구조입니다.

삽입[Push] 위치 : 스택의 끝(맨 뒤)
삭제[Pop] 위치 : 스택의 끝(맨 끝)

스택의 활용
1. 응용 프로그램의 Undo(되돌리기) 기능
2. 웹사이트의 뒤로가기 기능
3. 재귀 함수의 구현

큐는 가장 먼저 들어온 데이터가 가장 먼저 나가는(FIFO,First In First Out) 형태의 자료구조입니다.

삽입[Enqueue] 위치: 큐의 끝(맨 뒤)
삭제[Dequeue] 위치: 큐의 시작(맨 앞)

큐의 활용
1. 프로세스 처리
2. 대기열 처리
3. 너비 우선 탐색의 구현

원형 큐[Circular Queue]
큐는 아래와 같이 Front, Rear라는 변수를 이용해 큐의 내부가 비어있는지를 파악합니다.

내부 데이터의 개수 = Rear - Front

하지만 위의 노란색 화살표에서 보이는 것과 같이, 한번 Dequeue가 일어나게 되면 Front 이전의 공간은
그대로 남겨지게 됩니다.

이 문제를 해결하기 위해 고안된 것이 원형 큐입니다.

원형 큐는 Front,Rear가 큐의 범위를 넘어서면,
(Front,Rear Mod 큐의 길이) 연산을 수행해 다시 시작 인덱스로 돌아오는
방식으로, 앞에서 언급한 공간을 재사용할 수 있게됩니다.
큐 내부에 들어있는 값의 수를 구하는 연산은 다음과 같습니다.

1) Front == Rear인 경우: 0개
2) Front < Rear인 경우: Rear - Front 개
3) Front > Rear인 경우: 큐 길이 - Front + Rear 개

덱[Deque, Double Ended Queue]
덱은 앞, 뒤 모두에서 값의 삭제와 추가가 이루어지는 자료구조입니다.
앞에서 설명한 원형 큐를 이용한 구현과 매우 유사합니다.
다만, Front에서 값의 추가가, Rear에서 값의 삭제가 이루어질 수 있다는 점에서 차이가 있습니다.