스택과 큐

1. 스택

png

스택(Stack)은 한쪽으로 데이터를 저장하고 추출하는 자료구조를 가리킨다. 마지막으로 저장한 데이터를 가장 먼저 추출하므로 LIFO(Last In First Out)이라고 한다. 스택은 세 가지 요소로 구성된다.

• 스택에 값을 저장하는 Push

• 스택에서 마지막 값을 추출하는 Pop

• 스택의 끝을 가리키는 Top

2. 큐

png

큐(Queue, Linear Queue)는 한쪽에서 데이터를 저장하고 다른 한쪽으로 추출하는 자료구조를 가리킨다. 처음에 저장한 데이터를 가장 먼저 추출하므로 FIFO(First In First Out)이라고 한다. 큐는 네 가지 요소로 구성된다.

• 큐에 값을 저장하는 Enqueue

• 큐에서 값을 추출하는 Dequeue

• 큐의 시작을 가리키는 Front/Head

• 큐의 끝을 가리키는 Back/Tail/Rear

2.1. 원형 큐

png

선형 큐는 데이터가 꽉 차면 빈 공간을 활용하지 못하고 큐 사이즈를 늘리는 등의 추가 작업이 필요하다. 이 단점을 극복하기 위해 원형 큐가 나왔다. 원형 큐(Circular Queue)는 큐의 시작과 끝을 이어 원형 형태로 구현한 자료구조이다. 원형 구조이므로 front와 rear가 회전하며 데이터를 저장한다. 원형 큐는 큐를 원형으로 만든 것이므로 큐의 구성요소와 동일하다.

2.2. 덱

png

덱(Deque, Double-ended Queue)은 양쪽 끝에서 데이터를 저장하고 추출하는 자료구조를 가리킨다.

• 덱에 값을 저장하는 Insert

• 덱에서 값을 추출하는 Delete

• 덱의 시작을 가리키는 Front/Head

• 덱의 끝을 가리키는 Back/Tail/Rear