C++ 数据结构实现两个栈实现一个队列

C++ 数据结构实现两个栈实现一个队列

栈为后进先出，队列为先进先出

用两个栈实现一个队列。是一个比较经典的问题。

看到这个问题，我的第一个解题思路为：

定义两个栈，s1,s2。s1作为入队列栈，s2作为出队列栈；

入队列：每次入队列的时候，将数值压入s1栈中；

出队列：出队列时，将s1中的所有数据，压进s2栈中，然后删除s2的栈顶数据，然后再将s2中的剩余数据压入s1中。

在这其中s1是一个存储空间，s2是一个辅助空间。

进一步想一下上述办法，在出队列时，每一次都要将s1倒进s2，然后删除s2栈顶后又将s2的数据倒入s1;有另一个思路可以减少倒的次数；

入队列时：将数据压进s1;

出队列时：判断如果s2为空，那么将s1中的数据，压进s2中，然后删除s2栈顶，如果s2不为空那么再删除s2的栈顶即可；

并且还可以优化，优化如下：

出队列时，判断如果s2为空，那么将s1中n-1个数据，压进s2中，然后删除s1中的栈顶，如果s2不为空那么直接删除s2的栈顶即可；

优化版的c++实现如下：

#include<iostream> 
using namespace std; 
#include<stack> 
//栈 后进先出 队列 先进先出 
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() //比上面少一次出栈 
  { 
    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; 
}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

# C++两个栈实现一个队列 # 数据结构 # 两个栈实现一个队列 # C++线性表深度解析之动态数组与单链表和栈及队列的实现 # C++ 栈和队列的实现超详细解析 # C++基础学习之利用两个栈实现一个队列 # C++用两个栈实现一个队列（面试官的小结） # C++利用两个栈实现队列的方法 # C++中实现队列类链式存储与栈类链式存储的代码示例 # C++数据结构深入探究栈与队列 # 是一个 # 为空 # 还可以 # 第一个 # 在这 # 这个问题 # 希望能 # 要将 # 谢谢大家 # 又将 # 再将 # 可以减少 # 倒进 # std # namespace # brush # cpp # include # iostream

返回目录在线咨询

上一篇：怎么用Python将XML转换为YAML
下一篇： seo网络营销实战培训,零基础学习网络营销？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

C++ 数据结构实现两个栈实现一个队列

您的项目需求