C++奇迹之旅：快速上手Stack和Queue的使用与模拟实现

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;
};

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;

    }

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

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;
	};
}

# 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;
}

#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;
	};
}

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;

}