03栈和队列--栈
前言
知识框架
注意:必考的是 (出入栈的过程,出栈序列的合法性)以及队列的操作和特征。
算法设计题目中的是:对了的顺序存储,链式存储,双端队列。
3.1栈
3.1.1桟的基本概念
1,定义stack桟:只允许在一端进行插入或删除操作的线性表。首先桟是一种线性表,但是限定这种线性表只能在某一段进行插入和删除操作。
栈顶top:线性表允许进行插入和删除的那一段。
栈底bottom:固定的,不允许进行插入和删除的那一端。
空桟:不含任何元素的空表。
哈哈:看图我们可以知道栈的一个明显的特性可以概括为 后进先出 (last in first out , info)
备注:我们接触每一种新的数据结构类型,都应该分别从其逻辑结构,存储结构和对数据的运算三个方面着手。
2,栈的基本操作
基本操作语法:
InitStack(&S) : 初始化一个空栈。
StackEmpty(S):判断一个栈是否为空,如果空返回true,否则返回false.
Push(&S,x):进栈,若s栈未满,将x加入使之成为新栈顶。
Pop(&S,&x):出栈,若s非空,则弹出栈顶的元素,并用x返回
GetTop(S,&x):读栈顶元素,若栈S非空,用x返回栈顶元素。
ClearStack(&S) : 销毁栈,并释放栈S占用的存储空间
3.1.2栈的顺序存储结构
1,顺序栈的实现
栈的顺序存储称为顺序栈,它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附设一个指针(top)指示当前栈顶的位置。
栈的顺序存储类型可描述为:
#define Maxsize 50
typedef struct {
Elemtype data [Maxsize]; //存放栈中的元素
int top; //栈顶指针
}SqlStack
2,顺序栈的基本操作
以下是顺序栈常用的基本运算操作的实现:
初始化:
void InitStack (&S){
s.top=-1; //初始化栈顶指针
}
判栈空:
bool StackEmpty(S){
if(s.top == -1){
return true;
}else{
return false;
}
}
进栈:
bool Push(SqStack &S,ElemType x){
if(S.top == MaxSize-1){
return false; //栈满,报错
}
S.data[++S.top] = x ; //指针先加1,再入栈
return true;
}
出栈:
bool Pop(SqStack &S , ElemType &x){
if(S.top == -1){
return false; //栈空,报错
}
x = S.data[S.top--]; // 先出栈,指针再减1
return true;
}
读栈顶元素:
bool GetTop (SqStack S,ElemType &x){
if(S.top == -1){
return false; // 栈空,报错
}
x = S.data[S.top]; //x记录栈顶元素
return true;
}
3,共享栈
共享栈是为了更加有效地利用存储空间,两个栈的空间相互调节,只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1)。所以对存取效率没有什么影响。
3.1.3栈的链式存储结构
采用链式存储的栈称为链栈,链栈的优点是便于多个栈共享存储空间以及提高效率,并且不存在栈满上溢的情况。通常采用单链表实现,并且规定所有操作都是在单链表的表头进行的。这里规定栈链没有头结点。