数据结构之栈和队列(一)

本文主要介绍2种操作受限的线性表结构:栈(Stack)和队列(Queue),包括它们的概念和存储结构。除此之外,还会简单介绍一下特殊矩阵的压缩存储。

栈(Stack)

栈是只允许在一端进行插入或删除操作的线性表。它满足后进先出(LIFO)

栈的基本操作:

  1. InitStack(&S):初始化
  2. StackEmpty(S):判断栈是否为空
  3. Push(&S,x):进栈,若栈S未满,将x加入使之成为新的栈顶
  4. Pop(&S,x):出栈,若栈S非空,弹出栈顶元素,并用x返回
  5. GetTop(S,&x):读栈顶元素,若栈S非空,用x返回栈顶元素
  6. ClearStack(&S):销毁栈,释放S存储空间

栈的顺序存储

栈的顺序存储也称顺序栈,它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时设有一个指针(top)指示当前栈顶的位置。

栈的顺序存储类型描述如下:

1
2
3
4
5
#define MaxSize 50
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;

栈顶指针(top)初始值不同,进栈出栈操作也有所不同,栈顶指针初始值一般取-1或0,对应操作如下:

初始化栈

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

判栈空

1
2
3
4
5
6
bool StackEmpty(S){
if(s.top==-1)
return true; //栈空
else
return false;
}

进栈

1
2
3
4
5
6
bool Push(SqStack &S,ElemType x){
if(s.top==MaxSize-1) //栈满报错
return false;
S.data[++S.top]=x; //指针先加1,再进栈
return true;
}

出栈

1
2
3
4
5
6
bool Pop(SqStack &S,ElemType x){
if(s.top==-1) //栈空报错
return false;
x=S.data[S.top--]; //先出栈,指针再减1
return true;
}

读取栈顶元素

1
2
3
4
5
6
bool GetTop(SqStack &S,ElemType &x){
if(S.top==-1) //栈空报错
return false;
x=S.data[S.top]; //x记录栈顶元素
return true;
}

栈的链式存储

链式存储的栈又称链栈,优点是便于多个栈共享存储空间,提高效率,并且不存在栈满上溢情况。

  1. 常采用单链表实现,规定操作都是在单链表的表头进行
  2. 一般规定链栈没有头结点,Lhead指向栈顶元素

栈的链式存储类型描述如下:

1
2
3
4
typedef struct Linknode{
ElemType data; //数据域
struct Linknode *next; //指针域
}*LiStack;

共享栈

共享栈是为了高效的利用存储空间。利用栈底的位置相对不变这一特性,我们可以让2个顺序栈共享一个一维数据空间。这2个栈的栈底分别设在共享空间的两端,两个栈顶向共享空间延伸。

2个栈的进出栈操作如下图所示:

------ 本文结束------
bluesliuf wechat
坚持技术分享,欢迎大家扫码交流!