선형 구조 - 스택, 큐, 덱

---

스텍, 큐, 덱 이란?

• 데이터 값을 저장하는 기본적인 구조로 일차원의 선형(linear) 자료 구조 이다.
• (배열/리스트와 유사하게) 값을 저장하는 연산과 저장된 값을 거내는 연산이 제공 된다.
• 그러나, 매우 제한적인 규칙 (LIFO, FIFO) 등을 따른다.

스택(Stack) : LIFO - 후입 선출

• 스택은 가장 최근에 저장된 값 다음에 저장되며, 가장 최근에 저장된 값이 먼저 나간다.
  LIFO (Last In, First Out) 원칙

• top : 가장 최근에 스택에 삽입된 자료의 위치

• stack.push : top에 새로운 데이터 추가
• stack.pop : 가장 최근에 삽입된 데이터가 스택에서 삭제

• stack underflow : 스택이 비어있을 때, stack.pop을 시도하는 것
• stack overflow : 스택의 크기가 비어있을 때(스택이 꽉 차 있을때), stack.push를 시도하는 것

시간 복잡도

• top 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다.

장단점

• top을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.
• top위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능 하다.
  탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.

활용

• 재귀 알고리즘
• DFS 알고리즘
• 작업 실행 취소와 같은 역추적 작업이 필요할 때
• 괄호 검사, 후위 연산법, 문자역 역순 출력 등

큐(Queue) : FIFO - 선입 선출

• 큐는 가장 최근에 저장된 값, 다음에 저장되며, 가장 오래전에 저장된 값부터 나간다.
  FIFO (First In, First Out) 원칙 - 선착순

• rear : 데이터가 삽입되는 곳
• front : 데이터가 제거되는 곳

• 데이터 삭제하기 전에는 큐가 empty 한지, 큐에 데이터를 추가하려 할 때는 큐가 full 인지 확인 후 진행하여야 한다.

선형 큐 (Linear Queue)

• 선형 배열을 사용하여 구현된 큐
• 삽입을 위해서는 계속해서 요소들을 이동시켜야 함
  front, rear는 증가만 하는 방식, 실제로는 front 앞쪽에 공간이 있더라고 삽입할 수 없는 경우가 발생할 수 있음

원현 큐 (Circular Queue)

• 선형 큐의 단점을 보완
• front : 맨 첫번째 요소 바로 앞을 가리킴
• rear : 마지막 요소 가리킴

• 큐 공백(empty) 상태 : front == rear
• 큐 포화(full) 상태 : front == (rear + 1) % MAX_QUEUE_SIZE
• 공백 상태와 포화 상태를 구분하기 위해 하나의 공간을 비워 둠

시간 복잡도

• front, rear의 위치로 데이터 삽입 삭제가 바로 가능하기 때문에 데이터 삽입, 삭제의 시간 복잡도는 O(1) 이다.

장단점

• front, rear를 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.
• front, rear 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능 하다.
  탐색하려면 모든 데이터를 꺼내면서 진행해야 한다.

활용

• 데이터를 입력된 순서대로 처리해야 할 때
• BFS 알고리즘
• 프로세스 관리
• 대기 순서 관리

덱(Deque) : Double - Ended Queue

• 양쪽 front, rear에서 삽입 삭제가 모두 가능한 큐를 의미하는 자료구조 이다.
• 선언 이추 크기를 줄이거나 늘릴 수 있는 가변적 크기를 갖는다.
• 중간에 데이터가 삽입될 때 다른 요소들을 앞, 뒤로 밀 수 있다.

시간 복잡도

• 삽입 삭제 연산 - O(1)
• index를 통한 요소 탐색 - O(1)

장단점

• 데이터의 삽입 삭제가 빠르고 앞,뒤에서 삽입 삭제가 모두 가능하다
• 가변적 크기
• index를 통해 임의의 원소에 바로 접근이 가능하다
• 중간에서 삽입 삭제가 어렵다
• 스택, 큐에 비해 비교적 구현이 어렵다

활용

• 데이터를 앞, 뒤쪽에서 모두 삽입 삭제하는 과정이 필요한 경우
• 데이터의 크기가 가변적일 때