栈-数据结构

栈-数据结构

栈的定义

只允许在一端进行插入或删除操作的线性表。

逻辑结构:与普通的线性表相同

数据的运算:插入、删除操作有区别

栈的概念

栈顶:允许插入和删除的一端

栈底:不允许插入和删除的一端

空栈:不包含数据元素

栈的基本操作

InitStack(&S):初始化栈。构建一个空栈S,分配内存空间。

DestoryStack(&S):销毁栈。销毁并释放栈S所占用的内存空间。

Push(&S,x):进栈,若栈S未满,则将x加入使之成为新栈顶。

Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回。

GetTop(S,&x):读栈顶元素。若栈S非空,则用x返回栈顶元素。

StackEmpty(s):判断一个栈S是否为空。若S为空,则返回true,否则返回false。

顺序栈的实现

用顺序存储方式实现栈

基本操作:创(初始化)、增(进栈)、删(出栈)、查(获取栈顶元素)、判空、判满

顺序栈的定义

top指向栈顶元素

顺序存储:给各个数据元素分配连续的存储空间,大小为MaxSize*sizeof(ElemType)

#include <stdio.h>

#define MaxSize 10 //定义栈中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针
}SqStack;
int main(){
    SqStack S; //声明一个顺序栈(分配空间)
    return 0;
}
初始化操作
#include <stdio.h>

#define MaxSize 10 //定义栈中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack &S){
    S.top=-1; //初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S){
    if(S.top==-1) //栈空
    {
        return true;
    }else  //非空
    {
        return false;
    }
}
int main(){
    SqStack S; //声明一个顺序栈(分配空间)
    InitStack(S);
    return 0;
}
进栈操作
#include <stdio.h>

#define MaxSize 10 //定义栈中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针
}SqStack;

//新元素入栈
bool Push(SqStack &S,ElemType x){
    if(S.top==MaxSize-1) //栈满,报错
    {
        return false;
    }
    S.top = S.top+1; //新指针加1
    S.data[S.top]=x; //新元素入栈
    //S.data[++S.top]=x; //上面两句代码等价于这一句
    return true;
}
int main(){
    return 0;
}
出栈操作
#include <stdio.h>

#define MaxSize 10 //定义栈中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针
}SqStack;

//出栈操作
bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1) //栈空,报错
    {
        return false;
    }
    x=S.data[S.top]; //栈顶元素先出栈
    S.top=S.top-1; //指针减1
    //x=S.data[S.top--]; //与上面两条等价
    return true;
}
int main(){
    return 0;
}
读栈顶元素操作

读栈顶元素与出栈操作的区别,就只有少了栈顶指针减一的步骤

#include <stdio.h>

#define MaxSize 10 //定义栈中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top; //栈顶指针
}SqStack;

//出栈操作
bool Pop(SqStack &S,ElemType &x){
    if(S.top==-1) //栈空,报错
    {
        return false;
    }
    x=S.data[S.top]; //栈顶元素先出栈
    S.top=S.top-1; //指针减1
    //x=S.data[S.top--]; //与上面两条等价
}

//读栈顶元素
bool GetTop(SqStack &S,ElemType &x){
    if(S.top==-1) //栈空,报错
    {
        return false;
    }
    x=S.data[S.top]; //x记录栈顶元素
    return true;
}
int main(){
    return 0;
}
共享栈

共享栈是指两个栈共享同一片空间,栈满的条件:top0+1==top1

#include <stdio.h>

#define MaxSize 10 //定义栈中元素的最大个数
typedef int ElemType;
typedef struct {
    ElemType data[MaxSize]; //静态数组存放栈中元素
    int top0; //0号栈栈顶指针
    int top1; //1号栈栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack &S){
    S.top0=-1;
    S.top1=MaxSize;
}
int main(){
    return 0;
}

需要注意的是,另外一种定义方式,也可以把栈顶指针指向0的位置,这样判断栈空(S.top==0)、栈满(top==MaxSize)的条件和入栈、出栈的代码需要改变。

链式存储方式实现的栈

其实链式存储实现的栈跟头插法建立单链表差不多,对应的就是进栈的操作。

单链表后删操作对应的是出栈。

链栈的定义
typedef int ElemType;
typedef struct LinkNode{
    ElemType data; //数据域
    struct LinkNode *next; //指针域
}*LiStack; //栈类型定义

链栈的定义