31.STL中stack和queue的实现

1.STL中stack

1.栈的概念

栈（Stack）是一种数据结构，它遵循后进先出（Last-In-First-Out，LIFO）的原则，也就是说，最后进入栈的元素最先被取出。栈是一种线性数据结构，它由多个元素组成，每个元素被称为栈项（stack item），栈顶（top）是指最后一个被压入栈的元素，栈底（bottom）是指第一个被压入栈的元素。

栈的基本操作包括：

push（入栈）：将一个元素压入栈顶。
pop（出栈）：将栈顶的元素弹出，并返回它。
peek（查看栈顶元素）：查看但不弹出栈顶元素。
isEmpty（判断栈是否为空）：判断栈是否为空。
size（获取栈的大小）：获取栈中元素的个数。

栈可以用于许多场景，例如函数调用、括号匹配、逆波兰表达式求值等。

2.栈的算法实现

栈数据结构的定义

#define MaxSize 128 //预先分配空间，这个数值根据实际需要预估确定
typedef int ElemType;
typedef struct _SqStack 
{
	ElemType* base; //栈底指针
	ElemType* top; //栈顶指针
}SqStack;

栈的初始化

入栈
入栈操作：判断是否栈满，如果栈已满，则入栈失败，否则将元素放入栈顶，栈顶指针向上移动一个空间（top++）。

出栈
出栈操作: 和入栈相反，出栈前要判断是否栈空，如果栈是空的，则出栈失败，否则将栈顶元素暂存给一个变量，栈顶指针向下移动一个空间（top--）。

bool PopStack(SqStack& S, ElemType& e)//删除S的站顶元素，攒存在变量e中
{
	if (S.base == S.top)//空栈
	{
		return false;
	}

	e = *(--S.top);//栈顶指针减1，将栈顶元素赋给e

	return true;
}

获取栈顶元素
取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一份，栈的元素个数不变，而出栈是指栈顶元素取出，栈内不再包含这个元素。

//获取栈顶元素
ElemType GetTop(SqStack& S)//返回S的栈顶元素，栈顶指针不变
{
	if (S.top != S.base)//栈非空
		return *(S.top - 1);//返回栈顶元素的值，栈顶指针不变
	else
		return -1;
}

//更优的版本  可以使用自定义类型
bool GetTop1(SqStack& S, ElemType& e)//返回S的栈顶元素，栈顶指针不变
{
	if (S.top != S.base)//栈非空
	{
		e = *(S.top - 1);//返回栈顶元素的值，栈顶指针不变
		return true;
	}
	else
	{
		return false;
	}
}

判断空栈

bool IsEmpty(SqStack& S)//判断栈是否为空
{
	if (S.top == S.base)
		return true;
	else
		return false;
}

获取栈顶元素

int GetSize(SqStack& S) {//返回栈中元素个数
	return (S.top - S.base);
}

销毁栈

void DestroyStack(SqStack& S)//销毁栈
{
	if (S.base)
	{
		free(S.base);
		S.base = NULL;
		S.top = NULL;
	}
}

完整代码：

#define _CRT_SECURE_NO_WARNINGS
#include <Windows.h>
#include <iostream>
#include <stdlib.h>
using namespace std;

#define MaxSize 128 //预先分配空间，这个数值根据实际需要预估确定
typedef int ElemType;
typedef struct _SqStack 
{
	ElemType* base; //栈底指针
	ElemType* top; //栈顶指针
}SqStack;

bool InitStack(SqStack& S)//构造一个空栈
{
	S.base = new ElemType[MaxSize];//为顺序栈分配一个最大容量为MaxSize的空间
	if (!S.base)//空间分配失败
		return false;
	S.top = S.base;//top初始化为base
	return true;
}

bool PushStack(SqStack& S, ElemType e)//插入元素e为新的栈顶元素
{
	if ((S.top - S.base) == MaxSize)//栈满
		return false;

	*(S.top++) = e;//元素e压入栈顶，然后栈顶指针加1，等价于*S.top = e; S.top++;

	return true;

}

bool PopStack(SqStack& S, ElemType& e)//删除S的站顶元素，攒存在变量e中
{
	if (S.base == S.top)//空栈
	{
		return false;
	}

	e = *(--S.top);//栈顶指针减1，将栈顶元素赋给e

	return true;
}

//获取栈顶元素
ElemType GetTop(SqStack& S)//返回S的栈顶元素，栈顶指针不变
{
	if (S.top != S.base)//栈非空
		return *(S.top - 1);//返回栈顶元素的值，栈顶指针不变
	else
		return -1;
}

//更优的版本  可以使用自定义类型
bool GetTop1(SqStack& S, ElemType& e)//返回S的栈顶元素，栈顶指针不变
{
	if (S.top != S.base)//栈非空
	{
		e = *(S.top - 1);//返回栈顶元素的值，栈顶指针不变
		return true;
	}
	else
	{
		return false;
	}
}

bool IsEmpty(SqStack& S)//判断栈是否为空
{
	if (S.top == S.base)
		return true;
	else
		return false;
}

void DestroyStack(SqStack& S)//销毁栈
{
	if (S.base)
	{
		free(S.base);
		S.base = NULL;
		S.top = NULL;
	}
}

int GetSize(SqStack& S) {//返回栈中元素个数
	return (S.top - S.base);
}

int main()
{
	int n, x;
	SqStack S;
	InitStack(S);//初始化一个顺序栈
	cout << "请输入元素个数n：" << endl;
	cin >> n;
	cout << "请依次输入n个元素，依次入栈：" << endl;
	while (n--)
	{
		cin >> x; //输入元素
		PushStack(S, x);
	}

	cout << "元素依次出栈：" << endl;
	while (!IsEmpty(S))//如果栈不空，则依次出栈
	{
		cout << GetTop(S) << "\t";//输出栈顶元素
		PopStack(S, x); //栈顶元素出栈
	}
	cout << endl;

	DestroyStack(S);
	system("pause");
	return EXIT_SUCCESS;
}

参考资料来源：

奇牛学院

2.STL中stack和queue的实现

1.队列的概念

1.1队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。

1.2队列的常见基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。
QueueIsEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
QueueIsFull(Q)：判队列满，若队列Q为满返回true，否则返回false。
PrintQueue(Queue* Q)：打印队列中的各元素
EnQueue(&Q, x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)：出队，若队列Q非空，删除队头元素，并用x返回。
ClearQueue(Queue* Q)：清空队列
GetHead(Q, &x)：读队头元素，若队列Q非空，则将队头元素赋值给x。

————————————————
版权声明：本文为CSDN博主「UniqueUnit」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/Real_Fool_/article/details/113852222

2.队列的顺序存储

采用数组来保存队列的元素，设立一个队首指针front，一个队尾指针rear，分别指向队首和队尾元素。则
rear-front 即为存储的元素个数！

2.1队列定义

#define MaxSize 5 //队列的最大容量
typedef int DataType; //队列中元素类型
typedef struct Queue
{
    DataType queue[MaxSize];
    int front; //队头指针
    int rear; //队尾指针
}SeqQueue;

2.2队列初始化

//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue *SQ)
{
    if(!SQ) return;
    SQ->front = SQ->rear = 0;//把对头和队尾指针同时置0
}

2.3队列为空

//判断队列为空
int IsEmpty(SeqQueue *SQ)
{
    if(!SQ) return 0;
    if (SQ->front == SQ->rear)
    {
        return 1;
    }
    return 0;
}

2.4队列为满

//判断队列是否为满
int IsFull(SeqQueue *SQ)
{
    if(!SQ) return 0;
    if (SQ->rear == MaxSize)
    {
        return 1;
    }
    return 0;
}

2.5入队

//入队,将元素data 插入到队列SQ 中
int EnterQueue( SeqQueue *SQ, DataType data)
{
    if(!SQ) return 0;
    if(IsFull(SQ))
    {
        cout<<"无法插入元素"<<data<<", 队列已满!"<<endl;
        return 0;
    }
    SQ->queue[SQ->rear] = data; //在队尾插入元素data
    SQ->rear++; //队尾指针后移一位
    return 1;
}

2.6打印队列中的元素

//打印队列中的各元素
void PrintQueue(SeqQueue* SQ)
{
    if(!SQ) return ;
    int i = SQ->front;
    while(i<SQ->rear)
    {
        cout<<setw(4)<<SQ->queue[i];
        i++;
    }
    cout<<endl;
}

2.7出队

方式 1 - 删除 front 所指的元素, 后面所有元素前移 1 并返回被删除元素

//出队，将队列中队头的元素data 出队，后面的元素向前移动
int DeleteQueue(SeqQueue* SQ, DataType *data)
{
    if(!SQ || IsEmpty(SQ))
    {
        cout<<"队列为空！"<<endl;
        return 0;
    }
    if(!data) return 0;
    *data = SQ->queue[SQ->front];
    for(int i=SQ->front+1; i<SQ->rear; i++)//移动后面的元素
    {
        SQ->queue[i-1]=SQ->queue[i];
    }
    SQ->rear--;//队尾指针前移一位
    return 1;
}

方式 2 - 删除 front 所指的元素，然后加 1 并返回被删元素。8979438401111

//出队，将队列中队头的元素data 出队，出队后队头指针front 后移一位
int DeleteQueue2(SeqQueue* SQ,DataType* data)
{
    if (!SQ || IsEmpty(SQ))
    {
        cout<<"队列为空！"<<endl;
        return 0;
    }
    if(SQ->front>=MaxSize)
    {
        cout<<"队列已到尽头!"<<endl;
        return 0;
    }
    *data = SQ->queue[SQ->front]; //出队元素值
    SQ->front = (SQ->front)+1; //队首指针后移一位
    return 1;
}

2.8取队首元素：返回front 指向的元素值

//获取队首元素
int GetHead(SeqQueue* SQ,DataType* data)
{
    if (!SQ || IsEmpty(SQ))
    {
        cout<<"队列为空!"<<endl;
    }
    return *data = SQ->queue[SQ->front];
}

2.9清空队列

//清空队列
void ClearQueue(SeqQueue* SQ)
{
    SQ->front = SQ->rear = 0;
}

2.10获取队列长度

//获取队列中元素的个数
int getLength(SeqQueue* SQ)
{
    if(!SQ) return 0;
    return SQ->rear-SQ->front;
}

完整代码

#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>

using namespace std;

#define MaxSize 5 //队列的最大容量

typedef int DataType; //队列中元素类型

typedef struct Queue
{
    DataType queue[MaxSize];
    int front; //队头指针
    int rear; //队尾指针
}SeqQueue;

//队列初始化，将队列初始化为空队列
void InitQueue(SeqQueue* SQ)
{
    if (!SQ) return;
    SQ->front = SQ->rear = 0; //把对头和队尾指针同时置0
}

//判断队列为空
int IsEmpty(SeqQueue* SQ)
{
    if (!SQ) return 0;
    if (SQ->front == SQ->rear)
    {
        return 1;
    }
    return 0;
}

//判断队列是否为满
int IsFull(SeqQueue* SQ)
{
    if (!SQ) return 0;
    if (SQ->rear == MaxSize)
    {
        return 1;
    }
    return 0;
}

//入队,将元素data 插入到队列SQ 中
int EnterQueue(SeqQueue* SQ, DataType data) 
{
    if (!SQ) return 0;

    if (IsFull(SQ))
    {
        cout << "无法插入元素" << data << ", 队列已满!" << endl;
        return 0;
    }

    SQ->queue[SQ->rear] = data; //在队尾插入元素data
    SQ->rear++; //队尾指针后移一位

    return 1;
}

//出队，将队列中队头的元素data 出队，后面的元素向前移动
int DeleteQueue(SeqQueue * SQ, DataType * data) 
{
    if (!SQ || IsEmpty(SQ)) 
    {
        cout << "队列为空！" << endl;
        return 0;
    }

    if (!data) return 0;

    *data = SQ->queue[SQ->front];
    for (int i = SQ->front + 1; i < SQ->rear; i++)//移动后面的元素 
    {
        SQ->queue[i - 1] = SQ->queue[i];
    }
    SQ->rear--;//队尾指针前移一位

    return 1;
}

//出队，将队列中队头的元素data 出队，出队后队头指针front 后移一位
int DeleteQueue2(SeqQueue* SQ, DataType* data)
{
    if (!SQ || IsEmpty(SQ))
    {
        cout << "队列为空！" << endl;
        return 0;
    }

    if (SQ->front >= MaxSize) 
    {
        cout << "队列已到尽头!" << endl;
        return 0;
    }

    *data = SQ->queue[SQ->front]; //出队元素值
    SQ->front = (SQ->front) + 1; //队首指针后移一位
    return 1;
}
//打印队列中的各元素
void PrintQueue(SeqQueue* SQ)
{
    if (!SQ) return;

    int i = SQ->front; 
    while (i < SQ->rear)
    {
        cout << setw(4) << SQ->queue[i];
        i++;
    }
    cout << endl;
}

//获取队首元素，不出队
int GetHead(SeqQueue* SQ, DataType* data)
{
    if (!SQ || IsEmpty(SQ))
    {
        cout << "队列为空!" << endl;
    }
    return *data = SQ->queue[SQ->front];
}

//清空队列
void ClearQueue(SeqQueue* SQ)
{
    if (!SQ) return;
    SQ->front = SQ->rear = 0;
}

//获取队列中元素的个数
int getLength(SeqQueue* SQ)
{
    if (!SQ) return 0;
    return SQ->rear - SQ->front;
}

int main()
{
    SeqQueue* SQ = new SeqQueue;
    DataType data = -1;

    //初始化队列
    InitQueue(SQ);

    //入队
    for (int i = 0; i < 7; i++) 
    {
        EnterQueue(SQ, i);
    }
    //打印队列中的元素
    printf("队列中的元素(总共%d 个)：", getLength(SQ));
    PrintQueue(SQ);
    cout << endl;
    //出队
    for(int i=0; i<10; i++)
    {
        if (DeleteQueue2(SQ, &data))
        {
            cout << "出队的元素是：" << data << endl;
        }
        else
        {
        cout << "出队失败！" << endl;
        }
    }

    //打印队列中的元素
    printf("出队一个元素后，队列中剩下的元素：");
    PrintQueue(SQ);
    cout << endl;

    system("pause");
    return 0;
}

3.队列的链式存储

队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列。为了
操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点

3.1队列的定义

#define MaxSize 5 //队列的最大容量
typedef int DataType;//队列中元素的类型

typedef struct _QNode//结点结构
{
	DataType data;
	struct _QNode* next;
}QNode;

typedef QNode* QueuePtr;

typedef struct Queue
{
	int length;//队列的长度
	QueuePtr front;//队头指针
	QueuePtr rear;//队尾指针
}LinkQueue;

3.2队列初始化

//队列初始化，将队列初始化为空队列
void InitQueue(LinkQueue* LQ)
{
	if (!LQ) return;

	LQ->length = 0;
	LQ->front = LQ->rear = NULL;//把队头指针和队尾指针同时置0
}

3.3判断队列是否为空

//判断队列为空
int IsEmpty(LinkQueue *LQ)
{
	if (!LQ) return 0;

	if (LQ->front == NULL)
	{
		return 1;
	}
	return 0;
}

3.4判断队列是否为满

//判断队列是否为满
int IsFull(LinkQueue* LQ)
{
	if (!LQ) return 0;

	if (LQ->length == MaxSize)
	{
		return 1;
	}
	return 0;
}

3.5入队

空队列时，front 和rear 都指向空。

//入队,将元素data 插入到队列LQ 中
int EnterQueue(LinkQueue* LQ, DataType data)
{
	if (!LQ) return 0;

	if (IsFull(LQ))
	{
		cout << "队列无法插入元素" << data << "，队列已满" << endl;
		return 0;
	}

	//创建结点
	QNode* qNode = new QNode;
	qNode->data = data;
	qNode->next = NULL;

	if (IsEmpty(LQ))//空队列
	{
		LQ->front = LQ->rear = qNode;
	}
	else
	{
		LQ->rear->next = qNode;//在队尾插入结点qNode
		LQ->rear = qNode;//队尾指向新插入的结点
	}
	LQ->length++;

	return 1;
}

3.6删除结点

//出队，将队列中队头的元素data出队，后面的元素向前移动
int DeleteQueue(LinkQueue* LQ, DataType* data)
{
	QNode* tmp = NULL;

	if (!LQ || IsEmpty(LQ))
	{
		cout << "队列为空" << endl;
		return 0;
	}

	if (!data) 
		return 0;

	tmp = LQ->front;

	LQ->front = tmp->next;
	if (!LQ->front) 
		LQ->rear = NULL;//如果队头出列后不存在其他元素，则rear结点也要置空

	*data = tmp->data;
	LQ->length--;

	delete tmp;//配合入队时用了new

	return 1;
}

3.7获取队首元素

//获取队首元素，不出队
int GetHead(LinkQueue* LQ, DataType* data)
{
	if (!LQ || IsEmpty(LQ))
	{
		cout << "队列为空！" << endl;
		return 0;
	}

	if (!data) return 0;

	*data = LQ->front->data;
	return 1;
}

3.8清空队列

//清空队列
void ClearQueue(LinkQueue* LQ)
{
	if (!LQ) return;

	while (LQ->front)
	{
		QueuePtr tmp = LQ->front->next;
		delete LQ->front;
		LQ->front = tmp;
	}
	LQ->front = LQ->rear = NULL;
	LQ->length = 0;
}

3.9获取队列中元素个数

//获取队列中元素的个数
int getLength(LinkQueue* LQ)
{
	if (!LQ) return 0;
	
	return LQ->length;
}

3.10打印队列中的元素

//打印队列中的各元素
void PrintQueue(LinkQueue *LQ)
{ 
    QueuePtr tmp;
    if(!LQ) return ;
    if(LQ->front==NULL)
    {
        cout<<"队列为空！";
        return ;
    }
    tmp = LQ->front;
    while(tmp)
    {
        cout<<setw(4)<<tmp->data;
        tmp = tmp->next;
    }
    cout<<endl;
}

完整代码

#include <stdio.h>
#include <assert.h>
#include <Windows.h>
#include <iostream>
#include <iomanip>

using namespace std;

#define MaxSize 5 //队列的最大容量
typedef int DataType; //队列中元素类型

typedef struct _QNode//结点结构
{ 
	DataType data;
	struct _QNode* next;
}QNode;

typedef QNode* QueuePtr;

typedef struct Queue
{
	int length; //队列的长度
	QueuePtr front; //队头指针
	QueuePtr rear; //队尾指针
}LinkQueue;

//队列初始化，将队列初始化为空队列
void InitQueue(LinkQueue* LQ)
{
	if (!LQ) return;
	LQ->length = 0;
	LQ->front = LQ->rear = NULL; //把对头和队尾指针同时置0
}

//判断队列为空
int IsEmpty(LinkQueue* LQ)
{
	if (!LQ) return 0;
	if (LQ->front == NULL)
	{
		return 1;
	}
	return 0;
}

//判断队列是否为满
int IsFull(LinkQueue* LQ)
{
	if (!LQ) return 0;
	if (LQ->length == MaxSize)
	{
		return 1;
	}
	return 0;
}

//入队,将元素data 插入到队列LQ 中
int EnterQueue(LinkQueue* LQ, DataType data) 
{
	if (!LQ) return 0;
	if (IsFull(LQ)) 
	{
		cout << "无法插入元素" << data << ", 队列已满!" << endl;
		return 0;
	}
	QNode* qNode = new QNode;
	qNode->data = data;
	qNode->next = NULL;
	if (IsEmpty(LQ))//空队列
	{
		LQ->front = LQ->rear = qNode;
	}
	else
	{
		LQ->rear->next = qNode;//在队尾插入节点qNode
		LQ->rear = qNode; //队尾指向新插入的节点
	}
	LQ->length++;
	return 1;
}

//出队，将队列中队头的元素出队，其后的第一个元素成为新的队首
int DeleteQueue(LinkQueue* LQ, DataType* data) {
	QNode* tmp = NULL;
	if (!LQ || IsEmpty(LQ)) 
	{
		cout << "队列为空！" << endl;
		return 0;
	}

	if (!data) return 0;

	tmp = LQ->front;
	LQ->front = tmp->next;
	if (!LQ->front) LQ->rear = NULL;//如果对头出列后不存在其他元素，则rear节点也要置空
		* data = tmp->data;
	LQ->length--;
	delete tmp;

	return 1;
}

//打印队列中的各元素
void PrintQueue(LinkQueue* LQ)
{
	QueuePtr tmp;

	if (!LQ) return;

	if (LQ->front == NULL) 
	{
		cout << "队列为空！";
		return;
	}

	tmp = LQ->front;

	while (tmp)
	{
		cout << setw(4) << tmp->data;
		tmp = tmp->next;
	}
	cout << endl;
}

//获取队首元素，不出队
int GetHead(LinkQueue* LQ, DataType* data)
{
	if (!LQ || IsEmpty(LQ))
	{ 
		cout << "队列为空!" << endl;
		return 0;
	}

	if (!data) return 0;

	*data = LQ->front->data;

	return 1;
}

//清空队列
void ClearQueue(LinkQueue* LQ)
{
	if (!LQ) return;
	while (LQ->front) 
	{
		QueuePtr tmp = LQ->front->next;
		delete LQ->front;
		LQ->front = tmp;
	}

	LQ->front = LQ->rear = NULL;
	LQ->length = 0;
}

//获取队列中元素的个数
int getLength(LinkQueue* LQ) 
{
	if (!LQ) return 0;
	return LQ->length;
}

int main()
{
	LinkQueue* LQ = new LinkQueue;
	DataType data = -1;
	//初始化队列
	InitQueue(LQ);
	//入队
	for (int i = 0; i < 7; i++) {
		EnterQueue(LQ, i);
	}
	//打印队列中的元素
	printf("队列中的元素(总共%d 个)：", getLength(LQ)); 
	PrintQueue(LQ);
	cout << endl;

	//出队
	for(int i=0; i<10; i++)
	{
		if (DeleteQueue(LQ, &data)) 
		{
			cout << "出队的元素是：" << data << endl;
		}
		else 
		{	
			cout << "出队失败！" << endl;
		}
	}

	//打印队列中的元素
	printf("出队一个元素后，队列中剩下的元素[%d]：", getLength(LQ));
	PrintQueue(LQ);
	cout << endl;

	ClearQueue(LQ);
	cout << "清空队列!\n";
	PrintQueue(LQ);

	//清理资源
	delete LQ;
	system("pause");
	return 0;
}

参考资料来源：

奇牛学院

本栏目推荐文章
• hard_stack
• String 类和 STL (Standard Template Library)
• pandas单独设一个新列，譬如从2023-11-1到2023-11-31怎么搞法？
• 31-Scala-模式匹配
• 写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。 数据范围：保证结果在 1 \le n \le 2^{31}-1 \1≤n≤2 31 −1
• BACK Stack会成为平台工程的新趋势吗？
• R语言用LOESS(局部加权回归)季节趋势分解（STL）进行时间序列异常检测
• 1 Queue Sort
• 即时通讯技术文集（第31期）：IM开发综合技术合集(Part4) [共13篇]
• 常用容器：动态数组array、列表list、队列 queue、map或字典、 集合、栈等等

stack queue STL 31stack queue stl 31 deque stack queue stl stack_queue linkedlist queue stack lt stack queue stack_queue 20231110 stack queue queue stack java 容器 底层stack queue 底层 容器stack queue priority_queue priority queue stl