Queue & Stack

Queue란?

 

특징

- Queue의 사전적 의미는 줄, 혹은 줄을 서서 기다리는 것을 의미한다.

- 선입선출(FIFO - First In First Out) 의 자료구조이다. → 먼저 넣은 데이터가 먼저 나온다.

- 그러므로, 순서대로 처리해야할 때 사용한다. 

- 데이터를 추가하는 Enqueue / 데이터를 추출하는 Dequeue 연산이 있다. 

• Enqueue - 맨 뒤에 데이터를 추가하면 되기 때문에 O(1)이다. (rear포인터 이용)
• Dequeue - 맨 앞의 데이터를 삭제하면 되기 때문에 O(1)이다. (front포인터 이용)
  • 큐의 가장 첫번째 데이터를 front / 가장 마지막 데이터를 rear로 가리킨다.
  • 접근방법은 front/rear로만 가능하다.

- 활용 예시로는 하나의 자원을 공유하는 프린터나,은행 업무,콜센터 고객 대기시간,프로세스 관리, Cache구현, 너비우선탐색(BFS) 등이 있다.

 

 

 

구현방식

- Array Based : 고정된 크기의 배열로 남는 메모리가 생긴다.  

※ 이러한 단점을 보안하기 위해서? → 원형큐(circular queue)로 구현하는 것이 일반적이다. 

- List Based : 재할당이나 메모리 낭비의 걱정을 할 필요가 없어진다. 

 

 

원형큐(Circular Queue)란?

 

 

※ 우선순위 큐(priority queue)

- 일반적인 큐와 다르게 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옴

- 우선순위 큐는 일반적으로 Heap으로 구현

• Push - O(logn)
• Pop - O(logn)

 

힙(Heap)이란?

 

 

 

Stack이란?

 

특징

- 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 

- 후입선출(LIFO - Last In First Out) 의 자료구조이다. → 가장 나중에 추가한 데이터가 가장 먼저 나온다. 

- 재귀적이인 특징이 있다. 

- 데이터를 추가하는 Push / 데이터를 추출하는 Pop 연산이 있다. 

• Push - 맨 뒤에 데이터를 추가하면 되기 때문에 O(1)이다.
• Pop - 맨 뒤의 데이터를 삭제하면 되기 때문에 O(1)이다.

- 새로운 데이터는 top이 가리키는 데이터의 위에 쌓이게 된다. 데이터를 삭제할 때도 top을 통해서만 가능하다. 

- 활용 예시로는 call stack, 후위 표기법 연산, 괄호 유효성 검사,역순 문자열 만들기, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있다. 

 

 

---

 

 

스택(Stack) 두 개로 큐(Queue) 구현하기

큐(Queue) 두 개로 스택(Stack) 구현하기