用2个队列实现栈操作

简介:

一、文章来由

一道面试题,别说以前还真没好好想过,在未参考其他资料情况下自己想了两种,实现如下,如果另有高招,之后再补。

二、2种实现方式

分析:栈操作其实只有 push 和 pop 对栈内元素进行改变,我于是想从其一下手即可。

改变 push 操作:

比如输入,1 2 3 4 5,栈中结构应该是1在底,5在顶,但是队中元素是原顺序,如果要让push一个元素,让队列中的顺序反过来,就可以每推入一个元素,就用另一个队列中转把次序调整过来。

/* 
* 
* function: 用两个栈实现队列
* 
* Date:2016-03-15
* 
*    Author: Bill Wang
*/

#include <iostream>
#include <queue>

using namespace std;

template <class T>
class whStack
{
public:
    whStack(){}
    ~whStack(){}

    void push(T t);
    T pop();

private:
    std::queue<T> QueueA;
    std::queue<T> QueueB;
};

template<class T> void whStack<T>::push(T t) {

    //将另一个队列作为中转站

    //step1、将A队列所有元素推入B
    while ( !QueueA.empty() ) {
        T tmp = QueueA.front();
        QueueA.pop();
        QueueB.push(tmp);
    }

    //step2、推入新节点
    QueueA.push(t);

    //step3、将B队列回归A
    while ( !QueueB.empty() ) {
        T tmp = QueueB.front();
        QueueB.pop();
        QueueA.push(tmp);
    }

}

//pop时直接弹出并返回T
template<class T> T whStack<T>::pop() {

    T res = QueueA.front();
    QueueA.pop();
    return res;
}

int main() 
{
    whStack<int > s;

    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    cout<<s.pop()<<endl;
    cout<<s.pop()<<endl;
    cout<<s.pop()<<endl;

    return 0; 
}

这个输出:
5
4
3

但是这样相当于把另一个队列纯做中转,时间复杂度较高。

改变 pop 操作:

/* 
* 
* function: 用两个栈实现队列2
* 
* Date:2016-03-15
* 
*    Author: Bill Wang
*/

#include <iostream>
#include <queue>

using namespace std;

template <class T>
class whStack
{
public:
    whStack(){}
    ~whStack(){}

    void push(T t);
    T pop();

private:
    std::queue<T> QueueA;
    std::queue<T> QueueB;
};

template<class T> void whStack<T>::push(T t) {

    //判断哪一个队列非空
    if( !QueueA.empty() )
        QueueA.push(t);
    else
        QueueB.push(t);
}

//pop时直接弹出并返回T
template<class T> T whStack<T>::pop() {


    std::queue<T> &qa = QueueA.empty()? QueueB:QueueA;
    std::queue<T> &qb = QueueA.empty()? QueueA:QueueB;

    //将队尾最后一个元素留住,将其他元素入另一个队列
    T tmp;
    while (1) {

        tmp = qa.front();
        qa.pop();

        if( qa.empty() )
            break;

        qb.push(tmp);
    }

    return tmp;
}

int main() 
{
    whStack<int > s;

    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    cout<<s.pop()<<endl;
    cout<<s.pop()<<endl;
    cout<<s.pop()<<endl;

    return 0; 
}

同样输出:
5
4
3

三、复杂度分析

从源码可以看出,如果队列元素个数为n,他们的如果执行一对push和pop,都可以在线性时间 O(n),得出结果。

但是明显,第一种方法是将元素移进移出两次,一个队列始终为空,严格来说复杂度是 O(2n);第二种方法是两个队列轮流使用,省去一轮遍历,所以相较之下应该是 O(n),所以第二种更快一些。

相关文章
|
15天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
6天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
15 1
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
12天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
14天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
41 4
|
18天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
数据结构(栈与列队)
数据结构(栈与列队)
17 1
|
1月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
68 1
|
1月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
16 0
|
1月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
30 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器