2. Queue & Stack

Queue

Queue는 한글로 번역하면 줄이라는 뜻인데 줄을 서는 원리와 똑같이 동작하기 때문이다.

먼저 들어간 element가 먼저 나오는, First In First Out (FIFO) 형태를 갖는 자료구조이다.

 

따라서 index에 따라 넣고 빼는 것이 아닌 맨 뒤에 넣거나(enqueue), 맨 앞에서 빼는(dequeue) 것만 가능하다.

 

 

Enqueue

위와 같이 리스트 형태로 구현된 queue가 있을 때, enqueue를 통해 노드를 추가하고 싶다면

 

 

추가할 새 노드를 만들어 준 뒤

 

 

맨 뒤 노드의 포인터를 새 노드로 지정해주면 된다.

 

이 때 마지막 노드의 포인터(tail)를 따로 저장해두지 않으면 처음부터 끝까지 탐색해야 하므로 미리 저장해두어야 한다.

 

따라서 언제나 위와 같이 상수 시간이 걸리므로 시간복잡도는 O(1)이다.

 

 

Dequeue

마찬가지로 리스트로 구현된 다음과 같은 큐에서 첫번째 노드를 빼고 싶다면

 

맨 앞의 노드를 없애고 head를 다음 노드로 옮겨주면 된다.

 

따라서 언제나 상수 시간이 걸리므로 dequeue 또한 시간복잡도는 O(1)이다.

 

 

 

Stack

Stack은 쌓는다는 뜻을 갖고 있는데 물건을 쌓는 원리와 같이 동작한다.

가장 마지막에 삽입된 element가 먼저 나오는 Last In First Out (LIFO) 형태를 갖는 자료구조이다.

 

따라서 맨 위에 element를 삽입하는 push, 맨 위 element를 빼는 pop 만 가능하다.

 

 

Push

위와 같이 리스트로 구현된 스택이 있을 때 맨 앞에 새로운 노드를 추가하고 싶다면

(왼쪽이 스택의 위쪽, 오른쪽이 스택의 아래쪽이라고 생각하면 된다)

 

 

추가할 노드를 생성하고

 

 

새 노드의 포인터를 head로 설정해준 뒤,

 

 

head를 새 노드로 옮겨주면 된다.

 

따라서 언제나 상수 시간에 처리가 가능하므로 push의 시간복잡도는 O(1)이다.

 

 

Pop

위와 같은 형태에서 맨 앞의 노드를 제거하고 싶다면

 

 

맨 앞의 노드를 없애고

 

 

head를 다음 노드로 설정해주면 된다.

 

따라서 상수 시간 안에 가능하므로 pop 또한 시간복잡도는 O(1)이다.

 

 

 

Summary

Queue는 FIFO(First In First Out) 구조를 가지며 dequeue, enqueue 모두 O(1)의 시간복잡도를 갖는다.

Stack은 LIFO(Last In First Out) 구조를 가지며 push, pop 모두 O(1)의 시간복잡도를 갖는다.

 

삽입과 삭제 모두 상수 시간 안에 처리 가능하므로 필요한 알고리즘에 맞춰 사용하면 효율적인 구현이 가능하다.