Loveyless的学习笔记

Appearance

Return to top
On this page

题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

题解

自己做出来了 这道题其实还是比较简单的

主要的思路就是两个栈怎么实现队列结构？

一个输出栈一个输入栈

最重要的是当输出栈为空时 才把输入栈的数据依次放入输出栈

ts
class MyQueue {
  //输入栈
  arr1 = [];
  //输出栈
  arr2 = [];

  constructor() {}

  push(x: number): void {
    this.arr1.push(x);
    console.log("pushhh", this.arr1);
  }

  pop(): number {
    this.pushArr2();
    //取出输出栈顶元素
    console.log("popopop", this.arr2);
    return this.arr2.pop();
  }

  peek(): number {
    this.pushArr2();
    //返回输出栈顶元素
    console.log("ppp", this.arr2);
    return this.arr2[this.arr2.length - 1];
  }

  empty(): boolean {
    this.pushArr2();
    return this.arr2.length === 0;
  }

  pushArr2() {
    //如果输出栈为空!(这里为空才是关键 如果不为空就往里放想想后果) 则拿输入栈的数据放入输出栈
    if (this.arr2.length == 0) {
      //这里需要存一下长度 要不然循环会出错
      let long = this.arr1.length;
      for (let i = 0; i < long; i++) {
        this.arr2.push(this.arr1.pop());
      }
    }
  }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

const m = new MyQueue();
m.push(1);
m.push(2);
m.push(3);
m.peek();