服务器之家

服务器之家 > 正文

C++基础学习之利用两个栈实现一个队列

时间:2021-07-29 12:14     来源/作者:lixiaogang_theanswer

1 .给出类类型如下:有两个成员变量,分别是两个stack容器,存放的元素类型是 int;stack的特点是:先进后出;而队列queue的特点是先进先出;现在用两个 stack容器来实现队列:

实现代码:

?
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
-------------------------------------
------------- queue.h ---------------
#pragma once
#include <iostream>
#include <stdlib.h>
#include <stack>
using namespace std;
 
class Queue
{
private:
 stack<int> s1;
 stack<int> s2;
public:
 //入队
 void Push(const int& val);
 //出队
 void Pop();
 //返回队首元素
 int& Front();
 //返回队尾元素
 int& Back();
 //判断队列是否为空
 bool Empty();
 //返回队列大小
 int Size();
};
 
 
----------------------------------------
------------- queue.cpp ----------------
 
#include "queue.h"
 
//入队
void Queue::Push(const int& val)
{
 //栈s1作队列的队尾,s2作为队列的队头
 s1.push(val);
 cout<<val<<" ";
}
 
//出队
void Queue::Pop()
{
 while (!s1.empty())
 {
 int val = s1.top();
 s2.push(val);
 s1.pop();
 }
 s2.pop();
}
 
//返回队首元素
int& Queue::Front()
{
 while (!s1.empty())
 {
 s2.push(s1.top());
 s1.pop();
 }
 
 int temp = s2.top();
 while (!s2.empty())
 {
 int var = s2.top();
 s1.push(var);
 s2.pop();
 }
 return temp;
}
 
//返回队尾元素
int& Queue::Back()
{
 return s1.top();
}
 
//判断队列是否为空
bool Queue::Empty()
{
 if (s1.empty()&&s2.empty())
 {
 return true;
 }
 else
 return false;
}
 
//返回队列大小
int Queue::Size()
{
 return s1.size()+s2.size();
}
 
 
 
--------------------------------------
--------------- test.cpp -------------
#include "queue.h"
void test()
{
 Queue q1;
 cout<<"入队列操作:"<<endl;
 cout<<"插入的队列元素分别是:"<<endl;
 q1.Push(1);
 q1.Push(2);
 q1.Push(3);
 q1.Push(4);
 q1.Push(5);
 q1.Push(6);
 cout<<"判断队列是否为空!"<<endl;
 if (q1.Empty())
 {
 cout<<"empty."<<endl;
 }
 else
 {
 cout<<"not empty."<<endl;
 }
 cout<<"获取队头元素:"<<endl;
 cout<<q1.Front()<<endl;
 cout<<"获取队尾元素:"<<endl;
 cout<<q1.Back()<<endl;
 cout<<"获取队列的大小操作:"<<endl;
 cout<<q1.Size()<<endl;
 printf("出队列操作:\n");
 q1.Pop();
}
int main()
{
 test();
 system("pause");
 return 0;
}

分析过程:

让s1作为存储空间,而s2作为临时缓冲区。

进行入队操作时,将元素压入s1。

进行出队操作时,将s1的元素逐个“倒入”(弹出并压入)s2,将s2的顶元素弹出作为出队元素,之后再将s2剩下的元素逐个“倒回”s1。

C++基础学习之利用两个栈实现一个队列

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对服务器之家的支持。

原文链接:https://blog.csdn.net/lixiaogang_theanswer/article/details/72539997

标签:

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
2021德云社封箱演出完整版 2021年德云社封箱演出在线看
2021德云社封箱演出完整版 2021年德云社封箱演出在线看 2021-03-15
返回顶部