{ }codelper

学习 › C#

算法 · 27

栈与队列

栈先取出后放入的，队列先取出先放入的。

栈和队列是把值放进去、再按固定顺序取出来的数据结构。
下面的例子是学校食堂。
tray x 把 x 号餐盘放到盘堆的最上面，come 名字 让这个人排到队尾。
serve 让队首的人拿走最上面的餐盘，如果没有餐盘或没有人就输出 -。
最后输出剩下的餐盘数和还在等的人数。

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);    }}
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、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() 读。

各语言的差异
处理“最近的先来”的事情（撤销、括号配对）用栈，处理“按到达顺序”的事情（排队、等候轮次）用队列。
只移动 head 的队列，取出的值仍留在数组里，所以在 C 里数组要按“放入的次数”来开，而不是按“同时等待的最大数量”。
Craykon 的列表最多 1 万个元素，用 按位置移除(0) 把 1 万个元素从开头全部删完，在我们的评测机上也在 0.2 秒内完成。

练习题

  1. 食堂的餐盘堆8P0348
  2. 先到先得的借伞处8P0351
  3. 括号匹配8P0040
  4. 售票处排队8P0071
  5. 遵守先修课的学期计划8P0197
  6. 在车辆段连挂列车4P0207
  7. 门一扇扇上锁的博物馆8P0291
  8. 折叠的评论串的行号8P0292