程序员面试题精选100题(18)-用两个栈实现队列[数据结构]-程序员宅基地

技术标签: C/C++  程序员    队列  面试题  数据结构  

前几天实在太忙,今天继续,虽然是转载,但每天可以学习一点,进步一点。


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

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为空。再插入两个元素bc,还是插入到m_stack1中,此时m_stack1中的元素有{a,b,c}m_stack2中仍然是空的。

这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则,由于abc先插入到队列中,这次被删除的元素应该是a。元素a存储在m_stack1中,但并不在栈顶上,因此不能直接进行删除。注意到m_stack2我们还一直没有使用过,现在是让m_stack2起作用的时候了。如果我们把m_stack1中的元素逐个pop出来并push进入m_stack2,元素在m_stack2中的顺序正好和原来在m_stack1中的顺序相反。因此经过两次poppush之后,m_stack1为空,而m_stack2中的元素是{c,b,a}。这个时候就可以popm_stack2的栈顶a了。pop之后的m_stack1为空,而m_stack2的元素为{c,b},其中b在栈顶。

这个时候如果我们还想继续删除应该怎么办呢?在剩下的两个元素中bcbc先进入队列,因此b应该先删除。而此时b恰好又在栈顶上,因此可以直接pop出去。这次pop之后,m_stack1中仍然为空,而m_stack2{c}

从上面的分析我们可以总结出删除一个元素的步骤:当m_stack2中不为空时,在m_stack2中的栈顶元素是最先进入队列的元素,可以pop出去。如果m_stack2为空时,我们把m_stack1中的元素逐个pop出来并push进入m_stack2。由于先进入队列的元素被压到m_stack1的底端,经过poppush之后就处于m_stack2的顶端了,又可以直接pop出去。

接下来我们再插入一个元素d。我们是不是还可以把它pushm_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}

{}

总结完pushpop对应的过程之后,我们可以开始动手写代码了。参考代码如下:

///
// 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();
}


扩展:这道题是用两个栈实现一个队列。反过来能不能用两个队列实现一个栈?如果可以,该如何实现?


转自:http://zhedahht.blog.163.com/blog/static/2541117420073293950662/

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/licongqi/article/details/17390523

智能推荐

访问url没有加斜杠,nginx会301重定向_zblog nginx目录页没有斜杠301-程序员宅基地

文章浏览阅读1.1k次。访问url没有加斜杠,nginx会301重定向location 会加上/斜杠location /download { #rewrite ^/download$ https://192.168.137.3/download/; alias /usr/local/nginx/html/; } node2:/root#curl http://192.168.137.2:2443/download -IHTTP/1.1 301 Moved Per._zblog nginx目录页没有斜杠301

python 素因子分解-程序员宅基地

文章浏览阅读1.1k次。在使用python解决问题之前,我们先说一下,什么是素因子分解所谓素因子分解就是,先找这个数的所有约数(约数即:a%b == 0,也就是a可以被b整除)例如:20的约数集合为 [1, 2, 5, 10, 20]那么素因子分解呢?就是从最小的素数约数开始除,也就是这个除数要满足两个条件,一是约数,二是素数那么这里20的最小的素约数是2,所以我们从2开始除,并且一直除到不能被整出为..._python 素因子分解

动态创建Fastreport-程序员宅基地

文章浏览阅读224次。动态创建Fastreport分以下几个步骤:1.首先清空Fastreport,定义全局变量,并加载数据集 frReport.Clear; frReport.DataSets.Add(frxDBDataset1); DataHeight :=28; DataWidth :=80; FirstTop := 50; FirstLeft := 15;2.创建frxRepor..._pascalscript dataset.fields

安装numpy报错-------python setup.py egg_info Check the logs for full command output_numpy check the logs for full command output.-程序员宅基地

文章浏览阅读3k次。python -m pip install --upgrade pip 首先,我查看了自己的版本在这里插入图片描述链接服务器超时_numpy check the logs for full command output.

百度c语言贴吧 经典C源程序100例-2_c语言贴吧顶贴机源码-程序员宅基地

文章浏览阅读1k次。【程序2】 题目:企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高    于10万元,低于20万元时,低于10万元的部分按10%提成,高于10万元的部分,可可提    成7.5%;20万到40万之间时,高于20万元的部分,可提成5%;40万到60万之间时高于    40万元的部分,可提成3%;60万到100万之间时,高于60万元的部分,可提成1.5_c语言贴吧顶贴机源码

偏向锁,轻量级锁与重量级锁_轻量级锁和偏向锁,重量级锁-程序员宅基地

文章浏览阅读256次。偏向锁Hotspot 的作者经过以往的研究发现大多数情况下锁不仅不存在多线程竞争,而且总是由同一线程多次获得,为了让线程获得锁的代价更低而引入了偏向锁。当一个线程访问同步块并获取锁时,会在对象头和栈帧中的锁记录里存储锁偏向的线程 ID。以后该线程在进入和退出同步块时不需要花费CAS操作来加锁和解锁,而只需简单的检验一下对象头的Mark Word里是否存储着指向当前线程的偏向锁,如果存在,表示线_轻量级锁和偏向锁,重量级锁

随便推点

ThinkPHP5(1)基础内容_thinkphp5csdn-程序员宅基地

文章浏览阅读248次。ThinkPHP5视频教程传送门安装1、安装Composer安装教程2、安装中国全量镜像安装教程3、安装tp安装在项目文件夹下composer create-project topthink/think通过localhost访问think目录下的public目录,如果出现以下图片则安装成功运行流程目录结构application目录:存放程序代码config目录:配置文件存放目录route目录:路由模块存放目录配置的获取与设置获取Config::get()设置_thinkphp5csdn

解决No module named beginner_tutorials.srv_importerror: no module named beginner_tutorials.sr-程序员宅基地

文章浏览阅读2k次。@解决No module named beginner_tutorials.srv练习服务的时候出的错看看自己 是不是这个目录 catkin_ws /src/beginner_tutorials如果不是,改为自己目录下的名字,我的是 catkin_ws /src/learning_communication改为from learning_communication.srv import *..._importerror: no module named beginner_tutorials.srv

C语言计算字符串长度的几种方法_c语言中自定义计算长度-程序员宅基地

文章浏览阅读4k次。C语言计算字符串长度的几种方法C语言计算字符串长度,可以手动计算也可以使用库函数或者sizeof()操作符。自定义函数求长度使用strlen()函数使用sizeof()操作符自定义函数int cont_str(char *s){ int i = 0; while ( str[i++] != '\0') ; ret_c语言中自定义计算长度

Inception 简单上手体验(更新中)_invalid remote backup information.-程序员宅基地

文章浏览阅读1.5k次。 一、安装1、下载和编译依赖包:bison、cmake、ncurses-devel、openssl、gcc-c++下载源码:[root@237_30 tmp]# git clone https://github.com/mysql-inception/inception.gitInitialized empty Git repository in /tmp/inceptio..._invalid remote backup information.

linux查询本机IP地址(可用于SSH访问)_linux查看ssh ip-程序员宅基地

文章浏览阅读7.2k次,点赞2次,收藏9次。ifconfig | grep inet返回结果:第一排是局域网IP(v4),第二排是局域网IPv6第三排是广域网IP(v4),第四排是广域网IPv6咱们只需要看第三排就Ok了。第三排inet后面那四个数,就是咱们远程ssh连接本机时用到的。假设第三排是"inet 10.11.12.123",那么ssh连接只需:ssh [email protected]这时默认连接端口是22。..._linux查看ssh ip

centos7 mysql允许连接_centos7 mysql允许远程连接设置-程序员宅基地

文章浏览阅读779次。Mysql为了安全性,在默认情况下用户只允许在本地登录,可是在有此情况下,还是需要使用用户进行远程连接,因此为了使其可以远程需要进行如下操作:一、允许root用户在任何地方进行远程登录,并具有所有库任何操作权限,具体操作如下:在本机先使用root用户登录mysql:mysql -u root -p"youpassword"进行授权操作:mysql>GRANT ALL PRIVILEGES O..._centos7 mysql 允许客户端连接

推荐文章

热门文章

相关标签