文章目录

📝stack的介绍和使用🌠 stack的使用🌉stack的模拟实现

🌠 queue的介绍和使用🌉queue的介绍🌉 queue的使用

🌠queue的模拟实现🚩总结

📝stack的介绍和使用

stack官网文档链接：https://legacy.cplusplus.com/reference/stack/stack/?kw=stack

stack是一种容器适配器，专门用在具有后进先出的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。

stack是作为容器适配器被发现的，容器适配器就是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将其特定类作为最底层的，元素特定容器的尾部（即栈顶）被压入和弹出。

stack的底层容器可以是任何标准的容器类模版或者一些其他特定的容器类，这些容器应该支持以下的操作

empty：判空操作back：获取尾部元素操作push_back：尾部插入元素操作<code>pop_back：尾部删除元素操作

标准容器vector，deque，list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque.

🌠 stack的使用

例题：

最小栈：https://leetcode.cn/problems/min-stack/

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();

}

int top() { return _elem.top(); }

int getMin() { return _min.top(); }

private:

// 保存栈中的元素

std::stack<int> _elem;

// 保存栈的最小值

std::stack<int> _min;

};

栈的压入、弹出序列：https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

class Solution {

public:

bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {

// write code here

if(pushV.size() != popV.size())

{

return false;

}

//辅助栈

stack<int> in;

int n = pushV.size();

//遍历进栈下标

int i = 0;

//遍历出栈对比顺序下标

for(int j = 0; j < n; ++j)

{

//i是否遍历完

//辅助栈为空

//栈顶不等于出栈元素

while(i < n && (in.empty() || in.top() != popV[j]))

{

in.emplace(pushV[i++]);

}

//栈顶是否为出栈数组

if(in.top() == popV[j])

{

in.pop();

}

else

{

return false;

}

}

return true;

}

逆波兰表达式求值：https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

class Solution {

public:

int evalRPN(vector<string>& tokens) {

stack<int> s;

for (size_t i = 0; i < tokens.size(); ++i) {

string& str = tokens[i];

// str为数字

if (!("+" == str || "-" == str || "*" == str || "/" == str)) {

s.push(atoi(str.c_str()));

} else {

// str为操作符

int right = s.top();

s.pop();

int left = s.top();

s.pop();

switch (str[0]) {

case '+':

s.push(left + right);

break;

case '-':

s.push(left - right);

break;

case '*':

s.push(left * right);

break;

case '/':

// 题目说明了不存在除数为0的情况

s.push(left / right);

break;

}

}

}

return s.top();

}

};

用两个栈实现队列：https://leetcode.cn/problems/implement-queue-using-stacks/submissions/564009874/

🌉stack的模拟实现

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

stack.c

namespace own

{

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;

};

}

test.c

# define _CRT_SECURE_NO_WARNINGS 1

#include "Stack.h"

using namespace std;

void test_stack()

{

own::stack<int> mystack;

mystack.push(1);

mystack.push(2);

mystack.push(3);

mystack.push(4);

cout << mystack.size() << endl;

while (!mystack.empty())

{

cout << mystack.top() << " ";

mystack.pop();

}

cout << endl;

}

int main()

{

test_stack();

return 0;

}

运行结果：

🌠 queue的介绍和使用

🌉queue的介绍

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

提取元素。队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的

成员函数来访问其元素。元素从队尾入队列，从队头出队列。底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操

作:

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

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

准容器deque。

🌉 queue的使用

OJ题目：

用队列实现栈：https://leetcode.cn/problems/implement-stack-using-queues/description/

🌠queue的模拟实现

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

具体如下：

queue.c

#pragma once

#include <iostream>

#include <list>

using namespace std;

namespace own

{ -- -->

template <class T>

class queue

{

public:

queue()

{ }

void push(const T& x)

{

_c.push_back(x);

}

void pop()

{

_c.pop_front();

}

T& front()

{

return _c.front();

}

T& back()

{

return _c.back();

}

const T& front() const

{

return _c.front();

}

const T& back() const

{

return _c.back();

}

bool empty()

{

return _c.empty();

}

size_t size()

{

return _c.size();

}

private:

list<T> _c;

};

}

test.c:

void test_queue()

{

own::queue<int> q;

q.push(1);

q.push(2);

q.push(3);

q.push(4);

std::cout << "Front: " << q.front() << ", Back: " << q.back() << std::endl;

q.pop();

std::cout << "Front: " << q.front() << ", Back: " << q.back() << std::endl;

// Test empty and size

std::cout << "Empty: " << q.empty() << ", Size: " << q.size() << std::endl;

}

🚩总结