【题目】
编写一个类,用两个栈实现队列,支持队列的基本操作(add、poll、peek)。
【我的代码】
头文件:MyQueue.h
#pragma once
#include <stack>
#include <iostream>
using namespace std;
class MyQueue
{
private:
stack<int> stack_main;
stack<int> stack_help;
public:
//入队
void add(int num) {
//如果是空的情况下,就直接压入主栈
if (stack_main.empty())
stack_main.push(num);
else {
//主栈非空,说明里面有元素,需要先把里面的元素放入help栈
while (!stack_main.empty()) {
int temp = stack_main.top();
stack_help.push(temp);
stack_main.pop();
}
//当main栈空了以后,才放入main栈
stack_main.push(num);
//再把help栈里面的元素倒回来
while (!stack_help.empty()) {
int temp = stack_help.top();
stack_main.push(temp);
stack_help.pop();
}
}
cout << "【入队成功】元素:" << num << endl;
}
//出队
void poll() {
//出队操作直接把main栈顶元素弹出即可
if (stack_main.empty()) {
cout << "Queue is empty!" << endl;
return;
}
int num = stack_main.top();
stack_main.pop();
cout << "【出队成功】元素:" << num << endl;
}
//返回队头元素
int peek() {
//对头元素直接就是main栈栈顶元素
if (stack_main.empty()) {
cout << "Queue is empty!" << endl;
return 0;
}
return stack_main.top();
}
};
主函数:main.cpp
// 由两个栈组成的队列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include "MyQueue.h"
using namespace std;
int main() {
cout << "|-------------------------------------------------|" << endl;
cout << "| 1. 入队 |" << endl;
cout << "| 2. 出队 |" << endl;
cout << "| 3. 当前对头元素 |" << endl;
cout << "| 4. 退出 |" << endl;
cout << "|-------------------------------------------------|" << endl;
MyQueue myQueue;
while (1) {
int num;
cin >> num;
int min;
switch (num)
{
case 1:
cout << "请输入入队元素:";
int number;
cin >> number;
myQueue.add(number);
cout << endl;
break;
case 2:
myQueue.poll();
break;
case 3:
min = myQueue.peek();
cout << "当前对头元素:" << min << endl;
break;
case 4:
return 0;
}
}
}
【左神思路代码】
头文件:zuoshen.h
#pragma once
#include <stack>
#include <iostream>
using namespace std;
class Zuoshen
{
private:
//push栈只对接压栈
stack<int> stack_push;
//pop栈只对接出栈
stack<int> stack_pop;
public:
//入队
void add(int num) {
//无论什么时候,都只压入push栈
stack_push.push(num);
}
//出队
void poll() {
//出队只能从pop栈中出去
if (stack_pop.empty() && stack_push.empty()) {
cout << "Queue is empty!" << endl;
return;
}
else if(stack_pop.empty()){
//当pop栈为空时候
while (!stack_push.empty()) {
//把push里面的东西放入pop
int temp = stack_push.top();
stack_push.pop();
stack_pop.push(temp);
}
}
int num = stack_pop.top();
stack_pop.pop();
cout << "【出队成功】元素:" << num << endl;
}
//返回队头元素
int peek() {
//对头元素直接就是pop栈栈顶元素
if (stack_pop.empty() && stack_push.empty()) {
cout << "Queue is empty!" << endl;
return;
}
else if (stack_pop.empty()) {
//当pop栈为空时候
while (!stack_push.empty()) {
//把push里面的东西放入pop
int temp = stack_push.top();
stack_push.pop();
stack_pop.push(temp);
}
}
return stack_pop.top();
}
};
【思路对比】
我的思路是在输入的时候就进行调整操作,从而add()达到O(n),但其他操作就仅仅需要针对一个main栈操作即可,都是O(1)。我的栈的分类是主次之分,次栈只是提供了一点帮助而已。
左神的思路挺高级的,他把栈分类成同等级的栈,pop栈专门面向用户弹出元素,push栈专门面向用户的输入。当pop栈非空时,弹出时仅需pop栈;当pop栈空了后,需要立刻从push栈导入数据。push栈可以理解为一个缓存,ummm挺高级,不过最坏情况下,只有push()能达到O(1),而其他方法都是O(n)。