[자료구조] Queue와 Deque, Stack

모두 선형 자료구조

	Queue
	자료구조, FIFO
구현 클래스	Python : List, Queue, LifoQueue, PriorityQueue C : Circular array Java : LinkedList, PriorityQueue, ArrayBlockingQueue
Python	'queue' 모듈에서 제공 import queue data = queue.Queue()
Java	Collection 프레임워크의 인터페이스 import java.util.*; Queue<Integer> que = new LinkedList<Integer>();
특징	- 배열 기반: 고정 크기, 인덱스를 통해 데이터에 접근 - 연결 리스트 기반: 동적 크기 가능, 데이터 삽입과 삭제가 간편함 큐의 양끝에서 삽입·삭제가 각각 이루어짐
종류	1. 선형 큐(Linear Queue) - front와 rear가 증가만 하는 방식 (front 앞쪽에 공간이 있더라도 삽입할 수 없는 경우가 발생할 수 있음) 2. 원형 큐(Circular Queue) - 선형 큐의 단점을 보완 (공백 상태와 포화 상태를 구분하기 위해 하나의 공간을 비워둠) 3. 우선순위 큐(Priority Queue) - FIFO가 아닌 우선순위가 높은 순서대로 나감 (배열 또는 리스트를 이용해 구현 가능) ex. 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제의 테스크 스케쥴링
장점	연산 속도 빠름: 입출력 모두 O(1)
단점	- 멀티스레드 환경을 위한 모듈이기 때문에 매우 느림 - 중간에 위치한 데이터에 대한 접근 불가능
용도	주로 스레드 간의 통신을 위해 사용 ex. BFS

	Deque
	라이브러리, FIFO & LIFO
구현 클래스	Python : collections.deque Java : LinkedList, ArrayDeque
Python	'collections' 모듈에서 제공 from collections import deque q = deque()
Python에서 주요 함수	append() : deque의 right end에 요소 추가 appendleft() : deque의 left end에 요소 추가 pop() : deque의 right end의 요소 삭제 popleft() : deque의 left end의 요소 삭제
Java	'queue'를 상속받는 인터페이스 import java.util.*; Deque<Integer> deq = new Linkedlist<>();
장점	연산 속도 빠름 (양방향 입출력 모두 O(1))
단점	탐색이 불가능(모든 데이터를 꺼내면서 진행해야함)
용도	양방향 큐로 양끝에서 삽입·삭제 시 사용 ex. BFS

	Stack
	LIFO
구현 방법	list
Python	stack = [] top = -1
특징	top이 아닌 위치의 데이터에 대한 접근, 삽입, 삭제가 모두 불가능하다.
장점	연산 속도 빠름(입출력 모두 O(1))
단점	탐색이 불가능(모든 데이터를 꺼내면서 진행해야함)
용도	ex. DFS, 괄호 검사, 후위 연산법, 문자열 역순 출력

참고링크
[자료구조] 스택 Stack, 큐 Queue, 덱 Deque