해당 포스트는 이지스퍼블리싱, 『알고리즘 코딩테스트 자바 편』, Gene 김종관 을 참고하여 작성하였습니다.

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

스택과 큐의 핵심 이론

스택

스택stack은 삽입과 삭제 연산이 후입선출LIFO로 이뤄지는 자료구조입니다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있습니다.

스택용어

위치

• top : 삽입과 삭제가 일어나는 위치를 뜻한다.

연산

• push : top 위치에 새로운 데이터를 삽입하는 연산이다.
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

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

스택 예시 코드

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 스택에 요소 추가 (push)
        stack.push(1); // 스택: [1]
        stack.push(2); // 스택: [1, 2]
        stack.push(3); // 스택: [1, 2, 3]

        // 스택에서 요소 제거 (pop)
        int poppedElement = stack.pop();
        System.out.println("스택에서 꺼낸 요소: " + poppedElement); // 스택에서 꺼낸 요소: 3

        // 스택의 맨 위 요소 확인 (peek)
        int topElement = stack.peek();
        System.out.println("스택의 맨 위 요소: " + topElement); // 스택의 맨 위 요소: 2
    }
}

큐

큐queue는 삽입과 삭제 연산이 선입선출FIFO로 이뤄지는 자료구조입니다. 스택과 다르게 먼저 들어온 데이터가 먼저 나갑니다. 그래서 삽입과 삭제가 양방향에서 이뤄집니다.

큐 용어

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

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

큐 예시 코드

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 큐에 요소 추가 (offer)
        queue.offer(1); // 큐: [1]
        queue.offer(2); // 큐: [1, 2]
        queue.offer(3); // 큐: [1, 2, 3]

        // 큐에서 요소 제거 및 반환 (poll)
        int polledElement = queue.poll();
        System.out.println("큐에서 빠져나온 요소: " + polledElement); // 큐에서 빠져나온 요소: 1

        // 큐의 맨 앞 요소 확인 (peek)
        int frontElement = queue.peek();
        System.out.println("큐의 맨 앞 요소: " + frontElement); // 큐의 맨 앞 요소: 2
    }
}

offer() 메서드는 add()와 유사하지만, 큐가 꽉 찼을 때 add()는 예외를 발생시키고 offer()는 false를 반환합니다. 따라서 큐를 사용할 때는 일반적으로 offer()를 사용하는 것이 안전합니다.

[참고자료1] https://hong-devbox.tistory.com/4
[참고자료2] https://yoongrammer.tistory.com/46