定义
用顺序存储方式实现的栈称为顺序栈,顺序栈对应于顺序表。
设栈中的数据元素的类型是整型,用一个足够长的一维数组s来存放元素,数组的最大容量为STACK_INTSIZE。同时假设栈顶指针top。(在以下的程序中,top不是指向当前的栈顶元素,而是指向下一次将要进栈的元素的存储位置)
顺序栈可以描述如下:
1
2
3
4
|
#define STACK_INTSIZE 50 /*分配栈的最大存储空间*/ #define DataType int /*定义栈中数据元素的类型*/ DataType s[STACK_INTSIZE]; /*用来存放栈中数据元素的内存空间*/ int top; /*定义栈顶指针*/ |
可以用结构体数组来实现顺序栈:
1
2
3
4
5
6
7
8
|
#define STACK_INTSIZE 50 #define DataType int typedef struct { DataType s[STACK_INTSIZE]; int top; } Stack; Stack *st; /*指针st用来引用一个顺序栈*/ |
栈顶指针动态地反映了栈中元素的变化情况,top=0时,表示空栈;top=1时,表示已经有一个元素进栈;进栈时,栈顶指针top上移,top加1;top=STACK_INTSIZE,表示栈满;出栈时,栈顶指针top下移,top减1。
1.建立空栈
1
2
3
4
5
6
7
|
Stack *InitStack() { Stack *s; s = (Stack *) malloc ( sizeof (Stack)); s->top = 0; return s; } |
2.进栈
1
2
3
4
5
6
7
8
9
10
|
void Push(Stack *st, DataType x) { if (st->top >= STACK_INTSIZE) printf ( "栈已满,不能入栈!\n" ); /*若栈满则不能进栈,输出出错信息*/ else { st->s[st->top] = x; /*元素x进栈*/ st->top++; /*栈顶指针top加1*/ } } |
3.出栈
1
2
3
4
5
6
7
8
9
|
void Pop(Stack *st) { if (st->top == 0) printf ( "栈空,不能出栈!\n" ); /*若栈空则不能出栈,且输出栈空的信息*/ else /*栈非空*/ { st->top--; /*top减1,元素出栈*/ } } |
4.读栈顶元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
DataType ReadTop(Stack *st) { DataType x; if (st->top == 0) { printf ( "栈中无元素" ); return (0); } /*若栈空则返回0*/ else { x = st->s[st->top-1]; /*取栈顶元素*/ return (x); /*返回x即栈顶元素的值*/ } } |
5.遍历栈
结合元素出栈算法和读取栈顶元素算法,使用循环,当st->top=0时结束循环,即可遍历栈。
1
2
3
4
5
6
7
8
|
void ShowStack(Stack *st) { while (st->top > 0) { st->top--; printf ( "%d" , st->s[st->top]); } } |
总结
本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注服务器之家的更多内容!
原文链接:https://blog.csdn.net/weixin_60921752/article/details/122772938