Chinaunix首页 | 论坛 | 博客
  • 博客访问: 995566
  • 博文数量: 135
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1780
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(135)

文章存档

2020年(32)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2018-07-28 20:04:21

又是一道面试题。。。
哎,前一阵子被面试笔试搞得有点疯,现在有点回归正轨的趋势,现在慢慢整理一下,想起来哪个就写哪个,下周应该就不是面试题目了~~~
当初一看到这个题目的第一反应就是,卧槽,我好像在哪里见到过,卧槽,我好像忘了具体怎么搞的了。。。好在当时灵光一闪,记起来要用两个栈,这样基本代码框架就出来了~~~

点击(此处)折叠或打开

  1. #ifndef MYQUEUE_H
  2. #define MYQUEUE_H
  3. #include <stack>

  4. class MyQueue
  5. {
  6. public:
  7.     MyQueue();
  8.     void enqueue(int element);
  9.     int dequeue();
  10.     int length();
  11. private:
  12.     std::stack<int> s1;
  13.     std::stack<int> s2;
  14. };

  15. #endif // MYQUEUE_H

接下来就是实现了,队列是先入先出(FIFO),栈是先入后出(LIFO),既然要用到两个栈,那就应该是来回倒了,选定一个栈用于入队,另一个栈用于出队,如果出队栈为空,则将入队栈元素全部倒入出队栈,再进行出队,代码如下:

点击(此处)折叠或打开

  1. #include "myqueue.h"

  2. MyQueue::MyQueue()
  3. {

  4. }
  5. void MyQueue::enqueue(int element){
  6.     s1.push(element);
  7. }
  8. int MyQueue::dequeue(){
  9.     int res, temp;
  10.     if(!s2.empty()){
  11.         res = s2.top();
  12.         s2.pop();
  13.     }else{
  14.         while(!s1.empty()){
  15.             temp = s1.top();
  16.             s1.pop();
  17.             s2.push(temp);
  18.         }
  19.         res = s2.top();
  20.         s2.pop();
  21.     }
  22.     return res;
  23. }
  24. int MyQueue::length(){
  25.     return s1.size()+s2.size();
  26. }

阅读(1016) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~