Skip to content
第3章

3.11 链队 ​

队头放在哪一头 ​

3.10节的循环队列,格子数要事先定好,最多只能放MAXSIZE−1个。银行不知道一天会来多少人,格子定少了不够,定多了浪费。

3.4节用链表存栈,要多少结点就申请多少。队列也可以这样存:每个元素一个结点,用地址连起来。

和链栈一样,先要定队头放在哪一头。还是存1、2、3,1号在队头,有两种放法。

放法一:第一个结点是队头。

text
L = 100
  │
  ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│ 1 │ 109 │────►│ 2 │ 105 │────►│ 3 │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘
    100             109             105

出队删的是第一个结点:把L改成1结点地址格里的109,一步就到。入队就麻烦了:4号要接在3结点后面,可3结点在哪?链表只记着第一个结点的地址,只能从L出发一个一个走过去。队里有n个元素,就要走n−1步。

放法二:第一个结点是队尾。

text
L = 105
  │
  ▼
┌───┬─────┐     ┌───┬─────┐     ┌───┬─────┐
│ 3 │ 109 │────►│ 2 │ 100 │────►│ 1 │  0  │
└───┴─────┘     └───┴─────┘     └───┴─────┘
    105             109             100

入队插在最前面,一步都不用走。出队要删1结点,就得把2结点的地址格改成0,又得从L走过去找2结点。

链栈的进和出在同一头,放在表头就都是一步。队列的进和出分在两头,不管怎么放,总有一个操作要从头走一遍。

本节问题
用链表存队列,能不能让入队、出队都不用从头走?
选中正文里的任意文字,就可以针对它发表评论