【C++】stack和queue

发布于：2024-08-21 ⋅ 阅读:(68) ⋅ 点赞:(0)

📢博客主页：https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨

在这里插入图片描述

在这里插入图片描述

文章目录

🏳️‍🌈1.stack的介绍和使用

栈是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出（Last In First Out，LIFO）的原则存储数据。打个比方，栈就像一摞盘子，只能从最上面取盘子（删除）或者往最上面放盘子（插入）。
在这里插入图片描述
在这里插入图片描述

❤️最小栈的实现

在这里插入图片描述

class MinStack
{
	public :
	void push(int x)
	{
		// 只要是压栈，先将元素保存到_elem中
		_elem.push(x);
		// 如果x小于_min中栈顶的元素，将x再压入_min中
		if (_min.empty() || x <= _min.top())
			_min.push(x);
	} v	oid pop()
	{
		// 如果_min栈顶的元素等于出栈的元素，_min顶的元素要移除
		if (_min.top() == _elem.top())
			_min.pop();
		_elem.pop();
	} i
		nt top() { return _elem.top(); }
	int getMin() { return _min.top(); }
private:
	// 保存栈中的元素
	std::stack<int> _elem;
	// 保存栈的最小值
	std::stack<int> _min;
};

一、整体结构
这段代码定义了一个名为MinStack的类，用于实现一个具有获取最小元素功能的栈。这个类使用了 C++ 标准库中的std::stack容器来存储栈中的元素和最小元素。

二、成员函数分析
push(int x)函数：
首先，无论什么情况，将元素x压入_elem栈中，这个栈用于存储所有的元素。
接着，判断_min栈是否为空或者x是否小于等于_min栈顶元素。如果满足条件，说明x可能是当前栈中的最小元素，将x压入_min栈中。这样，_min栈始终保持着当前栈中最小元素在栈顶的状态。

pop()函数：
当执行出栈操作时，先判断_min栈顶元素是否等于_elem栈顶元素。如果相等，说明当前要出栈的元素就是当前栈中的最小元素，那么同时将_min栈顶元素也出栈。
最后，无论什么情况，都将_elem栈顶元素出栈。

top()函数：
这个函数很简单，直接返回_elem栈的栈顶元素，用于获取当前栈顶的元素值。

getMin()函数：
返回_min栈的栈顶元素，由于_min栈始终保持着最小元素在栈顶，所以这个函数可以快速获取当前栈中的最小元素。

🧡栈的弹出压入序列

在这里插入图片描述

class Solution {
public:
	bool IsPopOrder(vector<int> pushV, vector<int> popV) {
		//入栈和出栈的元素个数必须相同
		if (pushV.size() != popV.size())
			return false;
		// 用s来模拟入栈与出栈的过程
		int outIdx = 0;
		int inIdx = 0;
		stack<int> s;
		while (outIdx < popV.size())
		{
			// 如果s是空，或者栈顶元素与出栈的元素不相等，就入栈
			while (s.empty() || s.top() != popV[outIdx])
			{
				if (inIdx < pushV.size())
					s.push(pushV[inIdx++]);
				else
					return false;
			} /	/ 栈顶元素与出栈的元素相等，出栈
				s.pop();
			outIdx++;
		} return true;
	}
};

一、整体功能
这段 C++ 代码的目的是判断给定的两个整数向量pushV和popV是否可能是一个栈的入栈和出栈序列。

二、函数分析
首先检查两个输入向量的大小是否相等，如果不相等则直接返回false，因为入栈和出栈的元素个数必须相同。

然后使用一个while循环来模拟入栈和出栈的过程：

  1. 内部又有一个while循环，当栈s为空或者栈顶元素与当前要出栈的元素（popV[outIdx]）不相等时，进行入栈操作。
  2. 只要入栈索引inIdx小于pushV的大小，就将pushV[inIdx]入栈，并将inIdx递增。
  3. 如果入栈索引已经超出pushV的范围，说明无法再进行入栈操作但仍然没有找到与出栈序列匹配的元素，此时返回false。
  4. 当栈顶元素与当前要出栈的元素相等时，将栈顶元素出栈，并将出栈索引outIdx递增。
    如果整个循环顺利执行完毕，说明输入的两个序列可能是一个栈的入栈和出栈序列，返回true。

💛stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

#include<vector>
namespace bite
{
	template<class T>
	class stack
	{
	public:
		stack() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_back(); }
		T& top() { return _c.back(); }
		const T& top()const { return _c.back(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		std::vector<T> _c;
	};
}

🏳️‍🌈2.queue的介绍和使用

  1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

  2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供-组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

  3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push back:在队列尾部入队列
  • pop front:在队列头部出队列

4.标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
在这里插入图片描述
在这里插入图片描述

❤️用队列实现栈

在这里插入图片描述

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc newnode fail");
	}
	newnode->val = x;
	newnode->next = NULL;

	if (pq->ptail == NULL)
	{
		pq->phead = newnode;
		pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
	
}
// 队头删除
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);

	if (pq->size == 1)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

// 取队头和队尾的数据
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
        QueuePush(&obj->q2,x);
}

int myStackPop(MyStack* obj) {
    Queue* empty = &obj->q1;
    Queue* notempty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        notempty = &obj->q1;
    }

    while(QueueSize(notempty) > 1)
    {
        QueuePush(empty, QueueFront(notempty));
        QueuePop(notempty);
    }
    int top = QueueFront(notempty);
    QueuePop(notempty);

    return top;
}

int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else{
        return QueueBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    return (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2));
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

🧡queue的模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实
现queue，具体如下:

#include <list>
namespace bite
{
	template<class T>
	class queue
	{
	public:
		queue() {}
		void push(const T& x) { _c.push_back(x); }
		void pop() { _c.pop_front(); }
		T& back() { return _c.back(); }
		const T& back()const { return _c.back(); }
		T& front() { return _c.front(); }
		const T& front()const { return _c.front(); }
		size_t size()const { return _c.size(); }
		bool empty()const { return _c.empty(); }
	private:
		std::list<T> _c;
	};
}

👥总结

本篇博文对 stack和queue 做了一个较为详细的介绍，不知道对你有没有帮助呢

觉得博主写得还不错的三连支持下吧！会继续努力的~

请添加图片描述

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布