一.准备知识
顺序栈是数据结构栈的一个分类，顺序栈也是一种受限的线性表，我们说这个受限是指它受到了某种限制，这个限制是什么呢？
先来看一下顺序栈的示意图：
a1,a2…an依次进入这个容器，出来的时候是an先出来，接着…a2,a1.我们把这种进入出入的方式成为“先进后出”。造成这种方式的原因是这个容器只有一个开口，栈底是不能出入的，只能在栈顶那端进行操作，这就是我们说的受限。
二.顺序栈结构的打造
前期文章《顺序表》我们谈到顺序表的存储结构时用的是数组存取元素值，当前顺序栈也是同样的道理，具体看前期文章。
用结构体打造顺序栈：
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef struct Stack { int data[MAXSIZE];//栈空间 int top;//栈顶指针 }SeqStack;
这时候我们打造了如下的栈结构：
三.功能函数的声明与写法
void Init_SeqStack(SeqStack *s);//初始化 int Empty_SeqStack(SeqStack *s);//判空 int Push_SeqStack(SeqStack *s, int x);//入栈 void PrintStack(SeqStack *s);//打印栈元素 int Pop_SeqStack(SeqStack *s, int *x);//出栈 int Gettop_SeqStack(SeqStack *s, int *x);//获取栈顶元素
函数接口我们不用再具体分析了。
第一步初始化
void Init_SeqStack(SeqStack *s) { s->top = -1;//置空操作 }
在这里我们需要知道：
栈空：top=-1；
栈满：top=MAXSIZE-1；
这里是怎么来的呢？观察如下示意图：
0以下为-1，MAXSIZE以下为满。
第二步判空
int Empty_SeqStack(SeqStack *s) { if (s->top == -1) return 1; else return 0; }
第三步入栈
int Push_SeqStack(SeqStack *s, int m) { if (s->top == MAXSIZE - 1) return 0;//栈满不能入栈 else { s->top++; s->data[s->top] = m; } return 1; }
第四步顺序栈元素值的打印
void PrintStack(SeqStack *s) { int i; if (Empty_SeqStack(s) == 1) { printf("顺序栈为空！"); exit(1); } else for (i = s->top; i >= 0; i--) printf("%4d", s->data[i]); }
第五步顺序栈的出栈
int Pop_SeqStack(SeqStack *s, int *x) { if (Empty_SeqStack(s) == 1) return 0;//栈空，不能出栈 else { *x = s->data[s->top];//将栈顶元素放入变量x中 s->top--; } return 1; }
第六步栈顶元素的读取
int Gettop_SeqStack(SeqStack *s, int *x) { if (Empty_SeqStack(s) == 1) return 0;//栈空 else { *x = s->data[s->top]; } return 1; }
四.完成主函数
int main() { SeqStack s; int x;//出栈的时候读取到的值 int data[MAXSIZE];//这一个数组的定义主要是为了使用PrintStack函数的时候使用的 int n, m, i; Init_SeqStack(&s); Empty_SeqStack(&s); printf("请输入元素个数？\n"); scanf("%d", &n); printf("请输入入栈的%d个元素的值:\n\n", n); for (i = 0; i < n; i++) { scanf("%d", &m); Push_SeqStack(&s, m); } printf("出栈的元素为:\n"); for (i = 0; i < n; i++) { Pop_SeqStack(&s,&x); printf("%4d",x); } /* 其实输出栈的函数你可以选择使用PrintStack函数，这里我选择了使用出栈的函数Pop_SeqStack。 */ Gettop_SeqStack(&s,&x); printf("\n此时的栈顶元素读取到为%d\n", x); //PrintStack(&s); return 0; }
心得体会：
- 通过函数接口分析和算法分析自己完成主函数，这是一项很重要的能力。
- 入栈出栈的调用操作，我们通常在主函数里面用循环完成，循环调用。
- 观察函数接口用到的指针变量，我们在主函数里需要进行定义，定义好了梳理函数调用的先后次序，最后开始写代码。
五.全部代码演示
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef struct Stack { int data[MAXSIZE];//栈空间 int top;//栈顶指针 }SeqStack; /*========================== 函数声明 ===========================*/ void Init_SeqStack(SeqStack *s); int Empty_SeqStack(SeqStack *s); int Push_SeqStack(SeqStack *s, int x); void PrintStack(SeqStack *s); int Pop_SeqStack(SeqStack *s, int *x); int Gettop_SeqStack(SeqStack *s, int *x); int main() { SeqStack s; int x;//出栈的时候读取到的值 int data[MAXSIZE];//这一个数组的定义主要是为了使用PrintStack函数的时候使用的 int n, m, i; Init_SeqStack(&s); Empty_SeqStack(&s); printf("请输入元素个数？\n"); scanf("%d", &n); printf("请输入入栈的%d个元素的值:\n\n", n); for (i = 0; i < n; i++) { scanf("%d", &m); Push_SeqStack(&s, m); } printf("出栈的元素为:\n"); for (i = 0; i < n; i++) { Pop_SeqStack(&s,&x); printf("%4d",x); } /* 其实输出栈的函数你可以选择使用PrintStack函数，这里我选择了使用出栈的函数Pop_SeqStack。 */ Gettop_SeqStack(&s,&x); printf("\n此时的栈顶元素读取到为%d\n", x); //PrintStack(&s); return 0; } /*============================= 函数功能：顺序栈的初始化 ==============================*/ void Init_SeqStack(SeqStack *s) { s->top = -1; } /*============================= 函数功能：顺序栈的判空 ==============================*/ int Empty_SeqStack(SeqStack *s) { if (s->top == -1) return 1; else return 0; } /*============================= 函数功能：顺序栈的入栈 ==============================*/ int Push_SeqStack(SeqStack *s, int m) { if (s->top == MAXSIZE - 1) return 0;//栈满不能入栈 else { s->top++; s->data[s->top] = m; } return 1; } /*============================= 函数功能：顺序栈的输出 ==============================*/ void PrintStack(SeqStack *s) { int i; if (Empty_SeqStack(s) == 1) { printf("顺序栈为空！"); exit(1); } else for (i = s->top; i >= 0; i--) printf("%4d", s->data[i]); } /*============================= 函数功能：顺序栈的出栈 ==============================*/ int Pop_SeqStack(SeqStack *s, int *x) { if (Empty_SeqStack(s) == 1) return 0;//栈空，不能出栈 else { *x = s->data[s->top];//将栈顶元素放入变量x中 s->top--; } return 1; } /*============================= 函数功能：顺序栈的栈顶元素的读取 ==============================*/ int Gettop_SeqStack(SeqStack *s, int *x) { if (Empty_SeqStack(s) == 1) return 0;//栈空 else { *x = s->data[s->top]; } return 1; }
六.运行结果
