큐 스택

스택(stack)

스택

스택은 가장 마지막에 저장된 데이터가 가장 먼저 삭제되는 후입선출(LIFO, Last In First Out) 구조이다.
스택은 한쪽 방향에서만 삽입과 삭제가 가능하다.
 

스택 용어

 

• top(peek): 가장 최근에 저장된 데이터이자 먼저 삭제될 데이터이다. 그림상 에서 요소 4가 해당
• push: 데이터를 삽입하는 것을 말하며 삽입된 데이터는 삭제 시 가장 먼저 삭제될 데이터가 됨
• pop : 데이터를 삭제할 때 사용하며 가장 최근에 저장된 데이터가 삭제됨
• empty : 스택이 비어있으면 true, 아니면 false를 반환함
• size : 스택에 저장된 데이터의 개수를 반환함

 
 

사용되는 예

• 브라우저의 뒤로 가기
• 실행 취소 (Ctrl +Z)
• 재귀함수
• 역순 문자열(문자열 거꾸로 뒤집기)

 
 
스택의 자료구조는 삽입과 삭제 시에 O(1), 탐색에는 O(n)의 시간복잡도를 가지게 됨

---

큐(Queue)

---

 

선형 큐

큐는 데이터 삽입, 다른 한쪽에서는 데이터의 삭제만 가능한 선입선출(FIFO, First In First Out) 구조를 가지고 있음.
 
실생활에서는 재료의 선입선출(유통기한이 오래된 것을 가장 앞쪽으로 배치), 식당의 줄서기등이 대표적인 예이다.
 
 

큐 용어

• Enqueue: (push)데이터 삽입
• Dequeue :  (JS의 shift,  pop): 데이터 삭제
• Front: Dequeue시 삭제되는 데이터 (가장 먼저 저장된 데이터)를 가리킵니다.
• back : 큐의 맨 뒤 데이터를 참조함
• empty : 큐가 비어있으면 true, 아니면 false를 반환함
• size : 큐에 저장된 데이터의 개수를 반환합니다
• Rear: 추가될 새로운 요소의 위치를 가리킵니다.

 

사용되는 예

• BFS 알고리즘
• 프로세스 관리(JS의 콜백 큐)
• 프린터의 대기열

큐에는 우선순위 큐, 원형 큐라는 2종류에 큐가 더 존재한다.
 

우선순위 큐(Priority Queue)

우선순위 큐

우선순위 큐의 각 요소는 값과 우선순위, 총 2개의 데이터를 가지고 있습니다.
따라서 선형큐와는 달리 우선순위가 높은 요소일수록 먼저 삭제되는 특징을 가짐
우선순위가 같은 데이터일 경우 삽입순서를 따른다.
 
삽입 및 삭제 시 우선순위에 따라 요소들을 정렬해야 하기 때문에 주로 힙(Heap)이라는 자료구조로 구현됨
실생활에서 병원의 응급실에서는 응급 환자가 우선순위가 높으므로 먼저 진료를 받고 일반 환자는 순서가 뒤로 밀리는 것과 같음
 
 

원형 큐 (=Circular Queue, Ring Buffer)

원형 큐

http:// https://www.geeksforgeeks.org/
 
원형 큐는 선형 큐의 단점을 보완하기 위해 만들어짐
 
큐는 사이즈가 고정되어 있고 데이터의 삽입과 삭제 시 나머지 요소들은 이동하지 않는다.
따라서 데이터의 삽입과 삭제가 반복되면 언젠가 Rear는 큐의 마지막 인덱스를 가리키게 됨
이전에 삭제 작업을 진행 앞에 빈 공간을 활용하지 못함 따라서 선형 큐는 빈공간을 활용하기 위해 현재 요소들을 앞을 재배치하는 별도의 작업이 필요
 

하지만 원형큐의 경우 Front와 Rear가 아래 그림처럼 순환하기 때문에 빈 공간을 사용하기 위한 별도 작업이 없음.

Front와 Rear의 움직임이 계속해서 돌고 있는 모습을 띤다.
 
 

덱(Deque, Double-ended Queue)

덱

덱은 큐 2개를 겹쳐놓은 것과 같기 때문에 Double ended Queue라고 부르며 Deque이라고 축약하여 부르기도 함
 
이 자료구조는 이름처럼 양쪽에서 데이터의 입, 출력이 모두 가능한 자료구조이다. 
스택 큐와 마찬가지로 front와 rear라는 포인터가 있으며 이들은 각각 가장 앞, 뒤에 있는 데이터를 가리킴
 
다만 스택과 큐의 Rear는 다음 요소가 삽입될 위치를 가리키는 반면 덱의 Rear는 마지막 요소를 가리키게 됨
 
 
스택, 큐와 같이 데이터의 삽입과 삭제에 O(1)의 시간 복잡도를 가진다.