Skip to content
第3章

3.4 链栈 ​

栈顶放在哪一头 ​

3.3节用一段连续的格子存栈。栈也可以用2.9节的链表来存:每个元素一个结点,用地址连起来。

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

放法一:第一个结点是栈底,栈顶在表尾。

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

Pop要删掉3结点,就得把2结点的地址格改成0。可2结点在哪?链表只记着第一个结点的地址,只能从L出发一个一个走过去。栈里有n个元素,就要走n−1步。

放法二:第一个结点是栈顶。

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

Pop删的是第一个结点:把S改成3结点地址格里的109,一步就到。Push也只是在最前面接一个结点,一步都不用走。

这和2.16节量出的结论一样:链表在头部插入、删除是O(1),在尾部是O(n),正好和顺序表相反。所以链栈的栈顶放在表头,也和顺序栈正好相反。两种存法,都把栈顶放在自己最省事的那一头。

本节问题
栈顶在链表头,栈的五个操作怎么用C语言写出来?
选中正文里的任意文字,就可以针对它发表评论