3주차

Stack / Queue

코딩 테스트에서 매우 자주 등장하는 선형 자료구조

• 데이터를 어떤 순서로 넣고 꺼내느냐에 따라 동작 방식이 달라진다.
• 특히 두 자료구조는 순서 처리, 대기열 관리, 괄호 검사, 탐색(BFS/DFS) 등과 깊게 연결되어 있다.
• 삽입과 삭제가 어느쪽에서 일어나는지, 그리고 어떤 상황에서 Stack을 쓰고 Queue를 써야 하는지를 정확하게 이해하는 것이 중요하다.

ㅤ

개념

🧩Stack

나중에 들어온 데이터가 먼저 나가는 후입선출 구조로, LIFO(Last In, First Out) 구조라고도 부른다.

특징

• 한쪽 끝에서만 삽입과 삭제가 일어난다.
• 가장 마지막에 들어온 데이터가 가장 먼저 나온다.
• 재귀, 되돌리기(Undo), 괄호 검사 문제에 자주 사용된다.
• DFS와도 자주 연결되는 개념이다.

주요 연산

• push(e) : 새로운 요소 e를 스택의 최상단에 추가
• pop() : 스택의 맨 위에 있는 요소를 꺼내서 반환
• peek() : 스택의 최상단 요소를 삭제하지 않고 반환
• isEmpty : 스택이 비어있으면 True 반환 / 아니면 False 반환
• isFull : 스택이 가득 차 있으면 True 반환 / 아니면 False 반환

참고

• push의 경우 상단에 어떤 요소를 쌓을 지 그 정보를 입력해 주어야 한다.
• pop의 경우는 무조건 가장 상단의 요소를 삭제하는 것이므로 별도의 입력이 필요없다.

배열 구조로 스택 구현하기

const stackList = [];

function push(data) {
  stackList.push(data);
}

function pop() {
  // 가장 마지막 요소 삭제 및 반환
  const data = stackList[stackList.length - 1]; 
  stackList.pop();
  return data;
}

for (let index = 0; index < 10; index++) {
  push(index); // 0번부터 9번까지 데이터가 들어간다.
}

console.log(pop()); // 9가 출력된다.

ㅤ

🧩Queue

먼저 들어온 데이터가 먼저 나가는 선입선출 구조로, FIFO(First In, First Out) 구조라고도 부른다.

특징

• 뒤에서 삽입하고, 앞에서 삭제한다.
• 가장 먼저 들어온 데이터가 가장 먼저 나온다.
• 대기열, 작업 순서 처리, BFS 문제에 자주 사용된다.
• 입력 순서를 유지해야 하는 상황에서 유용하다.

주요 연산

• enqueue(e) : 큐에 끝(rear)에 요소 e를 추가
• dequeue() : 큐에 맨 앞(front)에 항목을 제거하고 반환
• peek() : 큐에 맨 앞(front)에 있는 항목을 반환
• isFull() : 큐가 가득 찼는지 확인
• isEmpty() : 비어 있는지 확인

참고

• Queue의 Rear(끝)에서 요소를 추가하는 작업을 enqueue라고 하며, Front(맨 앞)에서 요소를 제거하는 작업을 dequeue라고 한다.

배열 구조로 큐 구현하기

const queueList = [];

function enqueue(data) {
  queueList.push(data); // 뒤에 넣기
}

function dequeue() {
  return queueList.shift(); // 앞에서 꺼내기
}

for (let index = 0; index < 10; index++) {
  enqueue(index); // 0부터 9까지 들어감
}

console.log(dequeue()); // 0
console.log(dequeue()); // 1

Queue의 종류

Linear Queue(선형 큐)

데이터를 FIFO 순서로 처리하는 가장 기본적인 큐의 형태이다.

Circular Queue(환형 큐)

큐의 마지막 요소가 첫 요소와 연결된 큐로, 원형으로 순환하는 특징을 가진다.

Priority Queue(우선순위 큐)

각 데이터 요소에 우선순위를 할당하고 해당 우선순위에 따라 데이터를 처리하는 큐

Deque(덱)

양쪽에서 삽입, 삭제가 가능한 구조

ㅤ

🧐Stack vs Queue

구분	Stack	Queue
동작 방식	LIFO	FIFO
삽입 위치	한쪽 끝	뒤
삭제 위치	같은 쪽 끝	앞
대표 활용	괄호 검사, DFS, Undo	BFS, 대기열, 작업 처리

✨Tip

자료를 어떤 순서로 처리해야 하는가?

• 가장 최근 값부터 처리해야 한다면? ➡ Stack
• 들어온 순서대로 처리해야 한다면? ➡ Queue

참고

• 가득 찬 Stack 또 Queue에 요소를 추가하려고 하면 Overflow가 발생하며, 비어있는 Stack 또는 Queue에서 요소를 제거하려고 하면 Underflow가 발생한다.

ㅤ

---

문제 패턴

Stack / Queue 문제는 대부분 순서 처리 방식을 묻는 경우가 많으며, 다음과 같은 패턴이 등장하면 Stack 또는 Queue 문제일 가능성이 높다.

📚Stack 패턴

최근 값 기준 처리

가장 마지막에 넣은 값을 먼저 꺼내야 하는 경우, Stack을 주로 사용하자!

문제에서 자주 나오는 형태

• 괄호 짝 맞추기
• 문자열에서 특정 문자 제거
• 되돌리기 기능
• 이전 상태 추적

접근 방법

• 조건에 따라 push
• 필요할 때 pop
• 가장 위에 있는 값과 현재 값을 비교하며 처리

ㅤ

📚Queue 패턴

순서대로 처리

가장 먼저 들어온 값을 먼저 처리해야 하는 경우, Queue를 주로 사용하자!

문제에서 자주 나오는 형태

• 프린터 대기열
• 카드 뽑기
• BFS
• 시간 순서 시뮬레이션

접근 방법

• 뒤(Rear)에 데이터를 추가
• 앞(Front)에서 데이터를 꺼내며 처리
• 처리 순서를 유지하면서 반복

ㅤ

---

예시 문제 기반 설명

📝올바른 괄호

문자열 s가 주어졌을 때, 괄호가 올바르게 짝지어졌는 판단하라!

ㅤ

문제 접근 방법

Stack의 대표 예제로, 모든 순회가 끝난 뒤 Stack이 비어 있어야 올바른 괄호로 판단한다.

문자열을 왼쪽부터 순회하면서

• 여는 괄호 (는 Stack에 넣고
• 닫는 괄호 )가 나오면 Stack의 맨 위 괄호와 짝을 맞춘다. ㅤ

🐧이해가 제대로 되지 않으셨다고요? 예시를 들어 보겠습니다.

• ()() → 올바름
• (())() → 올바름
• )()( → 올바르지 않음

이런 느낌이라고 생각하시면 됩니다 :D

참고

• 시간 복잡도 : O(n)

ㅤ

JavaScript

function solution(s) {
    const stack = [];

    for (let char of s) {
        if (char === "(") {
            stack.push(char);
        } else {
            if (stack.length === 0) return false;
            stack.pop();
        }
    }

    return stack.length === 0;
}

코드 설명

1. 빈 Stack을 하나 생성한다.
2. 문자열을 왼쪽부터 순회하며 하나씩 확인한다.
3. 여는 괄호 (라면 push() 한다.
4. 닫는 괄호 )라면
   1. 비어있는지 먼저 확인한다.
   2. 비어 있지 않다면 pop()하여 짝을 맞춘다.
5. 순회가 끝난 뒤 Stack이 비어 있다면 올바른 괄호이다.

ㅤ

Java

import java.util.Stack;

class Solution {
    boolean solution(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(ch);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                stack.pop();
            }
        }

        return stack.isEmpty();
    }
}

코드 설명

1. 빈 Stack을 하나 생성한다.
2. 문자열을 문자 배열로 변환한 뒤 하나씩 순회한다.
3. 여는 괄호 (라면 push() 한다.
4. 닫는 괄호 )라면
5. Stack이 비어 있는지 확인한다.
6. 비어 있다면 올바르지 않은 괄호이므로 false를 반환한다.
7. 비어 있지 않다면 pop() 하여 짝을 맞춘다.
8. 순회가 끝난 뒤 Stack이 비어 있다면 올바른 괄호이다.

ㅤ

Python

def solution(s):
    stack = []

    for ch in s:
        if ch == '(':
            stack.append(ch)
        else:
            if len(stack) == 0:
                return False
            stack.pop()

    return len(stack) == 0

코드 설명

1. 빈 리스트를 Stack처럼 사용한다.
2. 문자열을 왼쪽부터 하나씩 순회한다.
3. 여는 괄호 (라면 append()로 스택에 넣는다.
4. 닫는 괄호 )라면
5. 스택이 비어 있는지 확인한다.
6. 비어 있다면 올바르지 않은 괄호이므로 False를 반환한다.
7. 비어 있지 않다면 pop()으로 짝을 맞춘다.
8. 순회가 끝난 뒤 스택이 비어 있다면 올바른 괄호이다.

ㅤ

---

실수 포인트

1️⃣ Stack/Queue를 배열로 구현할 때, 성능 차이를 고려하지 않은 경우

JS에서 배열로 Stack을 구현할 때 push, pop은 편하지만 Queue를 구현할 때 shift()를 자주 사용하면 비효율적일 수 있다.

queue.shift();

• shift()는 맨 앞 요소를 제거한 뒤 나머지 요소를 한 칸씩 당겨야 하므로, 반복해서 사용할 경우 성능이 떨어질 수 있다.

2️⃣ 비어있는 자료구조에서 꺼내려는 경우

Stack이나 Queue가 비어 있는데 pop, dequeue 같은 동작을 하면 예상하지 못한 값이 나오는 Underflow가 생길 수 있다.

• 따라서 값을 꺼내기 전에, 자료구조가 비어있는지 먼저 확인하는 습관이 중요하다.