C++第十三弹 -- STL之stack深度剖析与模拟实现

前言

在现代C++编程中，STL（标准模板库）是一个不可或缺的工具。它提供了一套通用的模板类和算法，使得开发者能够更加高效地处理数据。本文将重点介绍STL中的stack容器，作为一种重要的顺序容器，stack遵循后进先出（LIFO，Last In First Out）的特性，广泛应用于函数调用、表达式求值等场景。通过深入了解stack的特性、基本操作及应用实例，读者将能够更好地掌握和应用这一重要的数据结构。

博客主页: 酷酷学!!!

感谢关注!!!

正文开始

1. stack的介绍

1. stack是一种容器适配器, 专门用在具有后进先出操作的上下文环境中, 其删除只能从容器的一端进行元素的插入与提取操作.
2. stack是作为容器适配器被实现的, 容器适配器即是对特定类作为其底层的容器, 并提供了一组特定的成员函数来访问其元素, 将特定类作为其底层的, 元素特定容器的尾部(即栈顶)被压入和弹出.
3. stack的容器可以是任何形式的容器类模板或者一些其他特定的容器类, 这些容器类应该支持以下操作:

• empty: 判空操作
• back: 获取尾部元素操作
• push_back: 尾部插入元素操作
• pop_back: 尾部删除元素操作

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

2. stack的使用

重点:

代码演示:

#include<stack>
#include<iostream>
using namespace std;
int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	cout << st.top() << endl;
	st.pop();
	cout << st.size() << endl;
	st.pop();
	cout << st.empty() << endl;
	return 0;
}

3. stack的模拟实现

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

#pragma once
#include<iostream>
#include<vector>
#include<list>
using namespace std;

namespace my
{
	//传统写法
	//template<class T>
	//class stack
	//{
	//private:
	//	T* _a;
	//	int _top;
	//	int _capacity;
	//};
	//直接复用容器
	template<class T, class Container = vector<T>> //当然适配器也可以是其他容器
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}
		void pop()
		{
			_con.pop_back();
		}
		const T& top()
		{
			return _con.back();
		}
		bool empty()
		{
			return _con.empty();
		}
		size_t size()
		{
			return _con.size();
		}

	private:
		Container _con;
	};
}

4. stackOJ题目

4.1 最小栈

题目链接:最小栈

题目描述:

题目思路:

题目要求在常数时间内求出栈中最小元素, 如果我们遍历栈, 时间复杂度就为N, 不符合题目要求, 我们可以创建两个栈, 一个用来模拟入栈出栈, 一个用来记录最小数据, 定义两个栈为成员函数, 首先, 先插入一个元素, 然后让出栈序列与入栈的栈顶元素进行比较, 如果_minst为空或者栈顶元素小于或者等于_minst的栈顶元素, 则将数据push到最小栈, 出栈时, 如果_st的栈顶元素等于_minst的栈顶元素, 则_minst出栈, 即更改了当前最小元素.

代码演示:

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        if(_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
        _st.push(val);
    }
    
    void pop() {
        if(_st.top() == _minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }

    stack<int> _st;
    stack<int> _minst;

};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

4.2 栈的压入弹出序列

题目链接:栈的压入弹出序列

题目描述:

题目思路

对于栈的压入弹出序列, 我们如果直接上手对比, 很容易出错, 而且比较麻烦, 我们可以对入栈与出栈进行栈的模拟, 创建一个栈st, 对入栈序列进行遍历插入, 先插入一个元素, 然后与出栈序列进行对比, 遍历出栈序列, 如果与出栈序列相等, 则说明该出栈了, 就pop出此时的栈, 这时还不能插入新的元素, 继续将st的栈顶元素与出栈序列对比, 如果不想等了, 我们再插入, 然后再进行下一轮的对比, 或者此时st已经为空了, 则跳出循环, 也进行下一轮的插入对比, 如果插入序列全部遍历完, 而出栈序列没有遍历完, 则说明此出栈序列不为栈的弹出序列, 反之亦然.也可以判断此时栈是否为空即可.

代码演示:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型vector 
     * @param popV int整型vector 
     * @return bool布尔型
     */
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // write code here
        stack<int> st;
        int pos = 0;
        for(auto e : pushV)
        {
            st.push(e);
            while( !st.empty() && st.top() == popV[pos])
            {
                pos++;
                st.pop();
            }
        }
        return st.empty();
    }
};

4.3 用栈实现队列

题目链接:

用栈实现队列

题目描述:

题目思路

对于本题我们再栈的那一篇已经使用c语言完成过了, 本次我们采用C++进行完成, 避免了我们自己造轮子, 还是一样, 用两个栈实现一个队列, 一个栈进行插入, 如果需要出栈, 则就把所有的插入栈所有数据导一下,出栈直接出popst中的元素.

代码演示

class MyQueue {
public:
    MyQueue() {

    }
    
    void push(int x) {
        pushst.push(x);
    }
    
    int pop() {
        if(popst.empty())
        {
            while(!pushst.empty())
            {
                int x = pushst.top();
                popst.push(x);
                pushst.pop();
            }
        }
        int ret = popst.top();
        popst.pop();
        return ret;
    }
    
    int peek() {
        if(popst.empty())
        {
            while(!pushst.empty())
            {
                int x = pushst.top();
                popst.push(x);
                pushst.pop();
            }
        }
        int ret = popst.top();
        return ret;
    }
    
    bool empty() {
        return pushst.empty()&&popst.empty();
    }
    stack<int> pushst;
    stack<int> popst;

};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

总结

通过对STL中stack的探讨，我们认识到它在解决特定问题时的便利性和高效性。stack类提供了简单易用的接口，使得数据的插入和删除操作更加直接。同时，我们也了解了其在实际应用中的价值，例如在算法中用于管理临时状态或数据。此外，结合实际示例和代码实现，读者可以看到如何灵活地将stack应用于自己的项目中。掌握stack的使用，将为解决更复杂的问题奠定坚实的基础。希望本文能帮助大家更深入地了解STL之stack，并在日常编程中熟练运用

完