用来两个栈实现一个队列。

旧城等待， 2022-07-24 05:07 117阅读 0赞

题目：用来两个栈实现一个队列。
    
    
    
    #include<stack>
    template < class T>
    class CQueue
    {
    public:
              
    
               void AppendTail(const T& Node)
              {
                       _s1.push( Node);
              }
    
               void DeleteHead()
              {
                        //如果_s2空，就把所有数据都倒入s2中
                        if (_s2.empty())
                       {
                                  while (!_s1.empty())
                                 {
                                          _s2.push(_s1.top());
                                          _s1.pop();
                                 }
                                 _s2.pop();
                       }
                        else //不为空，就先pop出去。
                       {
                                 _s2.pop();
                       }
    
              }
              
               void Print()    //打印队列元素，分四种情况。
              {
                        if (_s1.empty() && _s2.empty())
                       {
                                 cout << "The Queue is Empty!";
                       }
                       
                        else if (!_s1.empty() && _s2.empty())
                       {
                                  while (!_s1.empty())
                                 {
                                          _s2.push(_s1.top());
                                          _s1.pop();
                                 }
                       
                                  while (!_s2.empty())
                                 {
                                          cout << _s2.top() << "  " ;
                                          _s2.pop();
                                 }
                       }
                       
                        else if (_s1.empty() && !_s2.empty())
                       {
                                  while (!_s2.empty())
                                 {
                                          cout << _s2.top() << "  " ;
                                          _s2.pop();
                                 }
                       }
                       
                        else
                       {
                                  while (!_s2.empty())
                                 {
                                          cout << _s2.top() << "  " ;
                                          _s2.pop();
                                 }
                       
                                  while (!_s1.empty())
                                 {
                                          _s2.push(_s1.top());
                                          _s1.pop();
                                 }
                       
                                  while (!_s2.empty())
                                 {
                                          cout << _s2.top() << "  " ;
                                          _s2.pop();
                                 }
                       }
                       cout << endl;
              }
    private:
               stack<T >  _s1;
               stack<T >  _s2;
    };
    
    
    void Test()
    {
               CQueue<int > cq;
              cq.AppendTail(1);
              cq.AppendTail(2);
              cq.AppendTail(3);
              cq.AppendTail(4);
              cq.DeleteHead();
              cq.Print();
    }

#include<stack>
    template<class T>
    class CQueue
    {
    public:
    	
    	void appendTail(const T& node)
    	{
    		stack1.push(node);
    	}
    	T deleteHead()
    	{
    		if (stack2.size() <= 0)
    		{
    			while (stack1.size() > 0)
    			{
    				T& data = stack1.top();
    				stack1.pop();
    				stack2.push(data);
    			}
    		}
    		if (stack2.size() == 0)
    			throw new exception("queue is empty");
    			
    		T head = stack2.top();
    		stack2.pop();
    		return head;
    	}
    
    private:
    	stack<T> stack1;
    	stack<T> stack2;
    };