【转】http://zhedahht.blog.163.com/blog/static/2541117420073293950662/
题目:某队列的声明如下:
template<typename T> class CQueue
{
public:
CQueue() {}
~CQueue() {}
void appendTail(const T& node); // append a element to tail
void deleteHead(); // remove a element from head
private:
T> m_stack1;
T> m_stack2;
};
分析:从上面的类的声明中,我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。
我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素a,不妨把先它插入到m_stack1。这个时候m_stack1中的元素有{a},m_stack2为空。再插入两个元素b和c,还是插入到m_stack1中,此时m_stack1中的元素有{a,b,c},m_stack2中仍然是空的。
这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则,由于a比b、c先插入到队列中,这次被删除的元素应该是a。元素a存储在m_stack1中,但并不在栈顶上,因此不能直接进行删除。注意到m_stack2我们还一直没有使用过,现在是让m_stack2起作用的时候了。如果我们把m_stack1中的元素逐个pop出来并push进入m_stack2,元素在m_stack2中的顺序正好和原来在m_stack1中的顺序相反。因此经过两次pop和push之后,m_stack1为空,而m_stack2中的元素是{c,b,a}。这个时候就可以pop出m_stack2的栈顶a了。pop之后的m_stack1为空,而m_stack2的元素为{c,b},其中b在栈顶。
这个时候如果我们还想继续删除应该怎么办呢?在剩下的两个元素中b和c,b比c先进入队列,因此b应该先删除。而此时b恰好又在栈顶上,因此可以直接pop出去。这次pop之后,m_stack1中仍然为空,而m_stack2为{c}。
从上面的分析我们可以总结出删除一个元素的步骤:当m_stack2中不为空时,在m_stack2中的栈顶元素是最先进入队列的元素,可以pop出去。如果m_stack2为空时,我们把m_stack1中的元素逐个pop出来并push进入m_stack2。由于先进入队列的元素被压到m_stack1的底端,经过pop和push之后就处于m_stack2的顶端了,又可以直接pop出去。
接下来我们再插入一个元素d。我们是不是还可以把它push进m_stack1?这样会不会有问题呢?我们说不会有问题。因为在删除元素的时候,如果m_stack2中不为空,处于m_stack2中的栈顶元素是最先进入队列的,可以直接pop;如果m_stack2为空,我们把m_stack1中的元素pop出来并push进入m_stack2。由于m_stack2中元素的顺序和m_stack1相反,最先进入队列的元素还是处于m_stack2的栈顶,仍然可以直接pop。不会出现任何矛盾。
我们用一个表来总结一下前面的例子执行的步骤:
操作
|
m_stack1
|
m_stack2
|
append a
|
{a}
|
{}
|
append b
|
{a,b}
|
{}
|
append c
|
{a,b,c}
|
{}
|
delete head
|
{}
|
{b,c}
|
delete head
|
{}
|
{c}
|
append d
|
{d}
|
{c}
|
delete head
|
{d}
|
{}
|
总结完push和pop对应的过程之后,我们可以开始动手写代码了。参考代码如下:
///////////////////////////////////////////////////////////////////////
// Append a element at the tail of the queue
///////////////////////////////////////////////////////////////////////
template<typename T> void CQueue<T>::appendTail(const T& element)
{
// push the new element into m_stack1
m_stack1.push(element);
}
///////////////////////////////////////////////////////////////////////
// Delete the head from the queue
///////////////////////////////////////////////////////////////////////
template<typename T> void CQueue<T>::deleteHead()
{
// if m_stack2 is empty, and there are some
// elements in m_stack1, push them in m_stack2
if(m_stack2.size() <= 0)
{
while(m_stack1.size() > 0)
{
T& data = m_stack1.top();
m_stack1.pop();
m_stack2.push(data);
}
}
// push the element into m_stack2
assert(m_stack2.size() > 0);
m_stack2.pop();
}
扩展:这道题是用两个栈实现一个队列。反过来能不能用两个队列实现一个栈?如果可以,该如何实现?
分享到:
相关推荐
python 实现 用两个栈实现队列
用两个栈实现队列.md
title: 剑指Offer-用两个栈实现队列subtitle: 用两个栈实现队列categories: 剑指Offer用两个栈实现队列题目描述用两个栈来实现一
两个栈 实现一个队列
232. 用两个栈实现队列232. 用栈实现队列题目描述解题思路/** Initialize your data structure here. *//** R
9. 用两个栈实现队列题目链接牛客网题目描述用两个栈来实现一个队列,完成队列的 Push 和 Pop 操作。当元素要出栈时,需要先进入 out 栈,此时元素出栈
用两个栈实现队列思路很简单:入栈只入栈1出栈只从栈2出,出栈时如果栈2右元素则顶部元素出栈,否则让栈1元素全部压入到栈2,然后栈2最上面元素出栈代码如下:
队列的两种实现方式一种是数组一种是栈,此处介绍如何将用两个栈来实现一个队列
队列的声明如下,请实现它的两个函数 appendTail 和deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元示例:
用量个栈实现一个队列,使其可以有进队和出队的操作。
使用面向对象技术,应用两个队列来实现一个栈,并且采用了类模板技术,实现的栈属于栈模板!
要求用两个栈{stack1,stack2}实现一个队列,也就是说我们需要使用栈的push和pop功能来构造队列的push和pop功能。 栈我们用列表表示,相应的功能使用append和pop函数实现。 队列的push功能: 使用stack1来存储元素,...
用两个栈实现一个队列的功能?要求给出算法和思路
自己写的代码,有详细的注释,供大家参考。
本文实例讲述了PHP使用两个栈实现队列功能的方法。分享给大家供大家参考,具体如下: 问题 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解决思路 两个栈。出栈的时候,如果栈2不为...
题目描述: 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 解题思路参考:https://blog.csdn.net/flower_48237/article/details/104055970
5.用两个栈实现一个队列题目描述用两个栈来实现一个队列,完成队列的Push和Pop操作。* @desc 用两个栈实现队列public class Solutio
1、熟练掌握栈和队列的基本操作在两种存储结构上的实现。 2、会用栈和队列解决简单的实际问题。 二、实验内容 题目:试写一个算法,判断依次读入的一个以@为结束符的字符序列,是否为回文。所谓“回文“是指正向读...