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라고 한다.
• 가득 찬 Queue에 요소를 추가하려고 할 때 Overflow가 발생하며, 빈 큐에서 요소를 제거하려고 할 때 Underflow가 발생한다.

배열 구조로 큐 구현하기

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

예시 문제 기반 설명

Java

Python

JavaScript

실수 포인트