C++ data structure implements two stacks to implement a queue

C++ data structure implements two stacks to implement one queue

Stack is last in first out, queue is first in first out

Implement 1 queue with 2 stacks. It's a classic problem.

Seeing this problem, my first solution idea is:

Define two stacks, s1 and s2. s1 as the on-queue stack, s2 as the off-queue stack;

Enqueue: every time you enqueue, push the value into s1 stack;

Out of queue: when out of queue, push all data in s1 into s2 stack, then delete the top data in s2 stack, and then push the remaining data in s2 into s1.

Among them, s1 is one storage space and s2 is one auxiliary space.

Step forward and think about the above method. When exiting the queue, pour s1 into s2 every time, then delete the top of s2 stack and then pour s2 data into s1; There's another way to reduce the number of falls;

When enqueuing: press data into s1;

When out of the queue: judge if s2 is empty, then press the data in s1 into s2, and then delete the top of s2 stack. If s2 is not empty, then delete the top of s2 stack.

And it can be optimized as follows:

When exiting the queue, judge that if s2 is empty, then press n-1 data in s1 into s2, and then delete the top of the stack in s1. If s2 is not empty, then directly delete the top of the stack in s2.

The optimized c++ implementation is as follows:

#include<iostream> 
using namespace std; 
#include<stack> 
// The stack   Last in, first out   The queue   First in first out  
template<class T> 
class Queue 
{ 
public: 
 
  /*T Pop_back() 
  { 
    if (s2.size() <= 0) 
    { 
      while(s1.size() > 0) 
      { 
        T& temp = s1.top(); 
        s1.pop(); 
        s2.push(temp); 
      } 
    } 
    if (s2.size() == 0) 
      throw new exception("queue is empty "); 
 
    T tep = s2.top(); 
    s2.pop(); 
    return tep; 
  }*/ 
 
  T Pop_back() // Less than the above 1 Make time for  
  { 
    if (s2.size() <= 0) 
    { 
      while (s1.size() > 1) 
      { 
        T& temp = s1.top(); 
        s1.pop(); 
        s2.push(temp); 
      } 
      T tep = s1.top(); 
      s1.pop(); 
      return tep; 
    } 
    else{ 
      T tep = s2.top(); 
      s2.pop(); 
      return tep; 
    } 
  } 
   
    void Push_back(const T& value) 
  { 
    s1.push(value); 
  } 
 
    bool Empty() 
    { 
      return (s1.empty() && s2.empty()); 
    }       
 
protected: 
  stack<T> s1; 
  stack<T> s2; 
}; 
 
void TextQueue() 
{ 
  Queue<int> q1; 
  q1.Push_back(1); 
  q1.Push_back(2); 
  q1.Push_back(3); 
  q1.Push_back(4); 
 
  cout << q1.Pop_back() << endl; 
  cout << q1.Pop_back() << endl; 
  cout << q1.Pop_back() << endl; 
  cout << q1.Pop_back() << endl; 
} 

Thank you for reading, I hope to help you, thank you for your support of this site!