学ぶ › JavaScript
アルゴリズム · 27
スタックとキュー
後から入れたものを先に出すスタック、先に入れたものを先に出すキュー。
スタックとキューは、値を入れておき、決まった順番で取り出すデータ構造です。
下の例は給食室です。tray x は番号 x のトレーを山のいちばん上に置き、come 名前 はその人が列のいちばん後ろに並びます。serve は列の先頭の人がいちばん上のトレーを取りますが、トレーか人がなければ - を表示します。
最後に、残ったトレーの数と待っている人の数を表示します。
from collections import deque q = int(input())pile = [] # 스택: 끝이 맨 위waiting = deque() # 큐: 왼쪽이 맨 앞for _ in range(q): parts = input().split() if parts[0] == "tray": pile.append(int(parts[1])) # 맨 위에 올리기 elif parts[0] == "come": waiting.append(parts[1]) # 맨 뒤에 서기 elif pile and waiting: # 꺼내기 전에 비었는지 확인 name = waiting.popleft() # 가장 먼저 온 사람 tray = pile.pop() # 가장 나중에 올린 식판 print(name, tray) else: print("-")print(len(pile), len(waiting))const lines = require("fs").readFileSync(0, "utf8").split("\n");const q = Number(lines[0]);const pile = []; // 스택: 끝이 맨 위const waiting = []; // 큐: 뒤에 넣고, 맨 앞 번호(head)만 뒤로 옮겨요let head = 0;for (let i = 1; i <= q; i++) { const parts = lines[i].trim().split(" "); if (parts[0] === "tray") { pile.push(Number(parts[1])); // 맨 위에 올리기 } else if (parts[0] === "come") { waiting.push(parts[1]); // 맨 뒤에 서기 } else if (pile.length > 0 && head < waiting.length) { // 꺼내기 전에 비었는지 확인 const name = waiting[head++]; // 가장 먼저 온 사람 const tray = pile.pop(); // 가장 나중에 올린 식판 console.log(name, tray); } else { console.log("-"); }}console.log(pile.length, waiting.length - head);import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const q: number = Number(lines[0]);const pile: number[] = []; // 스택: 끝이 맨 위const waiting: string[] = []; // 큐: 뒤에 넣고, 맨 앞 번호(head)만 뒤로 옮겨요let head: number = 0;for (let i = 1; i <= q; i++) { const parts: string[] = lines[i].trim().split(" "); if (parts[0] === "tray") { pile.push(Number(parts[1])); // 맨 위에 올리기 } else if (parts[0] === "come") { waiting.push(parts[1]); // 맨 뒤에 서기 } else if (pile.length > 0 && head < waiting.length) { // 꺼내기 전에 비었는지 확인 const name: string = waiting[head++]; // 가장 먼저 온 사람 const tray = pile.pop(); // 가장 나중에 올린 식판 console.log(name, tray); } else { console.log("-"); }}console.log(pile.length, waiting.length - head);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()); }}using System;using System.Collections.Generic; class Program{ static void Main() { int q = int.Parse(Console.ReadLine()); var pile = new Stack<int>(); // 스택: Push · Pop var waiting = new Queue<string>(); // 큐: Enqueue · Dequeue for (int i = 0; i < q; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); if (parts[0] == "tray") { pile.Push(int.Parse(parts[1])); // 맨 위에 올리기 } else if (parts[0] == "come") { waiting.Enqueue(parts[1]); // 맨 뒤에 서기 } else if (pile.Count > 0 && waiting.Count > 0) // 꺼내기 전에 비었는지 확인 { string name = waiting.Dequeue(); // 가장 먼저 온 사람 int tray = pile.Pop(); // 가장 나중에 올린 식판 Console.WriteLine(name + " " + tray); } else { Console.WriteLine("-"); } } Console.WriteLine(pile.Count + " " + waiting.Count); }}#include <iostream>#include <queue>#include <stack>#include <string> int main() { int q; std::cin >> q; std::stack<int> pile; // 스택: push · top · pop std::queue<std::string> waiting; // 큐: push · front · pop for (int i = 0; i < q; i++) { std::string cmd; std::cin >> cmd; if (cmd == "tray") { int x; std::cin >> x; pile.push(x); // 맨 위에 올리기 } else if (cmd == "come") { std::string who; std::cin >> who; waiting.push(who); // 맨 뒤에 서기 } else if (!pile.empty() && !waiting.empty()) { // 꺼내기 전에 비었는지 확인 std::string name = waiting.front(); // 가장 먼저 온 사람 waiting.pop(); // pop은 값을 돌려주지 않아서 먼저 읽고 빼요 int tray = pile.top(); // 가장 나중에 올린 식판 pile.pop(); std::cout << name << ' ' << tray << '\n'; } else { std::cout << "-\n"; } } std::cout << pile.size() << ' ' << waiting.size() << '\n';}#include <stdio.h>#include <string.h> int main(void) { int q; static int pile[1000]; // 스택: top이 든 개수이자 다음에 넣을 자리 int top = 0; static char waiting[1000][11]; // 큐: head가 맨 앞, tail이 다음에 넣을 자리 int head = 0, tail = 0; scanf("%d", &q); for (int i = 0; i < q; i++) { char cmd[8]; scanf("%7s", cmd); if (strcmp(cmd, "tray") == 0) { scanf("%d", &pile[top++]); // 맨 위에 올리기 } else if (strcmp(cmd, "come") == 0) { scanf("%10s", waiting[tail++]); // 맨 뒤에 서기 } else if (top > 0 && head < tail) { // 꺼내기 전에 비었는지 확인 char *name = waiting[head++]; // 가장 먼저 온 사람 int tray = pile[--top]; // 가장 나중에 올린 식판 printf("%s %d\n", name, tray); } else { printf("-\n"); } } printf("%d %d\n", top, tail - head); return 0;}q = コンソール.行読み().数に();pile = []; // 스택: 끝이 맨 위waiting = []; // 큐: 뒤에 넣고, 맨 앞 번호(head)만 뒤로 옮겨요head = 0;繰り返す (i = 0; i < q; i++){ parts = コンソール.行読み().空白除去().分ける(); もし (parts[0] == "tray") { pile.追加(parts[1].数に()); // 맨 위에 올리기 } でなければ もし (parts[0] == "come") { waiting.追加(parts[1]); // 맨 뒤에 서기 } でなければ もし (pile.個数 > 0 && head < waiting.個数) { name = waiting[head]; // 가장 먼저 온 사람 head += 1; tray = pile[pile.個数 - 1]; // 가장 나중에 올린 식판 pile.位置で取り除く(pile.個数 - 1); コンソール.書く(name + " " + tray); } でなければ { コンソール.書く("-"); }}コンソール.書く(pile.個数 + " " + (waiting.個数 - head));9 tray 3 tray 8 come ann come bob serve tray 5 serve serve come cho
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・Craykon では、配列（リスト）をキューとして使います。
入れるときは末尾に入れ、取り出すときは値を取り除かずにwaiting[head]を読んでから先頭の番号headを 1 進めます。headが入れた個数と同じなら空のキューで、待っている個数は「入れた個数 − head」です。
私たちのジャッジの JavaScript では、この方法で 20 万個を取り出すのに 0.01 秒もかかりませんでした。 - 取り出す前に空かどうかを先に確かめます。
空のスタックやキューから取り出すと、エラーで止まる言語もあれば（Python・C#・Craykon）、エラーなしで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 を返します |
| TypeScript | JavaScript と同じです。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。空のリストから読んだり取り除いたりすると「リストが空です」と言って止まります |
よくある間違い
空のスタックから取り出したのにエラーにならなかったJavaScript
const pile = [];
const tray = pile.pop();
console.log(tray + 1);→ NaN — 空の配列の pop() は止まらずに undefined を返すので、間違った値が黙って計算に混ざります
取り出す前に pile.length > 0 を確かめます。
TypeScript は同じコードを 'tray' is possibly 'undefined' として実行前に止めてくれます。
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 を返します。
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() で読みます。
言語ごとの違い
「いちばん新しいものから」扱う仕事（元に戻す、かっこの対応）はスタック、「来た順に」扱う仕事（行列、順番待ち）はキューです。
C では配列を「同時に待つ最大数」ではなく「入れる回数」の分だけ用意します。
Craykon のリストは 1 万個までで、1 万個を
「いちばん新しいものから」扱う仕事（元に戻す、かっこの対応）はスタック、「来た順に」扱う仕事（行列、順番待ち）はキューです。
head だけを進めるキューは、取り出した値も配列に残ります。C では配列を「同時に待つ最大数」ではなく「入れる回数」の分だけ用意します。
Craykon のリストは 1 万個までで、1 万個を
位置で取り除く(0) で先頭からすべて取り除いても、私たちのジャッジで 0.2 秒以内に終わりました。