后进先出（LIFO）的线性序列被称为栈。栈也是一种线性表，不过是操作受限的线性表，只能在一端进出。进出的一端被称为栈顶。另一端被称为栈底。栈可以采用顺序存储，也可以采用链式存储，分别被称为顺序栈和链栈。
一：栈
1.顺序栈
栈的顺序存储方式如下图：（见视频）
显然，顺序栈需要两个指针，base指向栈底，top指向栈顶。顺序栈的数据结构定义（动态分配）如下：
typedef struct SQStack{ElemType *base;ElemType *top;}SQStack;
在栈定义好后，还要定义一个最大的分配空间，顺序结构都是这个要求，需要预先分配空间，因而可以采用宏定义或常量。
#definr Maxsize 100//或者const int Maxsize = 100;
上面的结构体定义采用了动态分配形式，也可以采用静态分配形式，使用一个定长数组来存储数据元素，使用一个整形下标记录栈顶元素的位置。顺序栈的数据结构定义（静态分配）如下图所示。
typedef struct SQStack{ElemType data[Maxsize];int top;}SQStack;
需要注意的是，栈只能在一端操作，后进先出的特性是人为规定的，也就是说不允许在中间进行查找取值插入删除等操作，但顺序栈本身是按顺序存储的，确实能从中间取出一个元素，但这样就不是栈了。
顺序栈的基本操作包括初始化，入栈，出栈和取栈顶元素等。这里以动态分配空间及int类型的元素为例进行详解。
- 初始化。
初始化一个空栈，动态分配Maxsize大小的空间，S.top和S.base指向该空间的基地址。
bool InitStack(SQStack &s){S.base = new int [Maxsize];if(!S.base)return false;S.top = S.base;return true;}
- 入栈。
入栈前判断栈是否已满，如果栈已满，则入栈失败；否则将元素放入栈顶，栈顶指针向上移动一个位置（top++）。依次输入1,2，入栈，如下图所示。
bool Push(SQStack &S,int e){if(S.top-S.base==Maxsize)return false;*S.top++=e //等价于*S.top = e;S.top++;return true;}
- 出栈
出栈前要判断栈是否已空，如果栈已空，则出栈失败；否则就将栈顶元素暂存到一个变量中。栈顶指针向下移动一个空间（top—）。栈顶元素所在的位置实际上是S.top-1，因此把该元素取出来，暂存在变量e中，然后S.top指针向下移动一个位置。因此可以先移动一个位置，即—S.top，然后取元素。
注意，空间未销毁。只是下次元素进栈进行原有值的覆盖。
bool pop(SQStack &s,int &e){if(S.base==S.top)return false;e = *--S.top;return true;}
- 取栈顶元素
取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一次，栈顶指针未移动，栈内元素的个数未变。而出栈指栈顶指针向下移动一个位置，栈内不再包含该元素。
int GetTop(SQStack S){
if(S.top!=S.base)
return *(S.top-1);
else
return -1;
}
2：链栈
和线性表一样，栈可以采用顺序存储，也可以采用链式存储。顺序栈和链栈如下图所示：（视频）
顺序栈是分配一段连续空间，需要两个指针，base指向栈底，top指向栈顶。而链栈每个节点地址都是不连续的，只需一个栈顶指针即可。链栈的节点和单链表节点一样，包含两个域：数据域和指针域。可以把链栈看做一个不带头结点的单链表，但只能在头部进行插入删除取值等操作，无法在中间和尾部操作。
链栈的数据结构定义如下：
typedef struct StackNode
{
ElemType data;
struct StackNode *next;
}StackNode ,*LinkStack;
可以看出，链栈的节点定义和单链表一样，只不过它只能在栈顶那一端操作。
链栈的基本操作包括初始化，入栈，出栈，取栈顶元素等（以int为例）
- 初始化
初始化一个空栈，链栈不需要头结点，因此只需要让栈顶指针为空指针即可
bool InitStack(LinkStack &S){
S=NULL;
return true;
}
- 入栈
入栈就是把新节点压入栈顶，也就是将新节点放在第一个节点前面，然后把栈顶指针指向新节点即可。
p = new Snode;
p->data = e;
->是指针的指向运算符，通常与结构体一起使用。
- 出栈
出栈就是把栈顶指针删除，栈顶指针指向下一个节点，然后释放该节点空间。
bool Pop(LinkStack &S,int &e){
LinkStack p;
if(S==NULL)
{
return false;
}
e = S->data;
p=S;
S = S->next;
delete p;
return true;
}
- 取栈顶元素
和出栈不同，取栈顶元素就是把栈顶元素复制一份，栈顶指针不改变。而出栈是删除栈顶元素，栈顶指针指向下一个元素。
int GetTop(LinkStack S){
if(S!=NULL)
return s->data;
else
return -1;
}
#include<iostream>
using namespace std;
#define Maxsize 100 //预先分配空间，这个数值根据实际需要预估确定；
typedef struct SqStack {
int *base; //栈底指针
int *top; //栈顶指针
}SqStack;
bool InitStack(SqStack &S) //构造一个空栈S
{
S.base = new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间
if (!S.base) //空间分配失败
return false;
S.top=S.base; //top初始为base，空栈
return true;
}
bool Push(SqStack &S, int e) // 插入元素e为新的栈顶元素
{
if (S.top-S.base == Maxsize) //栈满
return false;
*(S.top++) = e; //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;
return true;
}
bool Pop(SqStack &S, int &e) //删除S的栈顶元素，暂存在变量e中
{
if (S.base == S.top) //栈空
return false;
e = *(--S.top); //栈顶指针减1，将栈顶元素赋给e
return true;
}
int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变
{
if (S.top != S.base) //栈非空
return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变
else
return -1;
}
int main()
{
int n,x;
SqStack S;
InitStack(S);//初始化一个顺序栈S
cout <<"请输入元素个数n：" <<endl;
cin>>n;
int &m=n;
cout<<&n<<endl;
cout <<"请依次输入n个元素，依次入栈：" <<endl;
while(n--)
{
cin>>x; //输入元素
Push(S, x);
}
cout <<"元素依次出栈：" <<endl;
while(S.top!=S.base)//如果栈不空，则依次出栈
{
cout<<GetTop(S)<<"\t";//输出栈顶元素
Pop(S, x); //栈顶元素出栈
}
return 0;
}
三：队列
后进先出（FILO）是栈，队列的特点是先进先出（FIFO）。队列也是一种线性表，不过他也是操作受限的线性表，只能在两端操作：从一端进，从另一端出。进的一端被称作队尾（rear），出的一端被称作队头（front）。同样，队列可以采用顺序存储，也可以采用链式存储。
1，顺序队列
队列的顺序存储指用一段连续的空间存储数据元素，用两个整型变量记录队头和队尾元素的下标。如图（视频）。
顺序队列的数据结构定义（动态分配）如下：
struct SqQueue{
int *base;//基地址
int front,rear;//头索引 尾索引
};
顺序结构定义好之后，还要先定义一个最大分配空间，顺序结构都是如此。
#define Maxsize 100
顺序队列的静态分配数据结构定义如下
typedef struct SqQueue{
ElemType data[Maxsize];
int front,rear;
}SqQueue;
与栈同理，队列只能从一端进一端出，不允许在中间查找取值替换等，先进先出也是人为规定的，若破坏此规则就不是队列了。
图解如视频。
2.循环队列
简单讲解下循环队列队空，队满的判定条件，以及入队，出队，队列元素个数计算等基本操作方法。
由于只是小的改动，大部分和顺序队列相同，只在视频中讲解，此处只写几个知识点。
（1）队空判断条件即Q.front ==Q.rear。
（2）判断队满（Q.rear+1）%Maxsize= Q.front。
（3）入队
Q.base[Q.rear]=x;
Q.rear = (Q.rear+1)%Maxsize;
(4)出队
e = Q.base[Q.front];
Q.front = (Q.front+1)%Maxsize;
(5)计算队列中元素个数
(Q.rear - Q.front+Maxsize)%Maxsize;
3.链队列
数据结构定义
typedef struct QNode /* 结点结构 */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
链队列结构体定义
typedef srtuct{
Qnode *front;
Qnode *rear;
}LinkQueue
各操作相同。
#include <iostream>
using namespace std;
#define Maxsize 100
typedef struct SqQueue{
int *base; //基地址
int front,rear; //头指针,尾指针
}SqQueue;
//循环队列的初始化
bool InitQueue(SqQueue &Q)//注意使用引用参数，否则出了函数，其改变无效
{
Q.base=new int[Maxsize];//分配空间
if(!Q.base) return false;
Q.front=Q.rear=0; //头指针和尾指针置为零，队列为空
return true;
}
//循环队列的入队
bool EnQueue(SqQueue &Q,int e)//将元素e放入Q的队尾
{
if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针，表明队满
return false;
Q.base[Q.rear]=e; //新元素插入队尾
Q.rear=(Q.rear+1)%Maxsize; //队尾指针加1
return true;
}
//循环队列的出队
bool DeQueue(SqQueue &Q, int &e) //删除Q的队头元素，用e返回其值
{
if (Q.front==Q.rear)
return false; //队空
e=Q.base[Q.front]; //保存队头元素
Q.front=(Q.front+1)%Maxsize; //队头指针加1
return true;
}
//取循环队列的队头元素
int GetHead(SqQueue Q)//返回Q的队头元素，不修改队头指针
{
if (Q.front!=Q.rear) //队列非空
return Q.base[Q.front];
return -1;
}
//循环队列的长度
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+Maxsize)%Maxsize;
}
int main()
{
SqQueue Q;
int n,x;
InitQueue(Q);//初始化队列(一定要初始化，否则后面存储出错)
cout <<"请输入元素个数n：" <<endl;
cin>>n;
cout <<"请依次输入n个整型数，依次入队：" <<endl;
while(n--)
{
cin>>x;
EnQueue(Q,x);//入队
}
cout<<endl;
cout <<"队列内元素个数，即长度："<<QueueLength(Q)<<endl;
cout <<"队头元素：" <<GetHead(Q)<<endl;
cout <<"元素依次出队：" <<endl;
while(true)//如果栈不空，则依次出栈
{
if(DeQueue(Q,x))
cout<<x<<"\t";//出队元素
else
break;
}
cout <<endl;
cout <<"队列内元素个数，即长度："<<QueueLength(Q)<<endl;
return 0;
}
训练，洛谷p1739—链接
若有收获，就点个赞吧
0 人点赞
