服务器之家

服务器之家 > 正文

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

时间:2021-05-04 15:57     来源/作者: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++实现如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
}

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

原文链接:http://blog.csdn.net/he_shuai20/article/details/62892260

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
返回顶部