Skip to content
第3章

3.3 顺序栈 ​

栈顶放在哪一头 ​

3.2节只说了栈能做什么,没说怎么存。现在把栈放进内存。

栈是线性表,2.3节的顺序表可以直接拿来用:一段连续的格子,元素从第0格开始一个挨一个放。只剩一个问题:栈只在一端进出,这一端放在数组的哪一头?

两种放法都试一下。站里已经有1号、2号、3号,3号是栈顶,现在Push(S, 4)。

放法一:栈底在第0格,栈顶在末尾。

text
         0   1   2   3   4
       ┌───┬───┬───┬───┬───┐
Push前 │ 1 │ 2 │ 3 │   │   │
       ├───┼───┼───┼───┼───┤
Push后 │ 1 │ 2 │ 3 │ 4 │   │
       └───┴───┴───┴───┴───┘

4直接放进第3格,谁都不用挪。

放法二:栈顶在第0格。

text
         0   1   2   3   4
       ┌───┬───┬───┬───┬───┐
Push前 │ 3 │ 2 │ 1 │   │   │
       ├───┼───┼───┼───┼───┤
Push后 │ 4 │ 3 │ 2 │ 1 │   │
       └───┴───┴───┴───┴───┘

要先把1、2、3各往后挪一格,才能空出第0格放4。Pop也一样,删掉第0格之后,后面的都要往前挪一格。

这和2.7节的结论一样:顺序表在末尾插入、删除,一个都不用挪;在开头插入、删除,要挪n个。栈的进出全在栈顶,所以栈顶放在末尾,栈底放在第0格。

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