[선형 구조] 스택과 큐

스택 Stack
나중에 들어간 원소가 먼저 나오는 후입선출, Last In First Out(LIFO)의 선형 자료구조입니다.
접시처럼 차곡차곡 쌓이는 구조로 데이터를 삽입하면 Top에 위치하며, Pop 연산을 할 때 Top에 위치한 데이터가 빠져 나옵니다.
데이터의 삽입/삭제는 O(1)의 시간복잡도가 소요됩니다.

Stack의 삽입/삭제

• 스택의 활용

1. 웹 브라우저 방문기록(뒤로가기): 가장 나중에 열린 페이지부터 다시 보여줌
2. 연산자 후위 표기법 계산
3. 수식의 괄호 검사: 연산자 우선순위 표현을 위한 괄호 검사
4. 프로그램에서의 시스템 스택
5. 실행 취소(Undo): 가장 나중에 실행된 것부터 실행을 취소함
6. 역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력
7. 안드로이드의 액티비티: 사용자의 동작으로 인해 새로운 화면이 띄워지면 Push 연산으로 스택에 쌓고, 뒤로가기를 누르면 가장 나중에 띄운 화면부터 차례대로 Pop 연산으로 돌아감

---

큐 Queue
먼저 들어간 원소가 먼저 나오는 선입선출 First In First Out(FIFO)의 선형 자료구조입니다.
티켓을 사기 위해 줄을 서서 먼저 온 순서대로 티켓을 구매하는 것처럼 데이터가 삽입된 순서대로 빠져나옵니다.
큐의 가장 앞에 있는 원소는 front, 가장 뒤에 있는 원소는 rear/back으로 표현합니다.
데이터를 삽입하는 enqueue/push 연산을 하면 데이터가 맨 뒤로 들어갑니다.
데이터를 삭제하는 dequeue/pop 연산을 하면 맨 앞의 데이터가 빠져나옵니다.
데이터의 삽입/삭제는 O(1)이 소요됩니다.

Queue의 삽입 삭제

 

• 선형 큐 Linear Queue

Linear Queue

기본적으로 선형 큐는 배열을 기반으로 구현됩니다.

따라서 삽입시에 Rear이 가리키는 index가 증가하며, 삭제시에는 Front가 가리키는 index가 증가합니다.

Linear Queue의 단점

Rear가 배열의 끝을 가리키면 큐가 꽉 차있다고 판단하며, 실제로 앞부분의 메모리가 비어있더라도 활용할 수 없다는 단점이 존재합니다.

즉, 삭제 후 빈 공간이 생기더라도 데이터를 추가할 수 없어 메모리 낭비가 발생합니다.

이러한 단점을 개선하기 위해서 빈자리가 생길 때마다 나머지 요소들을 앞으로 한 칸씩 땡겨주는 shift 연산을 추가할 수 있지만, 이는 시간 복잡도 O(n)이 소요됩니다.

 

이를 개선하기 위해 원형 큐가 생겼습니다.

 

 

• 원형 큐 Circular Queue

Front와 Rear를 연결하여 논리적으로 원형으로 되어 있어 원형 큐라고 합니다.

Front와 Rear가 연결되어 있기 때문에, 배열의 끝에 데이터가 채워지더라도 배열의 시작으로 돌아올 수 있어 선형 큐의 단점을 보완합니다.

큐가 비어있는 상태라면 Front = Rear = -1로 같은 지점에서 시작하며, 삽입이 될때마다 Rear가 가리키는 index가 한 칸씩 바뀌는 것은 선형 큐와 동일합니다.

 

하지만 다음 인덱스는 모듈러 연산을 통해 ((Rear + 1) % 배열 사이즈)로 바꿔줌으로써 빈 곳에 데이터를 다시 삽입하는 것이 가능합니다.

즉, 선형 큐의 단점이었던 메모리 낭비가 원형 큐에서는 발생하지 않습니다.

Shift 연산의 비용이 들지 않기 때문에 O(1)로 데이터 삽입/삭제가 가능합니다.

 

또한, 원형 큐는 공백과 포화 상태를 구분하기 위해 자리 하나는 항상 비워둔다는 특징이 있습니다.

 

 

• 큐의 활용

1. 프린터의 인쇄 대기열: 우선순위가 같은 작업을 예약한 순서대로 처리함
2. 선입선출이 필요한 대기열: 은행 업무, 티켓카운터, 콜센터 고객 대기시간
3. 윈도우 시스템의 메시지 처리기
4. 프로세스 관리
5. 너비 우선 탐색(BFS) 구현
6. 캐시 구현, 버퍼, 인쇄 작업, 실시간 비디오 스트리밍: 스트리밍에서 다운로드 된 데이터가 비디오를 재생하기에 충분하지 않으면 큐에 순서대로 모아 두었다가 충분한 양이 되면 비디오를 복원해서 재생함

---

참고

• https://slideplayer.com/slide/4151401/

Queues Objectives: Describe a queue - ppt video online download