队列实现栈&栈实现队列

文中转载微信公众平台「奇妙的程序猿K」，创作者奇妙的程序猿K。转截文中请联络奇妙的程序猿K微信公众号。

序言

让你2个栈你怎样完成一个序列，让你2个序列你怎样完成一个栈。

文中就跟大伙儿共享下这两个难题的处理构思与完成全过程，热烈欢迎诸位很感兴趣的开发人员阅读文章文中。

问题分析

大家先看来下栈与序列的特点：

• 栈：最开始添加的原素最终出
• 序列：最开始添加的原素最开始出

相关栈与序列的详尽解读请移景我的另一篇文章：算法设计:栈与序列

拥有栈与序列的理论基础后，大家就可以运用其特点来分析问题了，大家先看来下怎样用栈来完成序列：

• 大家的已经知道标准仅有2个栈，将这两个栈开展标志：栈1、栈2
• 实行入队实际操作时，大家原素放入栈1。
• 实行出队实际操作时：
  • 把栈1的原素压进栈2
  • 栈2顶端原素出栈

所述构思中，大家用栈1来储存原素，我们知道栈的标准是先进先出，因而大家将栈1的原素压进栈2后，将栈两元素出栈时，恰好合乎序列的特点。

下面，大家看来下怎样用序列来完成栈：

• 一样的，大家的已经知道标准有两个序列，将这两个序列开展标志：序列1，序列2
• 实行入栈实际操作时，将原素放入序列1
• 实行出栈实际操作时：
  • 假如序列2为空，大家将序列1中除队首外的原素放入序列2
  • 假如序列2不以空，大家将序列2的原素放入序列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