@[toc]
本篇将讲述栈的相关知识
在之前的文章中我们学习了线性表,大家一定要掌握线性表的相关知识,这是后面内容的基础。
栈的定义
先来看看栈的定义:
栈是限定仅在表尾进行插入和删除操作的线性表。表尾一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈;从一个栈删除元素又称作出栈或退栈。
由定义可以得知,栈本质就是一个线性表,只不过栈只能在表尾进行插入和删除操作,是操作受限的线性表。
因为只能在表尾进行插入和删除,所以栈中的元素是先进后出的,也就是说,最先进栈的元素最后才出栈。
可以将栈的结构类比成子弹夹,最先压入的子弹在最底下。
下图为元素的进栈过程:
下图为元素的出栈过程:
对于入栈和出栈的理解一定要透彻,比如现在有三个元素1,2,3,其入栈顺序为1,2,3,则出栈顺序是怎样的呢?有以下几种情况:
- 让1先入栈,然后2入栈,最后3入栈;出栈顺序为:3,2,1
- 让1先入栈,1出栈,然后2入栈,2出栈,最后3入栈,3出栈;出栈顺序为:1,2,3
- 让1先入栈,然后2入栈,2出栈,1出栈,最后3入栈,3出栈;出栈顺序为:2,1,3
- 让1先入栈,然后2入栈,2出栈,最后3入栈,3出栈,1出栈;出栈顺序为:2,3,1
- 让1先入栈,1出栈,然后2入栈,最后3入栈,3出栈,2出栈;出栈顺序为:1,3,2
元素的入栈和出栈顺序比较灵活,大家可以自己画图理解一下。
栈的抽象数据类型定义
这个大家都有基础了,我直接贴出来就可以了。
ADT Stack{
数据对象:D = {
ai|ai∈ElemSet,i = 1,2,3,...,n-1,n,n>=0}
数据关系:R1={
<ai-1,ai>|ai-1,ai∈D,i=2,3,...,n-1,n}
基本操作:
InitStack();//初始化栈
Push(int val);//入栈
Pop(int *val);//出栈
DestroyStack(&s);//销毁栈
StackEmpty(s);//判断栈是否为空
StackLength(s);//求栈的长度
GetTop(s,&val);//获取栈顶元素
ClearStack(&s);//清空栈
......
}ADT Stack
栈的顺序实现
对于栈的顺序存储,我们依然通过数组实现。
通过设置两个指针,一个top指针指示栈顶元素的位置;一个base指针指示栈底元素的位置。
不过为了操作方便,通常top指针指示的并不是栈顶元素的位置,而是栈顶元素之上的一个位置,如下图:
当top指向base,即:top == base
的时候,表示栈为空。
而为了判断栈满的情况,我们设置一个stacksize,它表示栈的最大容量。倘若top - base`== stacksize
,表示栈已满。
下面是对栈的结构定义:
#define Elemtype int
typedef struct{
ElemType *top; //栈顶指针
ElemType *base; //栈底指针
int stacksize; //栈的最大容量
}Stack,*PStack;
顺序栈的基本操作
下面介绍顺序栈的一些基本操作。
顺序栈的初始化
如何对顺序栈进行初始化呢?直接看代码:
void InitStack(PStack s){
//分配一段内存
s->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
if(s->base == NULL){
exit(-1);
}
//初始栈顶指针等于栈底指针
s->top = s->base;
s->stacksize = MAXSIZE;//最大容量
}
判断顺序栈是否为空
在顺序栈的定义中,我们就说道,如果知道一个顺序栈是否为空,判断栈顶指针的指向和栈底指针的指向是否相同,即:top == base
,若条件成立,则表示顺序栈为空。
代码如下:
int StackEmpty(Stack s){
if(s.top == s.base){
return 1;
}else{
return 0;
}
}
求顺序栈的长度
求顺序栈的长度非常简单,让栈顶指针减栈底指针即可得到长度。
代码如下:
int StackLength(Stack s){
return s.top - s.base;
}
清空顺序栈
清空顺序栈并不是释放栈的内存,而是清除栈内的元素,不管栈内有没有有用的元素,我们此时统统认为它们是无用的,是垃圾,所以只需将栈顶指针指向栈底即可完成顺序栈的清空。
代码如下:
void ClearStack(PStack s){
if(s->base != NULL){
s->top = s->base;
}
}
销毁顺序栈
销毁很简单,把栈的内存释放即可。
代码如下:
void DestroyStack(PStack s){
if(s->base != NULL){
free(s->base);
s->stacksize = 0;
s->base = s->top = NULL;
}
}
顺序栈的入栈
上面的操作比较简单,下面来看看比较复杂的操作:入栈和出栈。
假设有下面的一个顺序栈:
如何对该顺序栈进行入栈操作呢?
把入栈元素值赋值给top指针指向的位置,然后top指针往上移动一位。
还得考虑栈满的情况,也就是当top - base == stacksize
时,栈满,无法入栈。
代码如下:
int Push(PStack s,int val){
//判断栈是否满
if(s->top - s->base == s->stacksize){
return -1;
}
//将元素val入栈
*s->top = val;//对top指针所指的区域赋值
//栈顶指针加1
s->top++;
return 1;//入栈成功,返回1
}
顺序栈的出栈
假设有如下的一个顺序表:
如何实现出栈呢?
top指针指向的是栈顶元素的上一个位置,所以 要想实现出栈操作,得先让top指针向下移动一位,然后取出元素:
当然还需要考虑栈空的情况,当栈顶指针和栈底指针指向同一个位置,即:top == base
时,栈空,无法出栈。
代码如下:
int Pop(PStack s,int *val){
//判断栈是否空
if(StackEmpty(*s)){
return -1;
}
s->top--;//将指针下移
*val = *s->top;//元素出栈
return 1;//出栈成功,返回1
}
初始化、入栈、出栈的操作我们都实现了,下面来测试一下:
void main(){
Stack s,*ps;
int val,i;
ps = &s;
InitStack(ps);
Push(ps,1);
Push(ps,2);
Push(ps,3);
for(i = 0;i < 3;i++){
Pop(ps,&val);
printf("出栈元素:%d\t",val);
}
getchar();
}
运行结果:
出栈元素:3 出栈元素:2 出栈元素:1
在初始化的时候,我们是通过传入一个Stack指针类型的变量ps,而ps的值是Stack类型变量s的地址,为什么要这样做呢?
因为如果直接使用变量ps,或者直接通过PStack定义出指针变量,再将该变量作为参数传入初始化函数时,程序会检测出你没有对该变量进行初始化,从而产生错误,所以必须这么做。当然,你也可以把这一步骤放到初始化函数内部进行。
栈的链式实现
下面来说一说栈的链式实现,对于链式栈,我们同样通过链表实现,对于链栈,它只能在链表头部进行操作,我们将链表头部称为栈顶,链表尾部称为栈底。
链栈的结构定义如下:
typedef struct Node{
ElemType data;//数据域
struct Node *next;//指针域
}Node,*Stack;
在链栈中,可以不需要头结点(增设头结点反而会使操作更复杂),那么链表的头指针其实就是栈顶指针。
链栈的基本操作
链栈的初始化
链栈的初始化非常简单,无需创建头结点,声明头指针并设初始值为NULL即可,代码如下:
Stack InitStack(){
//构造一个空栈
Stack s = NULL;//s为头指针,亦为栈顶指针,初始值为NULL
return s;
}
判断链栈是否为空
判空算法也很简单,看看栈顶指针是否为NULL就可以了,代码如下:
int StackEmpty(Stack s){
//若栈顶指针为NULL,表明栈为空
if(s == NULL){
return 1;
}else{
return 0;
}
}
关于其它的一些操作比较简单,写法类似于单链表,下面重点说一说入栈和出栈操作。
链栈的入栈操作
假设有下面的一个链栈:
如何实现入栈操作呢?
先让新结点p的指针域指向栈顶结点,即:p->next = s
。
然后要让新插入的结点p成为栈顶结点,即:s = p
。
此时完成入栈操作。
代码实现如下:
Stack Push(Stack s,int val){
//创建新结点
Stack p = (Stack) malloc(sizeof(Node));
if(p == NULL){
exit(-1);
}
p->data = val;
//让p指向栈顶结点
p->next = s;
//让p成为栈顶结点
s = p;
return s;
}
链栈的出栈操作
假设如下的一个链栈:
该如何实现出栈呢?
出栈非常简单,让栈顶指针s指向下一个结点就可以了,即:s = s->next
。
但此时我们就找不到被删除的结点了,所以在改变指针指向之前,我们需要定义一个结点类型变量p存储栈顶结点,然后改变指针指向,最后释放p,完成出栈操作。
代码实现如下:
Stack Pop(Stack s,int *val){
Stack p;
if(s == NULL){
printf("栈为空!");
return s;
}
*val = s->data;
//保存栈顶结点
p = s;
//让栈顶指针指向下一个结点
s = s->next;
//释放结点内存
free(p);
return s;//出栈成功
}
下面来测试一下:
void main(){
Stack s;
int val = 0,i;
s = InitStack();
s = Push(s,1);
s = Push(s,2);
s = Push(s,3);
for(i = 0;i < 3;i++){
s = Pop(s,&val);
printf("出栈元素值:%d\t",val);
}
getchar();
}
运行结果:
出栈元素值:3 出栈元素值:2 出栈元素值:1
源代码
顺序栈代码
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAXSIZE 10
#define ElemType int
typedef struct{
ElemType *top; //栈顶指针
ElemType *base; //栈底指针
int stacksize; //栈的最大容量
}Stack,*PStack;
int Pop(PStack s,int *val){
//判断栈是否空
if(s->top == s->base){
return -1;
}
s->top--;//将指针下移
*val = *s->top;//元素出栈
return 1;//出栈成功,返回1
}
int Push(PStack s,int val){
//判断栈是否满
if(s->top - s->base == s->stacksize){
return -1;
}
//将元素val入栈
*s->top = val;//对top指针所指的区域赋值
//栈顶指针加1
s->top++;
return 1;//入栈成功,返回1
}
void DestroyStack(PStack s){
if(s->base != NULL){
free(s->base);
s->stacksize = 0;
s->base = s->top = NULL;
}
}
void ClearStack(PStack s){
if(s->base != NULL){
s->top = s->base;
}
}
int StackLength(Stack s){
return s.top - s.base;
}
int StackEmpty(Stack s){
if(s.top == s.base){
return 1;
}else{
return 0;
}
}
void InitStack(PStack s){
//分配一段内存
s->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
if(s->base == NULL){
exit(-1);
}
//初始栈顶指针等于栈底指针
s->top = s->base;
s->stacksize = MAXSIZE;//最大容量
}
链栈代码
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAXSIZE 10
#define ElemType int
typedef struct{
ElemType *top; //栈顶指针
ElemType *base; //栈底指针
int stacksize; //栈的最大容量
}Stack,*PStack;
int Pop(PStack s,int *val){
//判断栈是否空
if(s->top == s->base){
return -1;
}
s->top--;//将指针下移
*val = *s->top;//元素出栈
return 1;//出栈成功,返回1
}
int Push(PStack s,int val){
//判断栈是否满
if(s->top - s->base == s->stacksize){
return -1;
}
//将元素val入栈
*s->top = val;//对top指针所指的区域赋值
//栈顶指针加1
s->top++;
return 1;//入栈成功,返回1
}
void DestroyStack(PStack s){
if(s->base != NULL){
free(s->base);
s->stacksize = 0;
s->base = s->top = NULL;
}
}
void ClearStack(PStack s){
if(s->base != NULL){
s->top = s->base;
}
}
int StackLength(Stack s){
return s.top - s.base;
}
int StackEmpty(Stack s){
if(s.top == s.base){
return 1;
}else{
return 0;
}
}
void InitStack(PStack s){
//分配一段内存
s->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
if(s->base == NULL){
exit(-1);
}
//初始栈顶指针等于栈底指针
s->top = s->base;
s->stacksize = MAXSIZE;//最大容量
}