外观
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语言写出来?
顺序栈
用顺序存储的栈叫顺序栈。它和顺序表一样,是一段连续的格子,再加一个数记着栈里有几个元素:
c
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE]; /* 存放元素的连续空间,栈底在第0格 */
int top; /* 栈里元素的个数 */
} SeqStack;元素是整数,因为要放的是车厢编号。
top就是顺序表的length,换个名字,是因为它正好指着栈顶:元素放在第0格到第top−1格,栈顶元素在第top−1格,第top格是下一个空格。下面的图只画5格,右边的箭头指着第top格:
左边是空栈,top是0。右边放了1、2、3,top是3,栈顶3在第2格,箭头指着空着的第3格。
由此马上得到两个操作。初始化就是让top为0;判空就是看top是不是0:
c
void InitStack(SeqStack *S) {
S->top = 0;
}
int StackEmpty(SeqStack *S) {
return S->top == 0;
}S传的是地址,和2.5节以后的顺序表一样。
栈满时,top等于MAXSIZE。这一条Push会用到。
另一种约定:top指着栈顶元素
有的教材让top等于栈顶元素的下标。这时空栈的top是−1,栈满的top是MAXSIZE−1;Push要先把top加1再放,Pop要先取再把top减1。两种约定都对,本书沿用顺序表的length,让top等于元素的个数。
Push:放到栈顶
栈里是1、2,top是2。现在Push(S, 3)。
第一步:判断栈满。top是2,不等于MAXSIZE,放得下。
第二步:3放进第top格。第top格就是下一个空格,也就是第2格:
c
S->data[S->top] = 3; /* data[2] = 3 */第三步:top加1。现在有3个元素了:
c
S->top++; /* top = 3 */先放,再加1,顺序不能反。top指着的是空格。先加1,top就变成3,3会放进第3格;第2格空着没放东西,却已经算在栈里了。
写成函数。要放的是x,放进第top格,再把top加1。放不下返回0,放好了返回1:
c
int Push(SeqStack *S, int x) {
if (S->top == MAXSIZE) return 0; /* 第一步:栈满,放不下 */
S->data[S->top] = x; /* 第二步:x放进第top格 */
S->top++; /* 第三步:top加1 */
return 1;
}Pop:删除栈顶,用x带回
栈里是1、2、3,top是3。现在Pop(S, &x)。
第一步:判断栈空。top是3,不是0,有东西可删。
第二步:top减1。栈顶元素在第top−1格,也就是第2格。top减成2,第2格就不算在栈里了:
c
S->top--; /* top = 2 */格子里的3还在,图里画成灰色。它不用擦掉:top以上的格子都算空,下次Push会直接把它盖掉。
第三步:用x带回第top格。top现在是2,第2格里就是刚删掉的3:
c
*x = S->data[S->top]; /* x = data[2],也就是3 */这里的顺序和Push正好相反:Push先放再加,Pop先减再取。因为top指着的是空格,栈顶在它下面一格。
写成函数。栈空返回0,删好了返回1,删掉的元素用x带回:
c
int Pop(SeqStack *S, int *x) {
if (S->top == 0) return 0; /* 第一步:栈空,没有可删的 */
S->top--; /* 第二步:top减1 */
*x = S->data[S->top]; /* 第三步:用x带回第top格 */
return 1;
}为什么x是int *,不是int?Pop要把删掉的元素交给调用者,也就是要改调用者自己的变量。如果参数写成int x,调用时复制给函数的是调用者那个x的值。函数里给x赋值,改的只是这份复制品,调用者的x不变,和2.5节的Inc1一样。
所以调用时传的是x的地址&x,参数用存地址的int *。*x = …顺着地址改的,就是调用者的x。
GetTop:取栈顶
GetTop和Pop只差一点:只看,不删,所以top不变。栈顶元素在第top−1格,直接读出来:
c
int GetTop(SeqStack *S, int *x) {
if (S->top == 0) return 0; /* 栈空,没有栈顶 */
*x = S->data[S->top - 1]; /* 栈顶在第top-1格 */
return 1;
}把五个操作合起来
五个函数都写好了。再写一个main,照着3.2节的例题,用顺序栈把1、2、3调成2、1、3:
c
int main(void) {
SeqStack S;
int x;
InitStack(&S);
Push(&S, 1);
Push(&S, 2);
Pop(&S, &x); printf("%d ", x);
Pop(&S, &x); printf("%d ", x);
Push(&S, 3);
Pop(&S, &x); printf("%d\n", x);
printf("栈空吗:%d\n", StackEmpty(&S));
return 0;
}把这个main接在前面五个函数后面,再在开头加上#include <stdio.h>,就是完整的程序。运行结果:
text
2 1 3
栈空吗:1main里的调用和3.2节例题一一对应,只是S前面多了&,因为函数要的是地址。存法是这一节才定的,调用的顺序一个都没变。
五个操作都只碰栈顶那一格和top,一个元素都不挪,时间复杂度都是O(1)。
完整的程序放在下面,可以直接复制运行:
c
#include <stdio.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top;
} SeqStack;
void InitStack(SeqStack *S) {
S->top = 0;
}
int StackEmpty(SeqStack *S) {
return S->top == 0;
}
int Push(SeqStack *S, int x) {
if (S->top == MAXSIZE) return 0; /* 第一步:栈满,放不下 */
S->data[S->top] = x; /* 第二步:x放进第top格 */
S->top++; /* 第三步:top加1 */
return 1;
}
int Pop(SeqStack *S, int *x) {
if (S->top == 0) return 0; /* 第一步:栈空,没有可删的 */
S->top--; /* 第二步:top减1 */
*x = S->data[S->top]; /* 第三步:用x带回第top格 */
return 1;
}
int GetTop(SeqStack *S, int *x) {
if (S->top == 0) return 0; /* 栈空,没有栈顶 */
*x = S->data[S->top - 1]; /* 栈顶在第top-1格 */
return 1;
}
int main(void) {
SeqStack S;
int x;
InitStack(&S);
Push(&S, 1);
Push(&S, 2);
Pop(&S, &x); printf("%d ", x);
Pop(&S, &x); printf("%d ", x);
Push(&S, 3);
Pop(&S, &x); printf("%d\n", x);
printf("栈空吗:%d\n", StackEmpty(&S));
return 0;
}练习1:top和格子里是什么?
填空
顺序栈,从空栈开始,依次调用:
Push(&S, 7),Push(&S, 8),Push(&S, 9),Pop(&S, &x),Pop(&S, &x),Push(&S, 6)
- 全部做完,top是
- data[1]里是
- data[2]里是
- data[2]里的这个数,还在栈里吗?
三次Push之后,7、8、9在第0到第2格,top是3。两次Pop,top减到1,9和8都还留在格子里。再Push(&S, 6),6放进第top格,也就是第1格,把8盖掉,top变成2。第2格里的9没人动过,但它在第top格及以上,不算在栈里。
练习2:Push的两行写反了会怎样?
单选
有人把Push的第二步和第三步写反了:
c
S->top++;
S->data[S->top] = x;从空栈开始,调用Push(&S, 5),会怎样?
A
和原来一样,5放进第0格,top是1
先加1,top就是1了,5放进的是第1格。
B
5放进第1格,第0格没放东西,top是1
top是1,表示栈里有1个元素,栈顶在第0格。可第0格从没放过东西,GetTop读到的不是5。
C
编译出错
两行都是合法的C语句,编译能通过,错在结果。
top指着下一个空格,所以要先放、再加1。照这样写反,栈满时还会写到data[MAXSIZE],越过数组的末尾。
到这里你有了顺序栈:一段连续的格子加一个top,栈底在第0格,top等于元素个数,指着下一个空格。五个操作都是O(1)。下一步用链表存栈。