[자료구조] 스택, 큐, 덱 (Stack, Queue, Deque)

스택(stack)

• 리스트의 한쪽 끝으로만 자료의 삽입/삭제가 이루어지는 자료 구조
• 후입선출(LIFO) 방식: push(), pop()
• 깊이 우선 탐색(DFS)에서 사용
• 용도:
  함수의 콜 스택
  후위 표기법으로 표현된 산술식 연산
  재귀 프로그램의 순서 제어 등

 

큐 (queue)

• 선형 리스트의 한쪽에서는 삽입이, 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조
• 선입선출(FIFO) 방식: push(), get()
• Front 포인터: 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터. 삭제 작업에 사용
• Rear 포인터: 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터. 삽입 작업에 사용
• 용도:
  컴퓨터 버퍼에서 주로 사용(작업 대기 행렬을 버퍼(큐)로 만들어 처리)
  운영체제의 작업 스케쥴링 등

 

덱 (deque)

• 리스트의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 자료구조 (Double Ended Queue)
• Scroll: 입력 제한 덱 (입력이 한쪽에서만 발생하고, 출력은 양쪽에서 일어날 수 있음)
• Shelf: 출력 제한 덱 (입력은 양쪽에서 일어나고, 출력은 한쪽에서 일어나도록 제한)
• 용도:
  스케쥴링(스케쥴링이 복잡할수록 스택, 큐보다 덱의 효율이 높을 경우가 있음)
  우선순위 조절 (한 방향으로만 삽입/삭제가 가능한 스택/큐와 달리 양방향으로 삽입/삭제가 가능하기 때문)

 

References:

https://jeong-pro.tistory.com/97
http://itnovice1.blogspot.com/2019/01/blog-post.html