首 页最新软件下载排行文章资讯投稿发布下载专题
维维下载站
您的位置:首页编程开发网络编程编程其它 → C++数据结构如何实现两个栈实现一个队列例子分享

C++数据结构如何实现两个栈实现一个队列例子分享

来源:维维整理 发布时间:2017-3-18 11:11:41 人气:

C++数据结构怎么样实现两个栈实现一个队列?本文主要为大家介绍C++ 数据结构实现两个栈实现一个队列的相关资料,有兴趣的朋友赶紧来了解一下吧。

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

堆栈是先进先出,队列是先进先出,队列是用两个堆栈实现的。是一个更经典的问题。看到这个问题,我对这个问题的第一个解决方案是:

定义两个堆栈,s1,s2。 S1用作队列的队列,s2用作队列的队列;

进入队列:每次进入队列时,该值都被推入s1堆栈;

Out队列:当离开队列时,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; 
}
相关下载
栏目导航
本类热门阅览