스택과 큐는 배열에서 발전된 형태의 자료구조이며, 스택과 큐는 구조는 비슷하지만 처리 방식은 다릅니다.

스택과 큐의 핵심 이론

스택

스택(stack)은 삽입과 삭제 연산이 후입선출(LIFO: Last-in-First-out)로 이뤄지는 자료구조이다. 후입선출은 삽입과 삭제가 한쪽에서만 일어나는 특징이있다.

그림을 보면 새 값이 스택에 들어가면 top이 새 값을 가르킵니다. 스택에서 값을 빼낼 때 pop는 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 되는 것입니다. 그림에 여러 영어 표기가 있는데 이것은 스택 용어로서 한번 짚고 넘어가도록 하겠습니다.

스택 용어

• 위치
  • top
    • 삽입과 삭제가 일어나는 위치를 뜻한다.
• 연산
  • push
    • top 위치에 새로운 데이터를 삽입하는 연산이다.
  • pop
    • top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
  • peak
    • top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

스택은 깊이 우선 탐색(DFS: Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아두어야 합니다. 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문입니다.

큐

큐(queue)는 삽입과 삭제 연산이 선입선출(FIFO: First-in-First-out)로 이뤄지는 자료구조로, 스택과 다르게 먼저 들어온 데이터가 먼저 나갑니다. 그래서 삽입과 삭제가 양방향에서 이뤄진다는 특징이 있습니다.

그림을 보면 새 값 추가는 큐의 rear에서 이뤄지고, 삭제는 큐의 front에서 이뤄집니다. 큐 관련 용어 또한 한번 짚고 넘어가도록 하겠습니다.

큐 용어

• rear
  • 큐에서 가장 끝 데이터를 가리키는 영역이다.
  • 새로운 값이 들어가는 영역이다.
• front
  • 큐에서 가장 앞의 데이터를 가리키는 영역이다.
  • 데이터 삭제가이뤄지는 영역이다.
• add
  • rear 부분에 새로운 데이터를 삽입하는 연산이다.
• poll
  • front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
• peek
  • 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.

큐는 너비 우선 탐색(BFS: Breadth First Search)에서 자주 사용하므로 이 역시도 스택과 함께 잘 알아 두어야 하는 개념입니다.

우선순위 큐(Priority Queue)

우선순위 큐(priority queue)는 값이 들어간 순서와 상관 없이 우선 순위가 높은 데이터가 먼저 나오는 자료구조로, 큐 설정에 따라 front에 항상 최댓값 또는최솟값이 위치합니다. 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현하는데 힙은 트리 종류 중 하나입니다.

우선순위 큐의 특징

• 우선순위 큐는 값을 비교해야하므로 null을 허용하지 않는다.
• 마찬가지로 비교할 수 없는 객체는 큐를 만들 수 없다.
• 내부구조는 이진트리 힙으로 구성되어 있다.
• 내부구조가 이진트리로 되어있어서 add() 및 poll() 메서드(추가, 삭제 메서드)는 O(log(n))시간이 걸린다.
• AbstractQueue, AbstractCollection, Collection 및 Object 클래스에서 메서드를 상속한다.

가. Priority Queue(우선순위 큐) 선언하기

import java.util.PriorityQueue;

// Integer 타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQu1 = new PriorityQueue<>();

// Integer 타입으로 우선순위 큐 선언(높은 숫자 순으로 우선순위 결정)
PriorityQueue<Integer> priorityQu2 = new PriorityQueue<>
(Collections.reversOrder());

// String타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQu3 = new PriorityQueue<>();

// String타입으로 우선순위 큐 선언(낮은 숫자 순으로 우선순위 결정)
PriorityQueue<String> priorityQu3 = new PriorityQueue<>
(Collections.reversOrder());

나. Priority Queue 값 추가하기

import java.util.PriorityQueue;

public class PriorityQueueDemo {
	public static void main(String[] args){
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		// 1, 15, 8, 21, 25, 18, 10 값 추가
		pq.add(1);
		pq.add(15);
		pq.offer(10);
		pq.add(21);
		pq.add(25);
		pq.offer(18);
		pq.add(8);
		System.out.print(pq); // 결과: [1, 15, 8, 21, 25, 18, 10]
	}
}

• add와 offer의 차이점 Queue에 데이터를 추가, 삭제, 검색할 때 제공되는 메서드들의 차이는 기능적인 것보단 문제 상황에서 예외를 던지느냐 혹은 null이나 false를 반환하느냐에 있다.
  

즉 enqueue동작 처리를 위해서 데이터를 추가해야하는데 이미 큐가 꽉 찬 경우 add는 예외를 발생시키지만 offer는 추가 실패를 의미하는 false를 반환한다.

스택 연산 수행 방법

1. 현재 수열 값 ≥ 자연수

현재 수열 값이 자연수보다 크거나 같을 때까지 자연수를 1씩 증가시키며 자연수를 스택에 push한다. 그리고 push가 끝나면 수열을 출력하기 위해 마지막 1회만 pop한다.

예를 들어 현재 수열 값이 4면 스택에는 1, 2, 3, 4를 push하고 마지막 1회만 pop하여 4를 출력한 뒤 조건문을 빠져나온다. 자연수는 5가 된다.

2. 현재 수열 값 < 자연수

현재 수열 값보다 자연수가 크다면 pop으로 스택에 있는 값을 꺼낸다. 꺼낸 값이 현재 수열 값이거나 아닐 수 있다. 만약 아니라면 후입선출 원리에 따라 수열을 표현할 수 없으므로 NO를 출력한 후 문제를 종료하고, 현재 수열 값이라면 그대로 조건문을 빠져나온다.

앞의 예를 이어 설명하면 자연수는 5, 현재 수열 값은 3이므로 스택에서 3을 꺼낸다.