算法 · 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。从空列表里读或删会提示“列表是空的”并停止 |
常见错误
以为 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() 读。
从空栈里取值却没有报错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。
各语言的差异
处理“最近的先来”的事情（撤销、括号配对）用栈，处理“按到达顺序”的事情（排队、等候轮次）用队列。
只移动
Craykon 的列表最多 1 万个元素，用
处理“最近的先来”的事情（撤销、括号配对）用栈，处理“按到达顺序”的事情（排队、等候轮次）用队列。
只移动
head 的队列，取出的值仍留在数组里，所以在 C 里数组要按“放入的次数”来开，而不是按“同时等待的最大数量”。Craykon 的列表最多 1 万个元素，用
按位置移除(0) 把 1 万个元素从开头全部删完，在我们的评测机上也在 0.2 秒内完成。