栈（二）

女爷i 2022-09-26 13:58 14阅读 0赞

//两个栈实现一个队列
    /*
    #include <iostream>
    #include <stack>
    using namespace std;
    template<class T>
    class Queue
    {
    public:
    	void Push(const T& x)
    	{
    		_PushStack.push(x);
    	}
    	void Pop()
    	{
    		if (_PopStack.empty())
    		{
    			while (!_PushStack.empty())
    			{
    				_PopStack.push(_PushStack.top());
    				_PushStack.pop();
    			}
    		}
    		if (!_PopStack.empty())
    		{
    			cout << _PopStack.top() << " ";
    			_PopStack.pop();
    		}
    	}
    private:
    	stack<T> _PushStack;
    	stack<T> _PopStack;
    };
    int main()
    {
    	Queue<int> q1;
    	q1.Push(1);
    	q1.Push(2);
    	q1.Push(3);
    	q1.Push(4);
    	q1.Push(5);
    	q1.Push(6);
    	q1.Pop();
    	q1.Pop();
    	q1.Pop();
    	q1.Pop();
    	q1.Pop();
    	q1.Pop();
    	return 0;
    }
    */
    
    //使用两个队列实现一个栈
    #include <iostream>
    #include <queue>
    using namespace std;
    class Stack
    {
    public:
    	void Push(const int& x)
    	{
    		_PushQ1.push(x);
    	}
    	void Pop()
    	{
    		if (!Empty())
    		{
    			if (_PushQ1.empty() && !_TmpQ2.empty())
    			{
    				swap(_PushQ1, _TmpQ2);
    			}
    			int size = _PushQ1.size();
    			while (--size)
    			{
    				_TmpQ2.push(_PushQ1.front());
    				_PushQ1.pop();
    			}
    			_PushQ1.pop();
    		}
    	}
    	const int &Top()
    	{
    		if (!Empty())
    		{
    			if (_PushQ1.empty() && !_TmpQ2.empty())
    			{
    				swap(_PushQ1, _TmpQ2);
    			}
    			int size = _PushQ1.size();
    			while (--size)
    			{
    				_TmpQ2.push(_PushQ1.front());
    				_PushQ1.pop();
    			}
    			return _PushQ1.front();
    		}
    	}
    	bool Empty()
    	{
    		return _PushQ1.empty() && _TmpQ2.empty();
    	}
    private:
    	queue<int> _PushQ1;
    	queue<int> _TmpQ2;
    };
    int main()
    {
    	Stack s1;
    	s1.Push(1);
    	s1.Push(2);
    	s1.Push(3);
    	s1.Push(4);
    	s1.Push(5);
    	s1.Push(6);
    	cout << s1.Top() << " ";
    	s1.Pop();
    	cout << s1.Top() << " ";
    	s1.Pop();
    	cout << s1.Top() << " ";
    	s1.Pop();
    	cout << s1.Top() << " ";
    	s1.Pop();
    	cout << s1.Top() << " ";
    	s1.Pop();
    	cout << s1.Top() << " ";
    	s1.Pop();
    	return 0;
    }