[자료구조] 스택(Stack) ,큐(Queue) , 우선순위 큐(Priority Queue)

Stack : 가장 나중에 입력 된 자료가 가장 먼저 출력되는 자료구조(Last In First Out)

• 스택은 데이터를 일시적으로 쌓아 놓은 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)이다.
• 스택에 데이터를 넣는 작업을 push라 하고 스택에서 데이터를 꺼내는 작업을 pop이라고 한다.
• 스택은 push와 pop이 일어나는 곳이 한 군데 인데 이곳을 top 이라고 한다.
• 맨 아래 가장 먼저 push한 원소가 있는 곳을 bottom이라고 한다. 

• push: 스택의 맨 위에 새로운 요소를 추가
• pop: 스택의 맨 위에 있는 요소를 제거하고 반환
• peek: 스택의 맨 위에 있는 요소를 제거하지 않고 반환
• isEmpty: 스택이 비어 있는지 확인

package ch03_stack;

import java.util.Scanner;

public class IntStack {
	private int[] stk;
	private int capacity;
	private int ptr;
	
	public class EmptyIntStackException extends RuntimeException{
		public EmptyIntStackException() {}
	}
	
	public class OverflowIntStackException extends RuntimeException{
		public OverflowIntStackException() {}
	}
	
	public IntStack(int maxlen){
		ptr = 0;
		capacity = maxlen;
		try {
			stk = new int[capacity];
		} catch (OutOfMemoryError e) {
			capacity = 0;
		}
	}
	public int push(int x) throws OverflowIntStackException{		// stack의 데이터 삽입
		if(ptr >= capacity) throw new OverflowIntStackException();
		return stk[ptr++] = x;
	}
	
	public int pop() throws EmptyIntStackException{			// stack의 꼭대기 데이터 제거
		if(ptr <= 0 ) throw new EmptyIntStackException();
		return stk[--ptr];
	}
	
	public int peek() throws EmptyIntStackException{		// stack의 꼭대기에 있는 데이터를 보여주는 메서드
		if(ptr <= 0 )
			throw new EmptyIntStackException();
		return stk[ptr-1];
	}
	public void clear() {									// stack의 모든 데이터 제거
		ptr = 0 ;
	}
	public int indexOf(int x) {
		for (int i = ptr - 1; i >= 0 ; i--) {
			if(stk[i] == x)
				return i;
		}
		return -1;
	}
	public int getCapacity() {
		return capacity;
	}
	public int size() {
		return ptr;
	}
	public boolean isEmpty() {
		return ptr <= 0;
	}
	
	public boolean isFull() {
		return ptr >= capacity;
	}
	public void dump() { 
		if(ptr <= 0) {
			System.out.println("스택이 비어 있습니다");
		}
		else {
			for (int i = 0; i < ptr; i++) {
				System.out.println(stk[i]+ " ");
			}
			System.out.println();
		}
	}
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		IntStack s = new IntStack(64);
		
		while(true) {
			System.out.println();
			System.out.println("현재 데이터 개수" + s.size() / s.getCapacity());
			System.out.print("(1)푸시 (2)팝 (3)피크 (4)덤프 (5)종료:");
			
			int menu = scn.nextInt();
			if(menu == 0) break;
			
			int x;
			switch(menu) {
			case 1 :
				System.out.println("데이터 : ");
				x = scn.nextInt();
				try {
					s.push(x);
				} catch (IntStack.OverflowIntStackException e) {
					System.out.println("스택이 가득 찼습니다.");
				}
				break;
			case 2 :
				try {
					x = s.pop();
					System.out.println("팝한 데이터는" + x + "입니다");
				} catch (IntStack.EmptyIntStackException e) {
					System.out.println("스택이 비어있습니다.");
				}
				break;
				
			case 3 :
				try {
					x= s.peek();
					System.out.println("피크한 데이터는" + x + "입니다");
				} catch (IntStack.EmptyIntStackException e) {
					System.out.println("스택이 비어 있습니다.");
				}
				break;
			case 4 :
				s.dump();
				break;
			}
		}
		

	}

}

Queue : 가장 먼저 입력된 자료가 가장 먼저 출력되는 자료 구조(First In First Out)

• 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두는 기본 자료구조이다.
• 스택과 다른점은 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO) 구조이다.
• 큐에 데이터를 넣는 과정을 enqueue라 하고 큐에 데이터를 꺼내는 작업을 dequeue라고 한다.
• 데이터가 나오는 곳을 front , 데이터가 삽입되는 쪽을 rear라고 한다. 

 

활용 예시

• 프린터 대기열: 먼저 요청된 인쇄 작업부터 차례대로 처리
• 프로세스 스케줄링
• 데이터 스트림 처리

package ch04_queue;

import java.util.Scanner;

public class IntQueue {
	private int[] que;
	private int capacity;
	private int front;
	private int rear;
	private int num;
	
	public class EmptyIntQueueException extends RuntimeException{
		public EmptyIntQueueException() {}
	}
	public class OverflowIntQueueException extends RuntimeException{
		public OverflowIntQueueException() {}
	}
	
	public IntQueue(int maxlen) {
		num = front = rear = 0;
		capacity = maxlen;
		try {
			que = new int[capacity];
		} catch (OutOfMemoryError e) {
			capacity = 0;
		}
	}
	public int enque(int x) throws OverflowIntQueueException{		// rear에 데이터 삽입
		if(num >= capacity)
			throw new OverflowIntQueueException();
		que[rear++] = x;
		num++;
		if(rear == capacity)						// rear의 index가 capacity와 같다면 rear = 0
			rear = 0;
		
		return x;
	}
	public int deque() throws EmptyIntQueueException{				// front에 데이터 삽입
		if(num <= 0)
			throw new EmptyIntQueueException();
		int x = que[front++];
		num--;
		
		if(front == capacity)						// front의 index가 capacity와 같다면 front = 0
			front = 0;
		return x;
	}
	public int peek() throws EmptyIntQueueException{
		if(num < 0) 
			throw new EmptyIntQueueException();
		return que[front];
	}
	
	public void clear() {
		num = front = rear = 0;
	}
	public int indexOf(int x) {
		for (int i = 0; i < num; i++) {
			int idx = (i + front) % capacity;
			if(que[idx] == x)
				return idx;
		}
		return -1;
	}
	public int getCapacity() {
		return capacity;
	}
	public int size() {
		return num;
	}
	public boolean isEmpty() {
		return num <= 0;
	}
	public boolean isFull() {
		return num >= capacity;
	}
	public void dump() {
		if(num <= 0) 
			System.out.println("큐가 비어있습니다.");
		else
			for (int i = 0; i < num; i++) 
				System.out.println(que[(i+front) % capacity] + " ");
			System.out.println();
	}
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		IntQueue s = new IntQueue(64);
		while(true) {
			System.out.println();
			System.out.println("현재 데이터 개수 : " + s.size() + "/"+s.getCapacity());
			System.out.println("(1) 인큐 (2) 디큐 (3) 피크 (4) 덤프 (5) 종료");
			
			int menu = scn.nextInt();
			if(menu == 0) break;
			
			int x;
			switch (menu) {
			case 1: 
				System.out.print("데이터 : ");
				x = scn.nextInt();
				try {
					s.enque(x);
				} catch (IntQueue.OverflowIntQueueException e) {
					System.out.println("큐가 가득 찼습니다.");
				}
				break;
			case 2: 
				try {
					x =s.deque();
					System.out.println("디큐한 데이터는 : " + x + "입니다");
				} catch (IntQueue.EmptyIntQueueException e) {
					System.out.println("큐가 비어 있습니다.");
				}
				break;
				
			case 3: 
				try {
					x = s.peek();
					System.out.println("피크한 데이터는 : " + x + "입니다");
				} catch (IntQueue.EmptyIntQueueException e) {
					System.out.println("큐가 비어 있습니다.");
				}
				break;
			case 4 :
				s.dump();
				break;
			}
		}
	}
}

※ Deque

• 큐와 아주 유사하지만 양쪽 끝단에서 모두 입/출력이 가능한 자료구조
• 앞쪽에 삽입할 수 있고(Push front) , 뒤에 삽입할 수 있다(Push back)
• 앞쪽에서 삭제 할 수 있고(pop front) , 뒤 쪽에서 삭제할 수 있다.(pop back)
• 양방향 탐색이 필요한 알고리즘에서 주로 사용한다.

Priority Queue : Heap으로 이루어진 완전이진트리(Complete Binary Tree)

• 우선 순위 큐는 데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리 , 데이터 추가는 어떤 순서로 해도 상관이 없지만 제거 될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조이다.
• 최대 힙(Max Heap)은 부모 노드가 자식 노드보다 항상 크거나 같고 최소 힙(Min Heap)은 부모 노드가 자식노드봏다 항상 작거나 같다.

힙 트리의 루트 노드에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데 , 전자 최대힙 , 후자는 최소힙이라 한다. java에서 Priority Queue를 사용하려면 java.util.PriorityQueue를 import해야 한다.

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

• python에서 priority queue를 사용하려면 heapq 모듈을 import 하면 된다. heapq 모듈에는 python의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와 준다. 
• 처음에 stack 처럼 빈 리스트를 생성해 놓은 다음 heapq 모듈의 함수를 호출 할 때 마다 이 리스트를 인자로 넘겨야 한다.  heapq.heappush(리스트 , 원소) 함수를 이용하여 최소 힙에 원소를 추가할 수 있다. 첫번째 인자는 원소를 추가할 대상 리스트이며 두번째 인자는 추가할 원소를 넘긴다.
• heapq.heappop(리스트)을 사용하면 힙에서 원소를 삭제 할 수 있다. 가장 작은 원소를 삭제 후 그 값을 리턴 한다.

import heapq

min_heap = []                   # 최소 힙
heapq.heappush(min_heap,5)
heapq.heappush(min_heap,1)
heapq.heappush(min_heap,3)
print(heapq.heappop(min_heap))              

max_heap = []                   # 최대 힙
heapq.heappush(max_heap,-5)
heapq.heappush(max_heap,-1)
heapq.heappush(max_heap,-3)
print(-heapq.heappop(max_heap))

• heapq는 기본적으로 최소 힙을 지원한다.
• 하지만 문제에서 최대 힙을 구현해야 될 상황이 있다. 그럴 때는 다음과 같이 부호를 변경하는 방법을 사용해서 최대 힙을 구현한다.
• heappush를 할 때 부호를 바꿔서 최소 힙에 넣어 준 뒤에 최솟 값으로 부터 heappop을 할때 다시 부호를 바꿔주면 최대 힙을 구현 할 수 있다.
• 힙은 각 노드가 하위 노드보다 큰 우선순위를 가진다
• 우선순위 큐는 삽입 순서에 상관없이 우선순위(최대,최소)높은 데이터가 먼저 나가는 형태의 자료구조이다
• 리스트에 원소를 넣으면 자동으로 정렬되어야 하는 알고리즘에 사용한다.

ex) baekjoon - 11279

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

import heapq
import sys
input = sys.stdin.readline
h = []
for _ in range(int(input())) :
  x = int(input())
  if x == 0 :
    if len(h) == 0 :
      print(0)
    else :
      y = -heapq.heappop(h)
      print(y)
  elif x > 0 :
    heapq.heappush(h,x*(-1))

 

ex ) baekjoon - 1715 

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

import heapq
import sys

N = int(input())
card_deck = []
for _ in range(N) :
  heapq.heappush(card_deck, int(sys.stdin.readline()))

if len(card_deck) == 1 :
  print(0)
else :
  cnt = 0
  while len(card_deck) > 1 :
    min_val_1 = heapq.heappop(card_deck)
    min_val_2 = heapq.heappop(card_deck)
    cnt += min_val_1 + min_val_2
    heapq.heappush(card_deck,min_val_1+min_val_2)
  print(cnt)

• heap은 최댓값과 최솟값을 쉽게 찾을 수 있는 자료구조를 제공한다.
• heap 자료구조를 사용하면 O(log n)의 시간 복잡도를 가질 수 있다. 
• 리스트의 sort() 함수가 O(nlog n)의 시간 복잡도를 가진것에 비해 매우 빠르게 리스트를 정렬하고 원하는 원소를 출력할 수 있다.

heap 함수	설명
heapq.heappush(heap,item)	item을 heap에 추가
heapq.heappop(heap)	heap에 가장 작은 원소를 리턴, 비어있는 경우 indexError가 호출 된다.
heapq,heapify(x)	리스트 x를 즉각적으로 heap으로 변환해준다.

https://school.programmers.co.kr/learn/courses/30/lessons/42626#

프로그래머스