[자료구조] Queue / Stack

구분	Stack	Queue
순서	LIFO (Last in First Out)	FIFO (First in, First Out)
연산	push(삽입), pop(삭제)	enqueue(삽입), dequeue(삭제)
활용 사례	함수 호출, 괄호 짝 맞추기, 후위 표기법 계산 등	프린터 대기열, 버퍼 관리, 스케줄링 알고리즘 등

Queue

First In, First Out 선입선출을 개념으로 하고 있는 자료 구조이다.

• Front : 맨 앞의 요소를 가리킨다.
• Rear : 맨 뒤의 요소를 가리킨다.
• Enqueue : 삽입 연산 (Rear 뒤에 요소를 삽입한다.)
• Dequeue : 삭제 연산 (Front 가 가리키고 있는 요소를 제거한다.)

C언어에서는 Queue를 구현하기 위해서 배열로 구현하는 모습이 종종 보인다.

이때 배열로 구현하면, Dequeue(삭제 연산)을 하면 고려해야 하는 점이 있다.

1. 모든 요소를 한 칸씩 앞으로 이동

   • 이동에 필요한 동작이 필요하므로, 불 필요한 시간 소모가 이루어짐

2. Front 포인터를 뒤로 이동

   • 한정된 배열의 크기가 제한 될 수 있음

그래서 나온 개념이 Circular Queue가 존재한다.

Circular Queue

원형 큐는 값을 이동 시킬 필요도 없고, 계속해서 저장할 공간을 재 할당할 필요가 없다.

포인터를 이용하여 Front와 Rear를 구분하고, 삽입과 삭제 연산이 가능하다.

• 삽입 연산 : 삽입 연산을 하면 Front는 앞으로 저장될 공간을 가리킴
• 삭제 연산 : Rear 포인터가 가리키는 곳을 읽고, 포인터를 이동시킴.

실제로 C언어에서 배열로 구현하는 방법은, `mod`를 이용하여 구하면 된다.

위 사진과 같이, 할당된 공간이 8이라면, index는 0 ~ 7일 것이다.

반복문을 돌다가, index가 8이 되었을 때, 0으로 다시 되돌아 가야하니 배열의 크기만큼 나누어 주면 Circular Queue가 구현이 가능하다.

Priority Queue

우선순위 큐는 Queue에 우선 순위의 개념을 도입한 것이다.

항상 FIFO를 보장하는 것이 아니라, 우선 순위가 높은 값을 Return한다.

• 구현 방법 : 배열, 연결 리스트, 힙

구현 방법이 여러가지가 있는데, 시간 복잡도 측면에서 가장 좋은 것은 Heap이다.

O(logN)으로 가장 좋다.

Stack

Queue와 반대로, LIFO (Last in, First Out) 의 구조를 가지고 있다.

Queue는 Front와 Rear 두개의 포인터가 있었는데, Stack top 하나만 필요하다.

• top은 가장 상위의 요소를 가리킨다.
• 삭제 연산(pop) : top 이 가리키는 요소를 삭제한다. top을 이전의 요소를 가리킨다.
• 삽입 연산(push) : top 다음 공간에 요소를 삽입한다. top은 삽입한 곳을 가리킨다.

그래서 Stack이 가장 많이 사용되는 곳이, 함수를 적재하고 호출하는 곳에 사용된다.

컴퓨터는 CPU와 메모리로 구성되어 있다.

아래 사진은 메모리 공간의 구성을 나타낸 그림인데, stack 부분이 있는 것이 보인다.

우리의 컴퓨터의 메모리는 고정되어 있고, Stack의 메모리도 고정되어 있다.

이 메모리를 초과하여 계속해서 데이터를 적재하려고 하면, StackOverFlow가 초래될 수도 있다.

Stack은 웹/앱에서 방문한 페이지를 기록하는 데에도 쓰인다. 이전 페이지로 이동해야 하므로

Python - Queue

---

Queue 클래스

Python에서 Queue 라이브러리도 지원한다.

Queue 클래스는 멀티스레딩 환경에서, 공유 자원에 대한 Locking도 지원하기에, 동시성 작업에 많이 사용되곤 한다.

>>> from queue import Queue
>>>
>>> que = Queue()
>>> que.put(4)
>>> que.put(5)
>>> que.put(6)
>>> que.get()
4
>>> que.get()
5
>>> que.get()
6

deque

deque는 양방향 삽입 삭제가 가능한 자료구조이다.

기존에는 .append 메소드가 오른쪽만 추가하는 것 이였다면,
deque는 .appendleft 명령어를 통해서 왼쪽에 삽입하는 것도 지원한다.

추가로 .popleft도 지원한다.

>>> from collections import deque
>>>
>>> queue = deque([4, 5, 6])
>>> queue.appendleft(3)
>>> queue.appendleft(2)
>>> queue
deque([2, 3, 4, 5, 6])
>>> queue.pop()
6
>>> queue.pop()
5
>>> queue
deque([2, 3, 4])

List

List도 두가지 명령어로 Queue 구현이 가능하다.

• 삽입 : .append(value)
• 삭제 : .pop(0)
  
  

Python - Stack

List

• top 확인 : list[-1]
• 삽입 : append(value)
• 삭제 : .pop()

Deque

양방향 삽입 삭제가 가능한 Deque로도 사용이 가능하다.

오른쪽 삽입, 오른쪽 삭제만 사용하면 Stack 사용이 가능하다.