스택(Stack)과 큐(Queue)

1. 스택(Stack)

 

스택(Stack)은 먼저 들어간 요소가 가장 나중에 나오게 되는 선입후출의 구조를 가진 선형 자료구조이다.

이러한 스택의 구조적 특징을 LIFO(Last In First Out)이라고 한다.

 

스택의 대표적인 연산으로는 push(), peek(), pop()이 있다. 스택을 구현하기 위해서는 배열 / 연결리스트 사용이 가능하며, 주로 배열을 통해 구현된다. 일반적인 스택은 메모리의 크기가 정적이지만, 동적 배열을 이용하여 동적 스택을 만들 수도 있다.

 

스택 자료구조는 주로 웹 브라우저 방문기록(뒤로가기), 후위 표기법 계산, 문자열 뒤집기, 재귀 등에 사용되며, 거의 모든 애플리케이션을 만들 때 사용된다.

 

 

 

 

2. 큐(Queue)

큐(Queue)는 먼저 들어간 요소가 가장 먼저 나오게 되는 선입선출의 구조를 가진 선형 자료구조이다.

이러한 큐의 선입선출의 구조적 특징을 FIFO(First In First OUt)이라고 한다..

 

큐의 대표적인 연산으로는 enqueue(), dequeue()가 있다. 큐를 구현하기 위해는 배열 / 연결리스트 사용이 가능하며, 주로 연결리스트를 통해 구현된다.

 

큐 자료구조는 주로 BFS 알고리즘, 프린터 큐, 프로세스 스케줄링 등에 사용된다.

 

 

큐 자료구조는 더 확장하여 덱(Deque, double-ended queue), 원형 큐(Circular Queue), 우선순위 큐(Priority Queue) 등의 자료구조를 만든다.

 

덱(Deque, double-ended queue)은 스택과 큐의 장점을 살린 것으로, front와 rear 모두에서 요소를 넣고 뺄 수 있는 자료구조이다. 일반적으로 양방향 연결 리스트를 이용하여 구현한다.

 

원형 큐(Circular Queue)는 최초에 할당받았던 공간을 재활용하여 메모리를 효율적으로 사용하기 위해 만들어진 큐이다.

 

우선순위 큐(Priority Queue)는 큐 내부의 원소 중 가장 우선순위가 가장 높은 요소부터 빠져 나오는 큐이다.

배열, 연결 리스트, 힙을 사용하여 구현할 수 있는데, O(n)의 시간복잡도를 가지는 다른 자료구조들과는 달리, O(logn)의 시간복잡도를 가지는 힙을 주로 사용한다.

 

 

 

 High Level

Q. 스택이 비어있을 때 pop을 하면 ___가 발생한다.

=> Underflow / 객체를 통해 추상화된 함수를 통한 접근이기 때문

 

Q. 스택이 꽉 차있을 때 push를 하면 ___가 발생한다.

=> Overflow / 객체를 통해 추상화된 함수를 통한 접근이기 때문

 

Q. array로 구현된 스택은 컴파일 타임에 capacity가 결정되는가?

=> O / 런타임에 스택의 용량이 동적으로 변할 수 있는 dynamic stack과 달리 컴파일 때부터 capacity가 결정되어 변하지 않는다.

 

Q. array로 구현된 스택은 dynamic stack에 비해 push / pop이 빠른가?

=> O / 동적으로 메모리를 할당받을 필요가 없고 구조가 더 단순하므로 push/pop 오버헤드가 더 작다.

 

Q. circular queue를 배열로 구현할 때 삽입 시 마지막 (rear) 인덱스를 어떻게 갱신시키는가?

=> (rear + 1) % CAPACITY / 삽입이므로 인덱스를 증가시켜야해서 1을 우선 더한다. 더해서 배열의 크기(capacity)를 넘어섰다면 인덱스 0부터 다시 증가되도록 해야하므로 모듈러 연산을 추가적으로 해준다.