两个栈实现一个队列

用栈实现队列1、栈的特点栈的特点是先进后出,进出元素都是在同一端(栈顶)。入栈:出栈:2、队列的特点队列的特点是先进先出,出入元素是在不同的两端(队头和队尾)。入队:出队:3、两个栈实现队列我们拥有两个栈,可以让其中一个栈作为队列的入口,负责插入新元素;另一个栈作为队列的出口,负责移除老的元素。队列的主要操作无非有两个:入队和出队。在…

大家好,又见面了,我是你们的朋友全栈君。

用栈实现队列

1、栈的特点

栈的特点是先进后出,进出元素都是在同一端(栈顶)。

入栈:

两个栈实现一个队列

出栈:

两个栈实现一个队列

2、队列的特点

队列的特点是先进先出,出入元素是在不同的两端(队头和队尾)。

入队:

两个栈实现一个队列

出队:

两个栈实现一个队列

3、两个栈实现队列

我们拥有两个栈,可以让其中一个栈作为队列的入口,负责插入新元素;另一个栈作为队列的出口,负责移除老的元素。

两个栈实现一个队列

队列的主要操作无非有两个:入队和出队。在模拟入队操作时,每一个新元素都被压入到栈A当中。

         让元素1“入队”:

两个栈实现一个队列

         让元素2“入队”:

两个栈实现一个队列

         让元素3“入队”:

两个栈实现一个队列

         这时候,我们希望最先“入队”的元素1“出队”,需要怎么做呢?

         让栈A中的所有元素按顺序出栈,再按照出栈顺序压入栈B。这样一来,元素从栈A弹出并压入栈B的顺序是3,2,1,和当初进入栈A的顺序1,2,3是相反的:

两个栈实现一个队列

         此时让元素1“出队”,也就是让元素1从栈B弹出:

两个栈实现一个队列

         让元素2“出队”:

两个栈实现一个队列

         如果这个时候又想做入队操作了呢?当有新元素入队时,重新把新元素压入栈A。

         让元素4“入队”:

两个栈实现一个队列

         此时的出队操作仍然从栈B弹出元素。

         让元素3“出队”:

两个栈实现一个队列

         这个时候栈B已经空了,如果再想出队怎么办呢?只要栈A还有元素就像刚才一样,把栈A元素弹出并压入栈B。

两个栈实现一个队列

         让元素4“出队”:

两个栈实现一个队列

4、实现思路

(1) 使用两个栈A,B,其中假定A负责push操作,B负责pop操作。使用一个变量back_elem来存储最后添加的元素。

(2) 实现队列的push操作, 每次进行添加操作,都会相应得对栈A进行添加元素。并对back_elem赋值

(3) 实现队列的pop操作,每次进行删除操作,因为栈B负责pop操作,

首先判断栈B是否为空?

a.如果B为空,则判断A是否为空? 

          如果A也为空,则输出错误信息,此时队列为空。

          如果A不为空,则将栈A中的所有数据存储到B中。执B.push(A.top()),   A.pop().   然后在对栈B执行,B.pop()操作,将队列的头元素删除

b.如果B不为空, 则直接对B执行 B.pop()操作。

           例如对a,b,c实现push操作,然后实现pop操作

                   http://hi.csdn.net/attachment/201111/18/0_1321607953iMMg.gif

(4)实现队列的front()操作,方法如pop操作相同,只是在最后一步使用B.top()返回值。

(5)实现队列的back()操作,因为我们变量back_elem保存着最后一个输入的数据,故直接将其返回。

(6)实现队列的size()操作,和empty()操作,就是对A,B分别执行操作。

5、代码实现

#include <iostream>
#include <stack>
#include <string>
using namespace std;

template<typename T>
class Queue {
private:
	stack<T>stackA;	//栈A
	stack<T>stackB;	//栈B
	T back_elem;	//用于存储新添加的元素
public:
	void push(T elem);	//将新元素压入队列(压入栈A)中
	void pop();			//将元素弹出队列(从栈B中弹出)
	T front();			//队首元素
	T back();			//队尾元素
	int size()const;    //队列长度
	bool empty()const;  //队列是否为空
};

/*
入队操作
实现队列的push操作, 每次进行添加操作,都会相应得对栈A进行添加元素。并对back_elem赋值
*/
template<typename T>
void Queue<T>::push(T elem)
{
	stackA.push(elem);//将元素压入队列
	back_elem = elem;	//存储新添加的元素
}

/*
出队操作
实现队列的pop操作,每次进行删除操作,因为栈B负责pop操作。
首先判断栈B是否为空?
a.如果栈B为空,则判断A是否为空?
		如果A也为空,则输出错误信息,此时队列为空。
		如果A不为空,则将栈A中的所有数据存储到B中。执B.push(A.top()), A.pop().然后在对栈B
			执行,B.pop()操作,将队列的头元素删除
b.如果栈B不为空, 则直接对栈B执行 B.pop()操作。

*/
template<typename T>
void Queue<T>::pop()
{
	//判断栈B是否为空?
	if (!stackB.empty())	//栈B不为空, 则直接对栈B执行 B.pop()操作。
	{
		stackB.pop();
	}
	else if (!stackA.empty())	//栈B为空,则判断栈A是否为空?栈A不为空,则将栈A中的所有数据
   //存储到B中。执B.push(A.top()), A.pop().然后在对栈B执行,B.pop()操作,将队列的头元素删除
	{
		stackB.push(stackA.top());
		stackA.pop();
	}
	else
	{
		std::cout << "error pop(),empty queue!" << std::endl;
	}
}

/*
队首元素
*/
template<typename T>
T Queue<T>::front()
{
	if (!stackB.empty())
	{
		return stackB.top();
	}
	else if (!stackA.empty())
	{
		while (!stackA.empty())
		{
			stackB.push(stackA.top());
			stackA.pop();
		}
		return stackB.top();
	}
	else
	{
		std::cout << "error front(),empty queue!" << std::endl;
	}
}

/*
队尾元素
*/
template<typename T>
T Queue<T>::back()
{
	if (!empty())
	{
		return back_elem;
	}
	else
	{
		std::cout << "error back(),empty queue!" << std::endl;
	}
}

/*
队列长度
*/
template<typename T>
int Queue<T>::size() const
{
	return stackA.size() + stackB.size();
}

/*
队列是否为空
*/
template<typename T>
bool Queue<T>::empty() const {
	return stackA.empty() && stackB.empty();
}

int main()
{
	Queue<int>queue;
	//入队操作
	queue.push(1);
	queue.push(2);
	queue.push(3);
	queue.push(4);
	cout << "Four times push() After:" << endl;
	//队首元素
	cout << "The queue front:" << queue.front() << endl;
	//队尾元素
	cout << "The queue back:" << queue.back() << endl;
	//队列size
	cout << "The queue size:" << queue.size() << endl;
	//出队操作
	queue.pop();
	queue.pop();
	queue.pop();
	queue.pop();
	cout << "----------------------------" << endl;
	cout << "Four times pop() After:" << endl;
	//队首元素
	cout << "The queue front:" << queue.front() << endl;
	//队尾元素
	cout << "The queue back:" << queue.back() << endl;
	//队列size
	cout << "The queue size:" << queue.size() << endl;

	//system("pause");
	return 0;
}

结果:

Four times push() After:
The queue front:1
The queue back:4
The queue size:4
—————————-
Four times pop() After:
error front(),empty queue!
The queue front:260750304
error back(),empty queue!
The queue back:260750304
The queue size:0
请按任意键继续. . .

6、时间复杂度

入队操作的时间复杂度显然是O(1)。至于出队操作,如果涉及到栈A和栈B的元素迁移,时间复杂度是O(n),如果不用元素迁移,时间复杂度是O(1)。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124970.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 二进制加减法计算法则

    二进制加减法计算法则一、二进制加法(逢2进1)举例:100111+11010=10000110011111010——————100001十进制加法是逢十进一,二进制加法是逢二进一。最低位:1加0得1。倒数第2位:1加1得2,同时进1。倒数第3位:1加0得1,再加上进位的1,结果为2。其他位同理。二、二进制减法(借1当2)举例:1000001-11010=100111…

  • cmd命令怎么切换盘符_windows切换盘符命令

    cmd命令怎么切换盘符_windows切换盘符命令转载于:https://www.cnblogs.com/QMM2008/p/4003039.html

  • 没有sln文件怎么打开「建议收藏」

    没有sln文件怎么打开「建议收藏」没有sln文件怎么用相信这个问题应该是初学者,对.net了解不深的同学会发问的一、很多人学习.net网站开发的时候,使用MicrosoftVisualStudio工具,却没使用过IIS配置网站,我学习的时候就没用过IIS。二、.net网站有个website和webApplication区分,估计很多初学者都不了解这个。可以点击这个了解下三、网站分层架构估计也不是很了解。…

  • CSS基础笔记——超链接样式

    CSS基础笔记——超链接样式在浏览器中,超链接默认情况下字体为蓝色,带有下划线,鼠标单击时字体为红色,单击后为紫色而在CSS中,我们可以使用超链接伪类来定义超链接在鼠标单击的不同时期的样式a:link{…}a:visited{…}a:hover{…}a:active{…}定义四个伪类,必须按照link、visited、hover、active的顺序进行,不然浏览器可能无法正常显示这四种样式<!DOCTYPEhtml><html><head&gt

  • PHP中unset,array_splice删除数组中元素的区别

    PHP中unset,array_splice删除数组中元素的区别

    2021年10月15日
  • C#时间控件使用

    C#时间控件使用简单的做法是转换成指定精度的String,然后比较字符串。Dated1=datetimepicker.date;Datenow=DateTime.Now;假设精确到分钟:intresult=now.toString(“yyyy-MM-ddhh:mi”).compareTo(d1.toString(“yyyy-MM-ddhh:mi”));假如result=0

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号