算法---两个栈实现一个队列

asoren 发布于2019-08-20 15:58 / 2810人阅读

摘要：但是数据结构知识的需要，数据结构中对队列栈的定义很明确栈，先进后出队列，先进先出现在要用两个栈实现一个队列，那么首先定义一个栈构造函数吧。

其实JS很“流氓的”，JS的数组完全既可以是队列也可以是栈。
因为数组的push,pop就是栈的一组方法嘛。
数据的push,shift就是队列的一组方法嘛。
但是数据结构知识的需要，数据结构中对队列、栈的定义很明确：

栈，先进后出

队列，先进先出

现在要用两个栈实现一个队列，那么首先定义一个栈构造函数吧。

定义一个栈Stack构造函数

new两个Stack，stack1,stack2

stack1实现队列的进就好了

stack2实现队列的出就好了
重点来了，进的时候去的是stack1，怎么从stack2出数据呢

当栈2为空，栈1不为空时，把栈1的数据依次pop出去到栈2中，这样再栈2pop时就是队列应该pop的数据了

上代码：

function Queue(){
    var items = [];
    function Stack() {
        var item = [];
        this.push = function (elem) {
            item.push(elem);
            return item;
        };
        this.pop = function () {
            return item.pop();
        };
        this.isEmpty = function () {
            return item.length === 0;
        };
        this.get = function () {
            return item;
        };
    }
    var stack1 = new Stack();
    var stack2 = new Stack();
    this.push = function (elem) {
        stack1.push(elem);
        return items.push(elem);
    }
    this.pop = function () {
        if(stack1.isEmpty() && stack2.isEmpty()){
            throw new Error("空队列");
        }
        if(stack2.isEmpty() && !stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    };
    this.get = function () {
        if(!stack2.isEmpty()){
            return stack2.get().reverse();
        }else{
            return items;
        }
    }
}
var queue = new Queue();
queue.push(0);
queue.push(1);
queue.push(2);
queue.get();
queue.pop();
queue.get();

云服务器 GPU云服务器两个栈 java 栈队列 java 栈队列面试 java 手写一个栈

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/82624.html

算法面试：队列实现栈的方案

摘要：基本解决方案按照上述的大体思路，我们给出解决方案入栈和出栈都在中完成，只作为临时中转空间。入栈入队出栈除队尾的元素外将其他所有元素出队，再入队中转暂存，然后将中的元素出队出栈。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇介绍的是如何用两个队列实现栈的问题。这道题作为上一篇文章算法面试：栈实现队列的方案的姊...

dabai 2019-08-16 11:06 评论0 收藏0
算法面试：栈实现队列的方案

摘要：解决方案二入队都在中进行，用于队列，同时保证所有元素都在一个栈里，且遵循以下约束入队不管空与否，都将中的所有元素压入中出队若中不为空，则直接从中弹出元素若为空，则说明队列为空，不能出队。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。本篇文章介绍一个有趣的问题：用两个栈实现一个队列。这道题来自互联网公司的算法面试...

韩冰 2019-08-19 10:43 评论0 收藏0
算法学习之数据结构线性表、堆、栈

摘要：栈底是固定的，而栈顶浮动的如果栈中元素个数为零则被称为空栈。入栈将数据保存到栈顶。链栈链栈是指栈的链式存储结构，是没有附加头节点的运算受限的单链表，栈顶指针是链表的头指针。一、喜欢单挑线性表 1.线性表的特性线性表是一个线性结构，它是一个含有n≥0个节点的有限序列。在节点中，有且仅有一个开始节点没有前驱并有一个后继节点，有且仅有一个终端节点没有后继并有一个前驱节点。其他的节点都有且...

huaixiaoz 2019-06-27 14:11 评论0 收藏0
【面试算法】由两个栈组成的队列

摘要：题目编写一个类，用两个栈实现队列，支持队列的基本操作，，代码实现【题目】编写一个类，用两个栈实现队列，支持队列的基本操作（add，poll，peek）代码实现 public class TwoStacksQueue { private Stack stackPush; private Stack stackPop; public TwoStacksQue...

wenshi11019 2019-08-14 15:17 评论0 收藏0
学习数据结构与算法之栈与队列

摘要：于是翻出了机房里的这本学习数据结构与算法开始学习程序员的基础知识。这本书用了我最熟悉的来实现各种数据结构和算法，而且书很薄，可以说是一本不错的入门教程。队列在头部删除元素，尾部添加元素。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算...

pingan8787 2019-08-20 18:37 评论0 收藏0