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() : 큐에 끝(rear)에 항목을 추가
• 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(우선순위 큐)

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

De Queue(데 큐)

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

🧐Stack vs Queue

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

✨Tip

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

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

참고

• 가득 찬 Stack 혹은 Queue에 요소를 추가하려고 할 때 Overflow가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 Underflow가 발생한다.

---

문제 패턴

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

📚Stack 패턴

최근 값 기준 처리

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

문제에서 자주 나오는 형태

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

접근 방법

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

📚Queue 패턴

순서대로 처리

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

문제에서 자주 나오는 형태

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

접근 방법

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

예시 문제 기반 설명

올바른 괄호

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

ㅤ

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

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

JavaScript

Java

Python

실수 포인트