文章目录
- 一.栈
-
- 1.1 栈的逻辑结构
- 1.2 栈的顺序存储结构及实现
-
- 1.2.1 顺序栈的实现——入栈
- 1.2.2顺序栈的实现——出栈
- 1.2.3 两栈共享空间
- 1.3 栈的链接存储结构及实现
-
- 1.3.1 链栈的实现——入栈
- 1.3.2 链栈的实现——出栈
- 1.4 顺序栈和链栈的比较
- 二.队列
-
- 2.1 队列的逻辑结构
- 2.2 队列的顺序存储结构及实现
-
- 2.2.1 循环队列
- 2.2.2 循环队列的实现——入队
- 2.2.3 循环队列的实现——出队
- 2.2.4 循环队列的实现——读队头元素
- 2.3 队列的链接存储结构及实现
-
- 2.3.1 链队列的实现——构造函数
- 2.3.2 链队列的实现——入队
- 2.3.3 链队列的实现——出队
- 2.4 循环队列和链队列的比较
- 三 .栈和队列完整代码实现
-
- 3.1 顺序栈类模板实现：
- 3.2 链队列的代码实现：
- 3.3 循环队列实现代码
- 3.4 顺序栈，两栈共享，链栈的应用
两种特殊的线性表——栈和队列: 【数据结构|数据结构（三）——详解栈和队列及完整代码实现】
? 从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。一.栈 1.1 栈的逻辑结构 栈的相关定义：
? 从抽象数据类型角度看，栈和队列是两种重要的抽象数据类型。
1.栈：限定仅在表的一端进行插入和删除操作的线性表。
2.允许插入和删除的一端称为栈顶，另一端称为栈底。
3.? 空栈：不含任何数据元素的栈。
文章图片
如上图所示，栈的插入和删除是有一定条件的，即栈顶的元素先出栈，下面的元素才能接着出，如果栈顶的元素 a 3 a3 a3没有出栈，那么下面的元素 a 2 、 a 1 a2、a1 a2、a1是不可能出栈的，就比如往弹夹里面压子弹一样，最上面的一发子弹没有射出去，下面的子弹自然不可能出去了——这就是栈的操作特性：后进先出
1.2 栈的顺序存储结构及实现 顺序栈是指栈的顺序存储结构，那么如何改造数组来实现栈的顺序存储呢？
文章图片
如上图所示，我们先确定用数组的哪一端表示栈底，假设我们用a[0]端作为栈底，附设指针top指示栈顶元素在数组中的位置。
文章图片
如果a2进栈的，就让top++，指向a2对应的位置
文章图片
a3进栈，就让top++，指向a3对应的位置，同理，如果a3出栈了，就让top–，这样就用数组来实现栈的顺序存储，当栈空的适合，就让top=-1，而栈满的适合，则让top=数组的最大值-1.
1.2.1 顺序栈的实现——入栈
实现代码如下：
template
voidseqStack ::Push ( DataTypex)
{
if (top == MAX_SIZE-1)throw“溢出”;
top++;
data[top] = x;
}
如果栈没有满的话，就让top++，然年把x压栈到数组中即可，而这两步可以合并为一步：
文章图片
1.2.2顺序栈的实现——出栈
template
DataTypeseqStack :: Pop ( )
{
if (top == -1)throw“溢出”;
x = data[top--];
returnx;
}
原理很简单，再此处不多说啦
1.2.3 两栈共享空间
如果在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈呢？
我们可以采用顺序栈单向延伸——使用一个数组来存储两个栈，即两栈共享空间：
使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。
文章图片
如上图所示，栈1的底固定在下标为0的一端；栈2的底固定在下标为StackSize-1的一端。
top1和top2分别为栈1和栈2的栈顶指针；Stack_Size为整个数组空间的大小（图中用S表示）；
当top1== -1时，栈1为空1.3 栈的链接存储结构及实现 同理，我们应该如何改造链表实现栈的链接存储呢？
当top2= =Stack_Size时，栈2为空
而当top2= =top1+1时，栈满
文章图片
如上图所示，我们将链头作为栈顶，方便操作；且链栈不需要附设头结点。
1.3.1 链栈的实现——入栈
文章图片
如上图所示，让入栈时，我们定义一个新的结点s，然后将x赋值给s的数据部分，然后让s的下一个结点指向top，再修改top指向新入栈的结点s即可。
实现代码如下：
template
void LinkStack ::Push(DataType x)
{
s = new Node;
s->data = https://www.it610.com/article/x;
s->next = top;
top = s;
}
1.3.2 链栈的实现——出栈
文章图片
同理，出栈时，我们先存入x的值便于返回，然后让栈顶指针p指向结点top，修改top，让他指向他的下一个结点，删除结点p即可。
实现代码如下：
template
DataType LinkStack ::Pop( )
{
if (top == NULL)
throw "下溢";
x = top->data;
p = top;
top = top->next;
delete p;
return x;
}
1.4 顺序栈和链栈的比较 时间性能：相同，都是常数时间O(1)。
空间性能：
? 顺序栈：有元素个数的限制和空间浪费的问题。总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。
? 链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。
二.队列 2.1 队列的逻辑结构 队列的相关定义：
1.队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。
2. 允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。
3. 空队列：不含任何数据元素的队列。
文章图片
如上图所示，队列的特性是先出先进，也就和我们排队是一个道理。
2.2 队列的顺序存储结构及实现 如何才能改造数组实现队列的顺序存储呢？
文章图片
如上图所示，我们设置队头、队尾两个指针，分别约定：让队头指针front指向队头元素的前一个位置，让队尾指针rear指向队尾元素。
文章图片
当a1、a2依次出队后，对头和队尾指针也跟着相应变化。
2.2.1 循环队列
假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。
文章图片
如上图所示，虽然0和1位置还空着，但由于rear指针已经到数组中下标最大的位置，便无法再插入了。
如何解决假溢出呢？
我们设置一个循环队列，将存储队列的数组头尾相接：
文章图片
这样就能让rear指向前面的元素位置了。
但循环队列并不存在物理的循环结构，用软件方法求模实现，比如上图：
我们求模：（4＋1）mod 5＝0即可让rear指向0位置了
当需要执行出队操作，出队完成后，front==rear时，就表示队空了：
文章图片
文章图片
而当front==rear时，也能表示队满：
文章图片
如何才能确定不同的队空、队满的判定条件？有三种方法：
方法一：附设一个存储队列中元素个数的变量num，
当num==0时队空，当num==QueueSize时为队满；
方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；
方法三：设置标志flag，当front==rear且flag==0时为队空，
当front==rear且flag==1时为队满。
文章图片
在此当(rear+1) mod QueueSize==front时为队满，当rear=front时队空
2.2.2 循环队列的实现——入队
文章图片
入队的适合，当(rear+1) % QueueSize与front相同时，就说明队满了，否则修改rear的指向，然后x赋值到rear对应的数组元素处即可。
实现代码如下：
template
void CirQueue ::EnQueue(DataType x)
{
if ((rear+1) % QueueSize == front) throw "上溢";
rear =(rear+1) % QueueSize;
data[rear] = x;
}
2.2.3 循环队列的实现——出队
文章图片
当a3进行出队操作时，当rear == front，表示队列为空，否则修改front的指向，返回data值即可，因为front指向的是队头元素的前一个位置。
代码实现如下：
template
DataType CirQueue ::DeQueue( )
{
if (rear == front) throw "下溢";
front = (front + 1) % QueueSize;
return data[front];
}
2.2.4 循环队列的实现——读队头元素
文章图片
实现代码如下：
template
DataType CirQueue ::GetQueue( )
{
if (rear == front) throw "下溢";
i = (front + 1) % QueueSize;
return data[i];
}
2.3 队列的链接存储结构及实现
文章图片
如上图所示，队头指针即为链表的头指针
2.3.1 链队列的实现——构造函数
文章图片
构造一个空链表，让队头和队尾指针都指向该结点即可
代码实现如下：
template
LinkQueue ::LinkQueue( )
{
front = new Node;
front->next = NULL;
rear = front;
}
2.3.2 链队列的实现——入队
文章图片
如上图所示，如果要插入结点s，那么让s的下一个结点为空，让rear的下一个结点指向s，再修改rear指向s即可
template
void LinkQueue ::EnQueue(DataType x)
{
s = new Node;
s->data = https://www.it610.com/article/x;
s->next = NULL;
rear->next = s;
rear = s;
}
2.3.3 链队列的实现——出队
文章图片
如上图所示，我们先让p结点为front的下一个结点，然后让front的下一个结点指向p的下一个结点，删除p结点即可
此处需要注意当队列中只有一个元素时，我们要让rear指向front，然后再删除p结点。
文章图片
代码实现如下：
template
DataType LinkQueue ::DeQueue( )
{
if (rear == front) throw "下溢";
p = front->next;
x = p->data;
front->next = p->next;
if (p->next == NULL)rear = front;
delete p;
return x;
}
2.4 循环队列和链队列的比较 时间性能:
? 循环队列和链队列的基本操作都需要常数时间O (1)。
空间性能:
? 循环队列：必须预先确定一个固定的长度，
所以有存储元素个数的限制和空间浪费的问题。
? 链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，
但是每个元素都需要一个指针域，从而产生了结构性开销。
三 .栈和队列完整代码实现 3.1 顺序栈类模板实现：
#include//cout,cin
#include"process.h"//exit()
#include"stdio.h"//EOF,NULL
//顺序栈类定义
template
class SqStack
{
private:
T*base;
//栈底指针
int top;
//栈顶
int stacksize;
//栈容量
public:
SqStack(int m);
//构建函数
~SqStack(){delete [] base;
top=-1;
stacksize=0;
}//析构函数
void Push(T x);
//入栈
T Pop();
//出栈
T GetTop();
//获取栈顶元素
int StackEmpty();
//测栈空
void ClearStack();
//清空栈
void StackTop();
//返回栈顶指针
void StackTranverse();
//显示栈中元素
};
//顺序栈类实现
template
SqStack::SqStack(int m)
{ base=new T[m];
if(base==NULL)
{
cout<<"栈创建失败，退出!"<
void SqStack::Push(T x)
{
if(top==stacksize-1) throw "栈满，无法入栈";
top++;
base[top]=x;
//cout<<"top："<
T SqStack::Pop()
{
T x;
if(top==-1) throw "栈空，不能出栈";
x=base[top--];
return x;
}template
T SqStack::GetTop()
{
if(top==-1)
throw "栈空，栈顶无元素";
return base[top];
}template
int SqStack::StackEmpty()
{
if(top==-1)
return 1;
else
return 0;
}template
void SqStack::ClearStack()
{
top=-1;
}template
void SqStack::StackTop()
{//返回栈顶指针
cout<<"栈顶top= "<
void SqStack::StackTranverse()
{
int i=top;
while(i>=0)
cout< s(10);
//建立容量为20、元素类型为整型的空栈
system("cls");
//执行系统命令cls，清屏
int choice;
do
{//显示主菜单
cout<<"1-元素入栈\n";
cout<<"2-元素出栈\n";
cout<<"3-取栈顶元素\n";
cout<<"4-置栈空\n";
cout<<"5-测栈空\n";
cout<<"6-显示栈元素\n";
cout<<"7-显示栈顶指针\n";
cout<<"8-退出\n";
cout<<"Enter choice:";
cin>>choice;
switch(choice)
{
case 1://入栈
cout<<"请输入插入元素的值:";
cin>>e;
//
cout< 3.2 链队列的代码实现：
# include
using namespace std;
template
struct Node{
DataType data;
Node *next;
};
template //在队列中同样有头结点;
class LinkQueue{
public:
LinkQueue();
~LinkQueue(){};
void EnQueue(DataType x);
DataType DeQueue();
DataType GetQueue();
int Empty(){ if(front==rear) return 1;
else return 0;
}
private:
Node *front,*rear;
};
template
LinkQueue ::LinkQueue()
{
Node *s;
s=new Node;
s->next=NULL;
front=rear=s;
}template //根据队列的性质，入队只能从队尾;
void LinkQueue::EnQueue(DataType x)
{
Node *s;
s=new Node;
s->next=NULL;
s->data=https://www.it610.com/article/x;
rear->next=s;
//在队的最后一个元素后面插入s
rear=s;
//将rear后移；指向队尾元素；
}template //根据队列的性质，出队只能从队头;
DataType LinkQueue::DeQueue()
{
if(front==rear) throw "下溢";
Node *p;
p=front->next;
int x=p->data;
front->next=p->next;
if(p->next==NULL) rear=front;
//判断出队前长度是否为1;
若为1 则使头尾指针相同;
delete p;
return x;
}template
DataType LinkQueue::GetQueue()
{
return front->next->data;
//注意这里不改变front的位置;
}int main()
{
LinkQueue a;
int b[6]={2,45,12,7,8,3};
for(int i=0;
i<5;
i++)
{ a.EnQueue(b[i]);
}
cout< 3.3 循环队列实现代码
#include//cout,cin
#include"process.h"//exit()
#include"stdio.h"//EOF,NULL
#include "iostream.h"
//循环队列类的定义
template
class CirQueue
{
private:
DataType *base;
// 存储空间基址
int front;
// 队头指针
int rear;
// 队尾指针
int queuesize;
// 队容量
public:
CirQueue(int m);
//构造空队列
~CirQueue();
// 析构函数，释放链队各结点的存储空间
void EnQueue(DataType x);
// 元素x入队
DataType DeQueue();
// 队顶元素出队
DataType GetHead();
// 取队头元素
DataType GetLast();
//取队尾元素
int QueueEmpty();
// 判队空
int QueueFull();
//判队满
void ClearQueue();
//清空队
void Pointer();
//返回队头、队尾位置
void QueueTranverse();
//遍历队，输出队列元素
};
//循环队列类的实现
template
CirQueue::CirQueue(int m)//构造函数
{//创建一空队
base=new DataType[m];
if(base==NULL)
{
cout<<"队创建失败，退出!"<
CirQueue::~CirQueue()//析构函数
{//释放队列所占存储空间
delete [] base;
rear=0;
front=0;
queuesize=0;
}template
void CirQueue::EnQueue(DataType x)
{//元素入队
if((rear+1)%queuesize==front) throw "上溢，无法入队";
base[rear]=x;
rear=(rear+1)%queuesize;
}template
DataType CirQueue::DeQueue()
{
DataType x;
if(front==rear) throw "下溢，不能出队";
x=base[front];
front=(front+1)%queuesize;
return x;
}template
DataType CirQueue::GetHead()
{
DataType x;
if(front==rear) throw "队空，队顶无元素";
x=base[front];
return x;
}template
DataType CirQueue::GetLast()
{
DataType x;
if(front==rear) throw "队空，队顶无元素";
x=base[rear-1];
return x;
}template
int CirQueue::QueueEmpty()
{
if(front==rear)
return 1;
else
return 0;
}template
int CirQueue::QueueFull()
{
if((rear+1)%queuesize==front)
return 1;
else
return 0;
}template
void CirQueue::ClearQueue()
{
front=rear=0;
}template
void CirQueue::Pointer()
{
cout<<"队头front= "<>choice;
switch(choice)
{
case 1://入队
cout<<"请输入插入元素的值:";
cin>>e;
//
cout< 实验截图如下：
文章图片
3.4 顺序栈，两栈共享，链栈的应用
#include
using namespace std;
//栈
const int StackSize=100;
template
class SeqStack
{
public:
SeqStack(){top=-1;
}
~SeqStack(){}
void Push(DataType x);
DataType Pop();
DataType GetTop(){if(top!=-1) return data[top];
}
int Empty()
{
if(top==-1)return 1;
else return 0;
}
//private:
DataType data[StackSize];
int top;
};
template//顺序栈入栈算法
void SeqStack::Push(DataType x)
{
if(top==StackSize-1)throw"上溢";
data[++top]=x;
}
template//顺序栈出栈算法
DataType SeqStack::Pop()
{
if(top==-1)throw"下溢";
DataType x=data[top--];
return x;
}//两栈共享空间
template
class BothStack
{
public:
BothStack(){top1=-1;
top2=StackSize;
}
~BothStack(){}
void Push(int i,DataType);
DataType Pop(int i);
DataType GetTop(int i);
int Empty(int i);
private:
DataType data[StackSize];
int top1,top2;
};
template//两栈共享空间入栈算法
void BothStack::Push(int i,DataType x)
{
if(top1==top2-1)throw"上溢";
if(i==1)data[++top1]=x;
if(i==2)data[--top2]=x;
}
template//出栈算法
DataType BothStack::Pop(int i)
{
if(i==1){
if(top1==-1)throw"下溢";
return data[top1--];
}
if(i==2){
if(top2==StackSize)throw"下溢";
return data[top2++];
}
}
template//取栈顶元素
DataType BothStack::GetTop(int i)
{
if(i==1){ if(top1!=-1) return data[top1];
}
if(i==2){ if(top2!=-1) return data[top2];
}
}
template//判空操作
int BothStack::Empty(int i)
{
if(i==1)
{
if(top1==-1)
{
cout<<"栈1空"<
struct Node
{
DataType data;
Node *next;
};
template
class LinkStack
{
public:
LinkStack(){top=NULL;
}
~LinkStack(){};
void Push(DataType x);
DataType Pop();
DataType GetTop(){if(top!=NULL)return top->data;
}
int Empty();
private:
Node *top;
};
template//链栈入栈算法
void LinkStack::Push(DataType x)
{
Node *s;
s=new Node;
s->data=https://www.it610.com/article/x;
s->next=top;
top=s;
}
template//链栈出栈算法
DataType LinkStack::Pop()
{
Node *p;
p=new Node;
if(top==NULL)throw"下溢";
DataType x=top->data;
p=top;
top=top->next;
delete p;
return x;
}
template//判空操作
int LinkStack::Empty()
{
if(top==NULL)
{
cout<<"栈为空"< i1;
//创建顺序栈i1
cout<<"top="< i2;
//创建两栈共享的栈i2
i2.Push(1,'c');
i2.Push(1,'b');
i2.Push(1,'a');
//向1中压入c，b，a
i2.Push(2,'C');
i2.Push(2,'B');
i2.Push(2,'A');
//向2中压入C,B,A
cout<<"栈1的栈顶元素是:"< i3;
//创建链栈i3
i3.Push(3);
i3.Push(2);
i3.Push(1);
//依次压入3,2,1
cout<<"i3的栈顶元素是:"< 
文章图片
推荐阅读
- 初阶数据结构|数据结构栈和队列详解（C语言实现）
- 无监督的人工神经网络算法和技术
- Android版数据结构与算法（二叉排序树）
- 操作系统|LRU算法（JAVA实现）
- 数据结构|数组模拟队列
- Java数据结构|【浅学Java数据结构】简单模拟实现双向链表
- 算法|leetcode刷题（链表03 （反转链表））
- #|LeetCode 209. 长度最小的子数组（中等、数组）day23
- SIT742 数据分析