栈-数据结构
- C语言
- 2024-04-10
- 1721热度
- 0评论
栈-数据结构
栈的定义
只允许在一端进行插入或删除操作的线性表。
逻辑结构:与普通的线性表相同
数据的运算:插入、删除操作有区别
栈的概念
栈顶:允许插入和删除的一端
栈底:不允许插入和删除的一端
空栈:不包含数据元素
栈的基本操作
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; //栈类型定义