`

程序员面试题精选(18)-用两个栈实现队列

阅读更多

题目:某队列的声明如下:

C++代码 复制代码
  1. template<typename T> class CQueue   
  2. {   
  3. public:   
  4.        CQueue() {}   
  5.        ~CQueue() {}   
  6.   
  7.       void appendTail(const T& node);  // append a element to tail   
  8.       void deleteHead();               // remove a element from head    
  9.   
  10. private:   
  11.       T> m_stack1;   
  12.       T> m_stack2;   
  13. };  
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对应的过程之后,我们可以开始动手写代码了。参考代码如下:

C++代码 复制代码
  1. ///////////////////////////////////////////////////////////////////////   
  2. // Append a element at the tail of the queue   
  3. ///////////////////////////////////////////////////////////////////////   
  4. template<typename T> void CQueue<T>::appendTail(const T& element)   
  5. {   
  6.       // push the new element into m_stack1   
  7.        m_stack1.push(element);   
  8. }    
  9. ///////////////////////////////////////////////////////////////////////   
  10. // Delete the head from the queue   
  11. ///////////////////////////////////////////////////////////////////////   
  12. template<typename T> void CQueue<T>::deleteHead()   
  13. {   
  14.       // if m_stack2 is empty,    
  15.       // and there are some elements in m_stack1, push them in m_stack2   
  16.       if(m_stack2.size() <= 0)   
  17.        {   
  18.             while(m_stack1.size() > 0)   
  19.              {   
  20.                    T& data = m_stack1.top();   
  21.                    m_stack1.pop();   
  22.                    m_stack2.push(data);   
  23.              }   
分享到:
评论

相关推荐

    程序员面试题精选(1-57)

    本资源"程序员面试题精选(1-57)"显然是一个汇集了众多面试题目的集合,涵盖了从基础到高级的各种问题,旨在帮助求职者提升自己的技能并顺利通过面试。 首先,我们要理解数据结构的重要性。数据结构是组织和存储数据...

    程序员面试题精选.doc

    【程序员面试题精选】——用两个栈实现队列 在面试中,经常会出现这样一道题:如何使用两个栈来模拟一个队列的行为。这道题目旨在考察候选者对数据结构的理解,尤其是对栈(LIFO,后进先出)和队列(FIFO,先进先出...

    程序员面试题精选100题

    【程序员面试题精选100题】是一份中文Word文档,包含了针对程序员的100道面试题目,这些题目详细解答了如何准备编程面试,尤其是技术面试环节。面试是求职过程中至关重要的一环,它能让雇主直接评估应聘者的技能和...

    C/C++程序员面试指南.杨国祥(带详细书签).pdf

    面试题12:能否用两个栈实现一个队列的功能 10.5 二叉树 面试题13:建立一个二叉树 面试题14:计算一棵二叉树的深度 面试题15:在二元树中找出和为某一值的所有路径 第11章 排序 11.1 插入排序 面试题1:编码实现...

    程序员面试100题数据结构和算法

    18. **两个栈实现队列**:使用两个栈模拟队列的入队(push)和出队(pop)操作,当栈A为空时,将栈B中的元素弹出并压入栈A,再进行出队操作。 以上知识点是程序员面试中常见的数据结构和算法问题,掌握它们对于面试...

    C++ STL程序员面试题

    - 如何在不复制元素的情况下合并两个vector? - 何时使用list,何时使用vector,以及它们各自的优缺点? - 举例说明如何自定义一个函数对象,并在STL算法中使用。 - 描述STL容器的内存管理和效率特点,比如...

    算法大全-面试题-链表-栈-二叉树-数据结构

    - **判断相交**:使用两个指针,一个从一个链表的头开始,另一个从可能的相交点开始,如果最终相遇则相交,否则不相交。 - **计算相交点**:同上,两个指针同时移动,直到相遇点即为相交点。 - **模拟大整数加法*...

    程序员面试逻辑题

    根据提供的文件信息,本文将围绕“程序员面试逻辑题”这一主题进行深入探讨,解析与程序员面试相关的逻辑题目及其重要性,帮助求职者更好地准备面试。 ### 知识点一:理解程序员面试逻辑题的重要性 在程序员招聘...

    程序员面试100题精选

    根据提供的文件信息,本文将对“程序员面试100题精选”进行详细的解析与扩展,旨在为准备参加技术面试的程序员提供有价值的参考。 ### 一、程序员面试的重要性 在当前竞争激烈的IT行业中,拥有一份优秀的简历固然...

    程序员面试笔试真题与解析

    【程序员面试笔试真题与解析】是一份针对程序员面试准备的重要资源,涵盖了C++和JAVA两个主流编程语言的面试真题及其详细解析。这个压缩包包含两份PDF文档,分别是"程序员面试笔试真题与解析_2017版.pdf"和"Java...

    程序员面试题精选100例.doc

    - 使用二分查找,因为旋转后的数组可以看作是由两个有序数组拼接而成。 - 当中间值小于左右两端值时,最小值在左半边。 - 否则,最小值在右半边。 - **算法实现**: ```cpp int findMin(vector&lt;int&gt;& nums) { ...

    中级程序员必备面试题.txt

    ### 中级程序员必备面试题解析 #### 如何创建一个有序集合 有序集合通常是通过`TreeSet`或`LinkedHashSet`等类实现。`TreeSet`基于红黑树存储元素,可以保证元素的自然排序;而`LinkedHashSet`则是基于哈希表与...

    java-leetcode面试题解Stack之第232题用栈实现队列-题解.zip

    在第232题中,我们需要使用两个栈来模拟一个队列的行为。这个问题的关键在于如何利用栈的特性来实现队列的两个主要操作:入队(enqueue)和出队(dequeue)。 1. 入队(enqueue)操作:将新元素直接压入栈1。这个...

    程序员笔试面试指导--很不错的一本书电子版

    根据给定文件的信息,我们可以提炼出一系列与程序员笔试面试相关的知识点。下面将详细解析这些知识点。 ### 数据结构 1. **非线性数据结构** - **知识点**: 数据结构可以分为线性和非线性两大类。线性数据结构中...

    世界500强面试题+程序员面试宝典

    总之,《世界500强面试题+程序员面试宝典》将为程序员提供一个全面的准备平台,帮助他们在激烈的竞争中脱颖而出。通过深入学习和理解其中的内容,不仅可以提升技术实力,也能提高面试的成功率,从而在IT行业中攀登更...

    程序员面试宝典.pdf

    《程序员面试宝典》是一本专门为程序员准备面试所编写的参考资料,它覆盖了算法思想、数据结构以及计算等多个方面,针对程序员在面试过程中可能遇到的问题提供了深入的分析和解答。 首先,在算法思想方面,书中介绍...

    程序员经典面试题

    【程序员经典面试题】涉及到的是两个常见的编程问题,一个是寻找字符串中第一个只出现一次的字符,另一个是层次遍历二叉树。这两个问题都考察了程序员对于数据结构和算法的理解及应用。 首先,第一个问题——寻找...

    C/C++程序员面试宝典

    《C/C++程序员面试宝典》是一本专为准备C/C++编程面试的求职者精心编写的指南。这本书以PDF格式提供,具有清晰的目录结构,使得读者可以快速定位到感兴趣或需要复习的知识点,有助于高效学习和查阅。在追求理想的...

Global site tag (gtag.js) - Google Analytics