本文转载自微信公众号「神奇的程序员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类文件，声明解决本文问题所需要的变量

 
 
 
 

  
  
  
  
// 栈与队列的相关操作 
  
  
  
  
import Stack from "../../StackTest/lib/Stack.ts"; 
  
  
  
  
import Queue from "../../QueueTest/lib/Queue.ts"; 
  
  
  
  
 
  
  
  
  
export default class StacksAndQueues { 
  
  
  
  
    private firstStacks: Stack; 
  
  
  
  
    private secondStacks: Stack; 
  
  
  
  
    private firstQueues: Queue; 
  
  
  
  
    private secondQueues: Queue; 
  
  
  
  
 
  
  
  
  
    constructor() { 
  
  
  
  
        this.firstStacks = new Stack(); 
  
  
  
  
        this.secondStacks = new Stack(); 
  
  
  
  
        this.firstQueues = new Queue(); 
  
  
  
  
        this.secondQueues = new Queue(); 
  
  
  
  
    } 
  
  
  
  
} 
 
 
 
 

• 实现入队函数

 
 
 
 

  
  
  
  
// 入队 
  
  
  
  
    enqueue(key: string | number): void { 
  
  
  
  
        // 入栈1 
  
  
  
  
        this.firstStacks.push(key); 
  
  
  
  
    } 
 
 
 
 

• 实现出队函数

 
 
 
 

  
  
  
  
// 出队 
  
  
  
  
   dequeue() { 
  
  
  
  
       while (!this.firstStacks.isEmpty()) { 
  
  
  
  
           this.secondStacks.push(this.firstStacks.pop()); 
  
  
  
  
       } 
  
  
  
  
       if (!this.secondStacks.isEmpty()) { 
  
  
  
  
           // 出栈2 
  
  
  
  
           return this.secondStacks.pop(); 
  
  
  
  
       } 
  
  
  
  
       return null; 
  
  
  
  
   } 
 
 
 
 

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

 
 
 
 

  
  
  
  
import StacksAndQueues from "./lib/StacksAndQueues.ts"; 
  
  
  
  
 
  
  
  
  
// 用栈实现队列 
  
  
  
  
const stacksAndQueues = new StacksAndQueues(); 
  
  
  
  
stacksAndQueues.enqueue(3); 
  
  
  
  
stacksAndQueues.enqueue(9); 
  
  
  
  
stacksAndQueues.enqueue(12); 
  
  
  
  
console.log("出队", stacksAndQueues.dequeue()); 
  
  
  
  
console.log("出队", stacksAndQueues.dequeue()); 
  
  
  
  
console.log("出队", stacksAndQueues.dequeue()); 
 
 
 
 

队列实现栈

• 实现入栈函数

 
 
 
 

  
  
  
  
// 入栈 
  
  
  
  
   stackPush(key: string | number) { 
  
  
  
  
       // 入队1 
  
  
  
  
       this.firstQueues.enqueue(key); 
  
  
  
  
   } 
 
 
 
 

• 实现出栈函数

 
 
 
 

  
  
  
  
// 出栈 
  
  
  
  
    stackPop() { 
  
  
  
  
        if (this.firstQueues.isEmpty()) { 
  
  
  
  
            return null; 
  
  
  
  
        } 
  
  
  
  
        // 队列2为空 
  
  
  
  
        if (this.secondQueues.isEmpty()) { 
  
  
  
  
            while (this.firstQueues.size() != 1) { 
  
  
  
  
                // 将队列1除队首外的元素放进队列2 
  
  
  
  
                this.secondQueues.enqueue(this.firstQueues.dequeue()); 
  
  
  
  
            } 
  
  
  
  
        } 
  
  
  
  
 
  
  
  
  
        // 队列2不为空 
  
  
  
  
        while (!this.secondQueues.isEmpty()) { 
  
  
  
  
            // 将队列2的元素放进队列1 
  
  
  
  
            this.firstQueues.enqueue(this.secondQueues.dequeue()); 
  
  
  
  
        } 
  
  
  
  
        // 队列1出队 
  
  
  
  
        return this.firstQueues.dequeue(); 
  
  
  
  
    } 
 
 
 
 

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

 
 
 
 

  
  
  
  
// 队列实现栈 
  
  
  
  
stacksAndQueues.stackPush(3); 
  
  
  
  
stacksAndQueues.stackPush(9); 
  
  
  
  
stacksAndQueues.stackPush(12); 
  
  
  
  
console.log("出栈", stacksAndQueues.stackPop()); 
  
  
  
  
console.log("出栈", stacksAndQueues.stackPop()); 
  
  
  
  
console.log("出栈", stacksAndQueues.stackPop()); 
 
 
 
 

代码地址

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

• StacksAndQueues.ts

本文名称：队列实现栈&栈实现队列
文章起源：http://www.scanyue.cn/article/dpdcpho.html