队列实现栈&栈实现队列

本文转载自微信公众号「神奇的程序员K」，作者神奇的程序员K。转载本文请联系神奇的程序员K公众号。

创新互联建站自2013年创立以来，先为郸城等服务建站，郸城等地企业，进行企业商务咨询服务。为郸城企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

前言

给你两个栈你如何实现一个队列，给你两个队列你如何实现一个栈。

本文就跟大家分享下这两个问题的解决思路与实现过程，欢迎各位感兴趣的开发者阅读本文。

问题分析

我们先来看下栈与队列的特性：

  • 栈：最先加入的元素最后出
  • 队列：最先加入的元素最先出

有关栈与队列的详细讲解请移步我的另一篇文章：数据结构:栈与队列

有了栈与队列的理论基础后，我们就可以利用其特性来分析问题了，我们先来看下如何用栈来实现队列：

  • 我们的已知条件只有两个栈，将这两个栈进行标识：栈1、栈2
  • 执行入队操作时，我们元素放进栈1。
  • 执行出队操作时：
    • 把栈1的元素压入栈2
    • 栈2顶部元素出栈

上述思路中，我们用栈1来存储元素，我们知道栈的规则是先进后出，因此我们将栈1的元素压入栈2后，将栈2元素出栈时，刚好符合队列的特性。

接下来，我们来看下如何用队列来实现栈：

  • 同样的，我们的已知条件有两个队列，将这两个队列进行标识：队列1，队列2
  • 执行入栈操作时，将元素放进队列1
  • 执行出栈操作时：
    • 如果队列2为空，我们将队列1中除队首外的元素放进队列2
    • 如果队列2不为空，我们将队列2的元素放进队列1
    • 队列1元素出队

上述思路中，我们将元素都放入了队列1，出栈时，我们只保留队列1的队首元素，其他元素全部放入了队列2，随后将队列2的元素又放回了队列1，最后将队列1的元素出队，经过我们的这番倒腾后，刚好符合了栈的特性。

实现代码

经过上述分析，我们有了实现思路，接下来我们就将上述思路转化为具体的代码，下述代码中将引入我们之前写好的队列与栈的实现代码，对此不了解的开发者请移步我的另外两篇文章：数组实现栈与对象实现栈、队列与双端队列的实现

栈实现队列

  • 创建StacksAndQueues类文件，声明解决本文问题所需要的变量
 
 
 
 
    
  
  
  
  
  1. // 栈与队列的相关操作 
    2.   
  
  
  
  2. import Stack from "../../StackTest/lib/Stack.ts"; 
    3.   
  
  
  
  3. import Queue from "../../QueueTest/lib/Queue.ts"; 
    4.   
  
  
  
  4.  
    5.   
  
  
  
  5. export default class StacksAndQueues { 
    6.   
  
  
  
  6.     private firstStacks: Stack; 
    7.   
  
  
  
  7.     private secondStacks: Stack; 
    8.   
  
  
  
  8.     private firstQueues: Queue; 
    9.   
  
  
  
  9.     private secondQueues: Queue; 
    10.   
  
  
  
  10.  
    11.   
  
  
  
  11.     constructor() { 
    12.   
  
  
  
  12.         this.firstStacks = new Stack(); 
    13.   
  
  
  
  13.         this.secondStacks = new Stack(); 
    14.   
  
  
  
  14.         this.firstQueues = new Queue(); 
    15.   
  
  
  
  15.         this.secondQueues = new Queue(); 
    16.   
  
  
  
  16.     } 
    17.   
  
  
  
  17. } 
    18.
  • 实现入队函数
 
 
 
 
    
  
  
  
  
  1. // 入队 
    2.   
  
  
  
  2.     enqueue(key: string | number): void { 
    3.   
  
  
  
  3.         // 入栈1 
    4.   
  
  
  
  4.         this.firstStacks.push(key); 
    5.   
  
  
  
  5.     } 
    6.
  • 实现出队函数
 
 
 
 
    
  
  
  
  
  1. // 出队 
    2.   
  
  
  
  2.    dequeue() { 
    3.   
  
  
  
  3.        while (!this.firstStacks.isEmpty()) { 
    4.   
  
  
  
  4.            this.secondStacks.push(this.firstStacks.pop()); 
    5.   
  
  
  
  5.        } 
    6.   
  
  
  
  6.        if (!this.secondStacks.isEmpty()) { 
    7.   
  
  
  
  7.            // 出栈2 
    8.   
  
  
  
  8.            return this.secondStacks.pop(); 
    9.   
  
  
  
  9.        } 
    10.   
  
  
  
  10.        return null; 
    11.   
  
  
  
  11.    } 
    12.

接下来，我们通过一个例子来验证下上述代码能否正常执行：

 
 
 
 
    
  
  
  
  
  1. import StacksAndQueues from "./lib/StacksAndQueues.ts"; 
    2.   
  
  
  
  2.  
    3.   
  
  
  
  3. // 用栈实现队列 
    4.   
  
  
  
  4. const stacksAndQueues = new StacksAndQueues(); 
    5.   
  
  
  
  5. stacksAndQueues.enqueue(3); 
    6.   
  
  
  
  6. stacksAndQueues.enqueue(9); 
    7.   
  
  
  
  7. stacksAndQueues.enqueue(12); 
    8.   
  
  
  
  8. console.log("出队", stacksAndQueues.dequeue()); 
    9.   
  
  
  
  9. console.log("出队", stacksAndQueues.dequeue()); 
    10.   
  
  
  
  10. console.log("出队", stacksAndQueues.dequeue()); 
    11.

队列实现栈

  • 实现入栈函数
 
 
 
 
    
  
  
  
  
  1. // 入栈 
    2.   
  
  
  
  2.    stackPush(key: string | number) { 
    3.   
  
  
  
  3.        // 入队1 
    4.   
  
  
  
  4.        this.firstQueues.enqueue(key); 
    5.   
  
  
  
  5.    } 
    6.
  • 实现出栈函数
 
 
 
 
    
  
  
  
  
  1. // 出栈 
    2.   
  
  
  
  2.     stackPop() { 
    3.   
  
  
  
  3.         if (this.firstQueues.isEmpty()) { 
    4.   
  
  
  
  4.             return null; 
    5.   
  
  
  
  5.         } 
    6.   
  
  
  
  6.         // 队列2为空 
    7.   
  
  
  
  7.         if (this.secondQueues.isEmpty()) { 
    8.   
  
  
  
  8.             while (this.firstQueues.size() != 1) { 
    9.   
  
  
  
  9.                 // 将队列1除队首外的元素放进队列2 
    10.   
  
  
  
  10.                 this.secondQueues.enqueue(this.firstQueues.dequeue()); 
    11.   
  
  
  
  11.             } 
    12.   
  
  
  
  12.         } 
    13.   
  
  
  
  13.  
    14.   
  
  
  
  14.         // 队列2不为空 
    15.   
  
  
  
  15.         while (!this.secondQueues.isEmpty()) { 
    16.   
  
  
  
  16.             // 将队列2的元素放进队列1 
    17.   
  
  
  
  17.             this.firstQueues.enqueue(this.secondQueues.dequeue()); 
    18.   
  
  
  
  18.         } 
    19.   
  
  
  
  19.         // 队列1出队 
    20.   
  
  
  
  20.         return this.firstQueues.dequeue(); 
    21.   
  
  
  
  21.     } 
    22.
  • 接下来，我们通过一个例子来验证下上述代码能否正常执行：
 
 
 
 
    
  
  
  
  
  1. // 队列实现栈 
    2.   
  
  
  
  2. stacksAndQueues.stackPush(3); 
    3.   
  
  
  
  3. stacksAndQueues.stackPush(9); 
    4.   
  
  
  
  4. stacksAndQueues.stackPush(12); 
    5.   
  
  
  
  5. console.log("出栈", stacksAndQueues.stackPop()); 
    6.   
  
  
  
  6. console.log("出栈", stacksAndQueues.stackPop()); 
    7.   
  
  
  
  7. console.log("出栈", stacksAndQueues.stackPop()); 
    8.

代码地址

本文实现代码的完整地址如下：

  • StacksAndQueues.ts

文章标题：队列实现栈&栈实现队列
本文网址：http://www.shufengxianlan.com/qtweb/news14/119314.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

品牌网站制作知识

同城分类信息

电商网站建设方案　　 　达州网站设计　　 　网站免费收录　　 　小谭网创广告　　 　消防维保　　 　成都门窗定制　　 　软文推广公司　　 　广西弘博建站　　 　VI设计　　 　定制网站建设多少钱　　 　绵阳电信机房　　 　成都服务器租赁　　 　眉山联通机房　　 　移动手机网站制作　　 　安防网站建设方案　　 　成都服务器托管　　 　自贡主机托管　　 　绵阳电信机房　　 　绵阳网站制作　　 　娃娃鱼鱼苗