Stack, Queue, Deque

1. Stack

Stack

- 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다.

- 마지막으로 넣은 것이 가장 먼저 나오기 때문에 LIFO(Last In First Out)라고도 한다.

- 일차원 배열 하나로 구현한다.

연산	설명
push	스택에 자료를 넣는 연산이다.
pop	스택에서 자료를 빼는 연산이다.
top	스택의 가장 위에 있는 자료를 보는 연산이다.
empty	스택이 비어있는지 아닌지를 알아보는 연산이다.
size	스택에 저장되어 있는 자료의 개수를 알아보는 연산이다.

 

2. Queue

- 한 쪽 끝에서만 자료를 넣고 다른 한 쪽 끝에서만 뺄 수 있는 자료구조이다.

- 먼저 넣은 것이 가장 먼저 나오기 때문에 FIFO(First In First Out)라고도 한다.

- 일차원 배열 하나로 구현한다.

연산	설명
add	큐에 자료를 넣는 연산이다.
offer	큐에 자료를 넣는 연산이다.
poll	큐에서 자료를 빼는 연산이다.
front	큐의 가장 앞에 있는 자료를 보는 연산이다.
back	큐의 가장 뒤에 있는 자료를 보는 연산이다.
empty	큐가 비어있는지 아닌지를 알아보는 연산이다.
size	큐에 저장되어 있는 자료의 개수를 알아보는 연산이다.

 

3. Deque(Double-ended queue)

- 양 끝에서 자료를 넣고 양 끝에서 뺄 수 있는 자료구조이다.

- 덱을 통해 스택과 큐를 구현할 수 있다.

연산	설명
push_front	덱의 앞에 자료를 넣는 연산이다.
push_back	덱의 뒤에 자료를 넣는 연산이다.
pop_front	덱의 앞에서 자료를 빼는 연산이다.
pop_back	덱의 뒤에서 자료를 빼는 연산이다.
front	덱의 가장 앞에 있는 자료를 보는 연산이다.
back	덱의 가장 뒤에 있는 자료를 보는 연산이다.

 

참고

- 『알고리즘 기초 1/2』