最近看了个面试的帖子讲的是 "怎么用两个栈来实现队列的操作", 好奇的我也想试下这道题目, 咋一看这道题目挺简单的呀, 嗯, 确实不难. 先简单讲下我第一眼看到这个题目时想到的解法. 讲解法之前先给大家讲下数据结构中的栈和队列吧, 免得有的人不明白栈和队列, 那就没办法继续看下去了.
栈 (stack)(wiki)
我们经常会在面试中听到 "栈" 这个词语, 理解这个概念对于理解程序的运行至关重要. 栈这个词语在不同的语境中表达的含义是不同的. 下面我将解释下栈的三种含义 (参考:《Stack 的三种含义》 http://www.ruanyifeng.com/blog/2013/11/stack.html ).
含义一: 数据结构
我们这里讲的其实就是这种含义, stack 是一种存储数据的结构, 特点是 LIFO, 即后进先出 (last in First out).
这种数据结构其底层是用链表来现实的, 最大特点是只能操作最上面的元素, 所以先进栈的被压在下面只能后出栈.
这种数据结构通常又下面几种方法来操作最上面的元素:
push : 进栈
pop : 出栈
top : 获取栈顶元素
empty : 判断栈是否为空
含义二: 代码的运行方式
stack 的第二种含义是 "调用栈", 表示函数像积木一样的堆放, 以供层层调用, 我们在函数中的递归就是用堆栈实现的, 递归简单点来说就是函数中调用该函数.
含义三: 内存区域
stack 的第三种含义就是存储数据的一种内存区域. 程序在运行时需要一定的空间来存储数据. 一般来说系统会划分出两种不同的内存空间, 一种是栈 (stack), 另一种是堆 (heap).
栈是由操作系统自动分配和释放的, 存放函数的参数值, 局部变量值等. 堆一般由程序员分配并释放, 若程序员不释放, 程序结束时可能由 OS 回收, 分配方式类似于链表. 我们经常讲的内存泄漏其实就是指的就是堆.
介绍完了栈的定义, 简单说下栈和队列的区别吧, 栈的特点是先进的后出, 队列的特点是先进的先出. 这道题目考查的重点还是对于栈和队列特性的理解, 其次再加上一些思考就好了.
看完这道题目我其实第一反应就觉得这道题挺简单的, 新建两个栈 s1,s2, 然后当有入栈请求的时候先将 s1 栈中的数据依次出栈进入到 s2 的栈中, 然后将新请求入栈的数据放入 s1 中, 最后将 s2 栈中数据依次出栈进入到 s1 栈中. 每次有出栈请求的时候将 s1 栈中的数据出栈就好了. 这种解法应该是比较常规的解法, 也比较容易想到的.
但是仔细想下这种方法效率比较低, 有频繁的出栈和入栈操作, 对于性能的影响比较大, 那有没有什么更好的方法能解决这个问题呢? 其实我们可以在出栈的时候把栈底元素取出来, 入栈的时候正常入栈. 具体实现就是当有入栈请求的时候将数据压入栈 s1, 当有出栈请求的时候将 s1 数据依次出栈压入 s2 栈中, 那么这时 s2 的栈顶元素就是 s1 的栈底元素, 最后将 s2 的数据又依次压入 s1 中. 这么这样的话就只有出栈的操作会有频繁的栈操作, 对于入栈来讲没有额外的栈操作. 这种方法其实效率已经非常高了.
其实还有一种效率更高的方法来解决这个问题, 仔细想下这么问题, 将上面的解法做个优化, 将 s1 栈中的数据依次压入 s2 中后又依次压入 s1 中,** 那为什么又要将 s2 中的数据重新压回 s1 呢?** 其实这步操作可以避免, 我们可以当有入栈的操作时将数据压入 s1, 当有出栈操作时将 s2 中的数据出栈, 若 s2 栈为空, 则将 s1 中的数据全部依次压入 s2 中, 这样的方法效率会比上面的方法更优.
下面的代码就是上面提到的最后一种方法的实现:
- #include <iostream>
- #include <cstdio>
- #include <stack>
- #include <algorithm>
- using namespace std;
- std::stack<int>s1, s2;
- int main()
- {
- printf("Please input argument:1 push,2 pop\n");
- int operation, num;
- while(scanf("%d", &operation) != EOF)
- {
- if(operation == 1)
- {
- printf("please input queue push num:");
- scanf("%d", &num);
- s1.push(num);
- }
- else if(operation ==2)
- {
- if(!s2.empty())
- {
- printf("Queue pop num: %d\n", s2.top());
- s2.pop();
- }
- else if(!s1.empty())
- {
- while(!s1.empty())
- {
- s2.push(s1.top());
- s1.pop();
- }
- printf("Queue pop num: %d\n", s2.top());
- s2.pop();
- }
- else
- {
- printf("queue empty\n");
- }
- }
- else
- {
- printf("Input invalid, please input repeat");
- }
- }
- return 0;
- }
来源: https://juejin.im/post/5c83371ef265da2dac457fa5