{ }codelper

배우기 › Java

알고리즘 · 27

스택과 큐

나중에 넣은 것부터 꺼내는 스택, 먼저 넣은 것부터 꺼내는 큐.

스택과 큐는 값을 넣어 두었다가 정해진 차례로 꺼내는 자료 구조예요.
아래 예제는 급식실이에요.
tray x는 번호 x인 식판을 더미 맨 위에 올리고, come 이름은 그 사람이 줄 맨 뒤에 서요.
serve는 줄 맨 앞 사람이 맨 위 식판을 가져가는데, 식판이나 사람이 없으면 -를 찍어요.
마지막에 남은 식판 수와 기다리는 사람 수를 찍어요.

import java.util.ArrayDeque;import java.util.Scanner; public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int q = sc.nextInt();        ArrayDeque<Integer> pile = new ArrayDeque<>(); // 스택: push · pop        ArrayDeque<String> waiting = new ArrayDeque<>(); // 큐: add · poll        for (int i = 0; i < q; i++) {            String cmd = sc.next();            if (cmd.equals("tray")) {                pile.push(sc.nextInt()); // 맨 위에 올리기            } else if (cmd.equals("come")) {                waiting.add(sc.next()); // 맨 뒤에 서기            } else if (!pile.isEmpty() && !waiting.isEmpty()) { // 꺼내기 전에 비었는지 확인                String name = waiting.poll(); // 가장 먼저 온 사람                int tray = pile.pop(); // 가장 나중에 올린 식판                System.out.println(name + " " + tray);            } else {                System.out.println("-");            }        }        System.out.println(pile.size() + " " + waiting.size());    }}
stdin
9
tray 3
tray 8
come ann
come bob
serve
tray 5
serve
serve
come cho
stdout
ann 8
bob 5
-
1 1

핵심

  • 스택은 나중에 넣은 것이 먼저 나와요(후입선출, LIFO).
    쌓아 둔 식판처럼 넣는 곳과 꺼내는 곳이 같은 한쪽 끝이에요.
  • 큐는 먼저 넣은 것이 먼저 나와요(선입선출, FIFO).
    줄 서기처럼 뒤로 넣고 앞에서 꺼내요.
  • 스택은 목록의 끝만 쓰면 돼요.
    끝에 넣고 끝에서 빼면 다른 값은 움직이지 않아요.
  • 목록의 맨 앞을 빼면 남은 값이 모두 한 칸씩 당겨져요.
    우리 채점기에서 20만 개를 앞에서부터 다 빼 보니 Python list.pop(0)은 3.5초쯤, Java ArrayList.remove(0)은 2초쯤, C# List.RemoveAt(0)과 C++ vector.erase(begin())는 1.7초쯤 걸렸고, JavaScript shift()는 3초를 조금 넘겨 시간 제한(3초)에 걸렸어요.
    같은 일을 큐 전용 자료 구조(deque·ArrayDeque·Queue·std::queue)로 하면 프로그램이 뜨는 시간까지 넣어도 모두 0.05초 안에 끝났어요.
  • 큐 전용 자료 구조가 없는 JavaScript·TypeScript·C·크레이콘에서는 배열(목록)을 큐로 써요.
    넣을 때는 끝에 넣고, 꺼낼 때는 값을 빼지 않고 waiting[head]를 읽은 다음 맨 앞 번호 head를 1 늘려요.
    head가 넣은 개수와 같으면 빈 큐이고, 기다리는 개수는 넣은 개수 − head예요.
    우리 채점기의 JavaScript에서 이 방법으로 20만 개를 꺼내는 데는 0.01초도 안 걸렸어요.
  • 꺼내기 전에 비었는지 먼저 확인해요.
    빈 스택·큐에서 꺼내면 오류로 멈추는 언어도 있고(Python·C#·크레이콘), 오류 없이 undefined나 null이 나오는 것도 있어요(JavaScript, Java의 poll).
    C·C++에서는 무슨 일이 일어날지 정해져 있지 않아요.

언어별로 쓰는 법

Python스택은 리스트: pile.append(x), pile.pop(), 맨 위 보기 pile[-1].
큐는 from collections import deque: waiting.append(x), waiting.popleft(), 맨 앞 보기 waiting[0].
비었는지는 if pile:.
빈 데서 꺼내면 IndexError.
queue.Queue는 스레드끼리 값을 주고받는 데 쓰는 것이고, 비었을 때 get()이 오류 없이 계속 기다리니 여기서는 deque를 써요
JavaScript스택은 배열: pile.push(x), pile.pop(), 맨 위 보기 pile[pile.length - 1].
큐 전용은 없어서 waiting.push(x)로 넣고 waiting[head++]로 꺼내요.
빈 배열의 pop()·shift()는 오류 없이 undefined를 줘요
TypeScriptJavaScript와 같아요.
pile.pop()의 타입이 number | undefined라서, number 변수에 담으려면 비었는지 확인한 뒤 pile.pop()!처럼 써요
Java둘 다 ArrayDeque.
스택은 push·pop·peek, 큐는 add·poll·peek.
push는 맨 앞에, add는 맨 뒤에 넣고, pop·poll·peek는 모두 맨 앞을 다뤄요.
비었는지는 isEmpty().
빈 데서 pop()은 NoSuchElementException, poll()·peek()는 null
C#Stack<int>: Push·Pop·Peek.
Queue<string>: Enqueue·Dequeue·Peek.
개수는 Count.
빈 데서 꺼내면 InvalidOperationException, TryPop(out x)·TryDequeue(out x)는 멈추지 않고 false를 돌려줘요
C++#include <stack>: push·top·pop.
#include <queue>: push·front·pop.
pop()은 값을 돌려주지 않으니 top()·front()로 먼저 읽어요.
비었는지는 empty().
빈 데서 top()·front()·pop()을 부르면 오류로 멈춘다는 보장이 없고, 무슨 일이 일어날지 정해져 있지 않아요(정의되지 않은 동작)
C전용 자료 구조가 없어서 배열과 번호로 만들어요.
스택: pile[top++] = x;로 넣고 pile[--top]으로 꺼내요.
큐: waiting[tail++]에 넣고 waiting[head++]에서 꺼내요.
비었는지는 top > 0, head < tail
Craykon둘 다 목록이에요.
스택: pile.넣기(x), 맨 위는 pile[pile.개수 - 1], 빼기는 pile.자리빼기(pile.개수 - 1).
큐: waiting.넣기(x)로 넣고 waiting[head]를 읽은 뒤 head += 1.
빈 목록에서 읽거나 빼면 "목록이(가) 비어 있어요"라며 멈춰요

자주 하는 실수

add로 넣고 pop으로 꺼냈어요Java

Deque<Integer> pile = new ArrayDeque<>();
pile.add(1);
pile.add(2);
pile.add(3);
System.out.println(pile.pop());

→ 1 — 가장 나중에 넣은 3이 아니에요. add는 맨 뒤에 넣고 pop은 맨 앞에서 꺼내서 큐처럼 움직였어요

스택은 push·pop, 큐는 add·poll로 짝을 맞춰 써요.
push는 맨 앞에 넣으니, push로 1, 2, 3을 넣으면 pop()이 3을 줘요.

빈 스택에서 꺼냈는데 오류가 안 났어요JavaScript

const pile = [];
const tray = pile.pop();
console.log(tray + 1);

→ NaN — 빈 배열의 pop()은 멈추지 않고 undefined를 줘서, 틀린 값이 조용히 계산에 섞여요

꺼내기 전에 pile.length > 0인지 확인해요.
TypeScript는 같은 코드를 'tray' is possibly 'undefined'라며 실행 전에 막아 줘요.

pop()이 값을 돌려줄 줄 알았어요C++

std::stack<int> pile;
pile.push(3);
int tray = pile.pop();

→ 컴파일 오류 void value not ignored as it ought to be — std::stack과 std::queue의 pop()은 빼기만 하고 아무것도 돌려주지 않아요

int tray = pile.top();으로 먼저 읽고 pile.pop();으로 빼요.
큐는 front()로 읽어요.

언어마다 다른 점
"가장 최근 것부터" 다루는 일(되돌리기, 괄호 짝 맞추기)은 스택, "온 차례대로" 다루는 일(줄 서기, 차례 기다리기)은 큐예요.
head만 옮기는 큐는 꺼낸 값도 배열에 그대로 남으니, C에서는 배열을 "한꺼번에 기다리는 최대 수"가 아니라 "넣는 횟수"만큼 잡아요.
크레이콘은 목록이 1만 개까지라, 1만 개를 자리빼기(0)으로 앞에서부터 다 빼도 우리 채점기에서 0.2초 안에 끝났어요.

연습 문제

  1. 급식실 식판 더미8P0348
  2. 먼저 온 사람부터 받는 우산 대여함8P0351
  3. 괄호 짝 맞추기8P0040
  4. 매표소 줄8P0071
  5. 선수 과목을 지키는 학기 계획8P0197
  6. 차량 기지에서 기차 엮기4P0207
  7. 문이 하나씩 잠기는 박물관8P0291
  8. 접힌 댓글 타래의 줄 번호8P0292