【数据结构与算法】(6)：用两个栈实现一个队列

队列是一种 先进先出（FIFO）的数据结构，本文就演示一下 用两个栈(Stack)实现一个队列(Queue) 。

一、前言

• 队列是逻辑结构，是一个理论模型。
• 只能在队尾插入元素，在队头删除元素。

二、代码演示

export class MyQueue {
  private stack1: number[] = []
  private stack2: number[] = []

  add(n: number) {
    this.stack1.push(n)
  }
  delete():number | null {
    let res
    const stack1 = this.stack1
    const stack2 = this.stack2

    // 将 stack1 所有元素移动到 stack2 中
    while (stack1.length) {
      const n = stack1.pop()
      if (n!=null) {
        stack2.push(n)
      }
    }

    // stack2 pop
    res = stack2.pop()

    // 将 stack2 所有元素还给 stack1
    while (stack2.length) {
      const n = stack2.pop()
      if (n!=null) {
        stack1.push(n)
      }
    }

    return res || null

  }
  get length(): number {
    return this.stack1.length
  }
}

const q = new MyQueue()
q.add(100)
q.add(200)
q.add(300)
console.log(q.length)
console.log(q.delete())
console.log(q.length)
console.log(q.delete())
console.log(q.length)

• 逻辑结构 VS 物理结构

三、算法复杂度

• 时间复杂度 add O(1); delete O(n)
• 空间复杂度 整体是 O(n)

《数据结构与算法》系列

1. 什么是算法复杂度
2. 堆(heap)、栈(stack)、队列(queue)
3. 把一个数组旋转k步
4. 判断字符串是否括号匹配
5. 数组、栈、链表、队列结构与对比
6. 用两个栈实现一个队列
7. 反转单向链表
8. 用链表实现队列
9. 二分查找
10. 查找两数之和

欢迎访问：天问博客