[자료 구조] Stack, Queue, Priority Queue

Stack

스택(stack)은 데이터를 입력된 순서대로 쌓고, 나중에 들어온 데이터부터 먼저 꺼내 사용하는 자료 구조이다.

스택의 특징

• 맨 마지막에 들어온 데이터가 가장 먼저 스택에서 제거되는 LIFO(Last in First Out) 원리가 작용한다.
• 요소의 삽입/제거가 'top'이라는 한 쪽 끝에서 일어난다.
• 스택에서 삽입 연산은 push, 제거 연산은 pop이라고 부른다. 또한 가장 마지막 위치에 있는 데이터를 읽는 것은 peek(top에 있는 데이터가 제거되지 않음)이라고 부른다.
• 삽입, 제거 연산은 top이라는 특정 위치에서 일어나기 때문에 시간 복잡도가 O(1)이고, 탐색 연산은 해당 데이터를 찾을 때까지 수행해야 하므로 평균적으로 O(n)의 시간 복잡도를 가진다.
• 스택은 dynamic array나 linked list를 사용하여 구현 가능하다.
• 스택은 recursive data structure를 가지고 있기 때문에 recursion에 기반한 문제 풀이에 사용된다.
  - Example: pre-order(root-left-right 순 탐색), post-order(left-right-root 순 탐색), in-order traversal(left-root-right 순 탐색) of the binary tree
• 스택은 임시로 사용되는 정보를 저장하는 메모리 영역에서 사용한다. (Stack Area: 지역 변수, 파라미터, 리턴값, 호출된 메소드 등이 저장되는 메모리 영역)

  스택은 대표적으로 프로그램을 수행할때 사용합니다.
  Main 프로그램에서 함수 A를 호출하면 Main 프로그램 위에 함수 A가 쌓이고, 함수 A의 수행 중에 함수 B가 호출되면, 함수 A위에 함수 B가 스택처럼 쌓이게 된다.
  함수 B의 실행이 완료되면 함수 A가 실행되고, 함수 A의 실행이 완료되면 주 프로그램의 실행이 시작됩니다 (LIFO)

JVM 메모리 영역

자바에서 배열로 스택 구현하기

import java.util.ArrayList;

class MyStack {
	private ArrayList<String> arrayStack = new ArrayList<String>();

	public void push(String data) {
		arrayStack.add(data);
	}

	public String pop() {
		int len = arrayStack.size();
		if (len == 0) {
			System.out.println("스택이 비었습니다.");
			return null;
		}
		return arrayStack.remove(len - 1);
	}

	public String peek() {
		int len = arrayStack.size();
		if (len == 0) {
			System.out.println("스택이 비었습니다.");
			return null;
		}
		return arrayStack.get(len - 1);
	}
}

Queue

큐(queue)는 데이터를 입력된 순서대로 쌓고, 처음 들어온 데이터부터 먼저 꺼내 사용하는 자료 구조이다.

큐의 특징

• 맨 처음에 들어온 데이터가 가장 먼저 스택에서 제거되는 FIFO(First in First Out) 원리가 작용한다.
• 요소의 삽입은 큐의 뒤쪽인 'Rear'에서, 제거는 큐의 앞쪽인 'Front'에서 일어난다. 즉, 삽입과 제거 연산이 작용하는 위치가 다르다.
• 큐에서 삽입 연산은 enqueue, 제거 연산은 dequeue라고 부른다.
• 삽입 연산은 front, 제거 연산은 rear이라는 특정 위치에서 일어나기 때문에 시간 복잡도가 O(1)이고, 탐색 연산은 해당 데이터를 찾을 때까지 수행해야 하므로 평균적으로 O(n)의 시간 복잡도를 가진다.
• 큐는 dynamic array나 linked list를 사용하여 구현 가능하다.
• 큐는 sequential data structure를 가지고 있기 때문에 sequential processing에 기반한 문제 풀이에 사용된다.
  - Example: Routers and switches, round-robin scheduling algorithm
• 큐는 프로세스 처리에서 사용하는 자료 구조이다.

  컴퓨터 안에 여러 개의 프로세스가 수행 중인데, 새로운 프로세스가 수행되어야 하는 경우 기존에 수행되던 프로세스 중에서 가장 먼저 메모리에 올라온 프로세스가 아웃되고(실행), 새로운 프로세스를 메모리에 올리게 됩니다. 이 경우에 운영체제는 현재 수행 중인 프로세소를 큐의 형태로 관리합니다.
  Windows 운영체제를 사용하는 컴퓨터에서 수행 중인 프로그램에 이벤트 (버튼 누르기, 윈도우 크기 조정, 메뉴 선택하기 등)가 발생하면 발생한 이벤트가 큐에 저장되고, 수행중인 프로그램이 큐에 저장된 것을 앞에서부터 읽어 와서 처리한다 (FIFO).

자바에서 배열로 큐 구현하기

class MyQueue {
	private ArrayList<String> arrayQueue = new ArrayList<String>();

	public void enQueue(String data) {
		arrayQueue.add(data);
	}

	public String deQueue() {
		int len = arrayQueue.size();

		if (len == 0) {
			System.out.println("큐가 비었습니다.");
			return null;
		}
		return arrayQueue.remove(0);
	}
}

스택 두 개로 큐 구현하기
스택1과 스택2로 큐를 구현해보자. 스택 두 개를 이용하여 아래와 같은 과정으로 큐를 구현할 수 있다.

1. 데이터가 들어올 때(enqueue) 스택1에 쌓아준다.
2. 데이터를 내보낼 때(dequeue) 스택2에 요소가 없다면 스택1의 요소를 pop()해서 스택2에 순서대로 쌓아준 후, 스택2에서 요소 하나를 pop()해서 내보낸다.
3. 데이터를 내보낼 때(dequeue) 스택2에 요소가 있다면 스택2에서 요소를 pop()해서 내보낸다.

스택 2개로 큐 구현하기

큐 두개로 스택 구현하기
큐1과 큐2로 스택을 구현해보자. 큐 두 개를 이용하여 아래와 같은 과정으로 스택을 구현할 수 있다.

1. 데이터가 들어올 때(push) 큐1에 데이터(1->2->3->4)를 넣는다.
2. 큐1의 데이터 중 마지막 데이터를 제외하고 모두 큐2로 이동시킨다.(1->2->3)
3. 다시 큐2에 있는 데이터를 큐1으로 이동시킨다.(1->2->3)
   (위 세 과정을 통해 큐1 데이터 순서는 4->1->2->3이 된다.)
4. 데이터를 내보낼 때(pop) 큐1에서 dequeue()해서 내보낸다.(4가 빠져나옴)

Priority Queue

우선순위 큐(priority queue)는 큐에 들어간 순서와는 상관 없이 우선순위가 높은 데이터가 먼저 큐에서 제거(사용)되는 것을 말한다. 우선순위 큐에서 모든 항목에는 우선순위가 있고, 우선순위가 높은 요소는 낮은 요소보다 큐에서 먼저 제거되며, 우선순위가 같은 경우에는 큐에 들어온 순서에 따라 제거 순서가 결정된다.

위 그림에서 숫자가 높을 수록 우선순위가 높고 input이 1, 3, 5, 11, 7, 9의 순서로 큐에 들어왔다고 가정하면 큐와 우선순위 큐의 dequeue 순서는 다음과 같이 정해진다.
queue: 1, 3, 5, 11, 7, 9
prioirty queue: 11, 9, 7, 5, 3, 1

우선순위 큐는 array, linked list, heap으로 구현할 수 있는데, 각 구현 방법에 따른 시간 복잡도는 아래와 같다.

힙 방식 구현으로는 최악의 경우라도 O(logn)을 보장하기 때문에 일반적으로 힙을 이용하여 우선순위 큐를 구현한다.

추가로 공부해야 할 내용

• Heap
• priority queue 코드 구현
• circular queue
• Deque(Double ended queue)

참고 링크
[Favtutor]Stack vs Queue
우선순위 큐(Prioirty Queue) 개념 및 구현