📢博客主页：https://blog.csdn.net/2301_779549673

📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！

📢本文由 JohnKi 原创，首发于 CSDN🙉

📢未来很长，值得我们全力奔赴更美好的生活✨

文章目录

🏳️‍🌈1.stack的介绍和使用❤️最小栈的实现🧡栈的弹出压入序列💛stack的模拟实现

🏳️‍🌈2.queue的介绍和使用❤️用队列实现栈🧡queue的模拟实现

👥总结

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

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

❤️最小栈的实现

<code>class MinStack

{ -- -->

public :

void push(int x)

{

// 只要是压栈，先将元素保存到_elem中

_elem.push(x);

// 如果x小于_min中栈顶的元素，将x再压入_min中

if (_min.empty() || x <= _min.top())

_min.push(x);

} void 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栈始终保持着最小元素在栈顶，所以这个函数可以快速获取当前栈中的最小元素。

🧡栈的弹出压入序列

<code>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循环来模拟入栈和出栈的过程：

内部又有一个while循环，当栈s为空或者栈顶元素与当前要出栈的元素（popV[outIdx]）不相等时，进行入栈操作。只要入栈索引inIdx小于pushV的大小，就将pushV[inIdx]入栈，并将inIdx递增。如果入栈索引已经超出pushV的范围，说明无法再进行入栈操作但仍然没有找到与出栈序列匹配的元素，此时返回false。当栈顶元素与当前要出栈的元素相等时，将栈顶元素出栈，并将出栈索引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的介绍和使用

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

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

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

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

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

❤️用队列实现栈

<code>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 做了一个较为详细的介绍，不知道对你有没有帮助呢

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