企业官网建设流程全解析

一、用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop和empty）。

实现MyStack类：

• void push(int x)将元素 x 压入栈顶。
• int pop()移除并返回栈顶元素。
• int top()返回栈顶元素。
• boolean empty()如果栈是空的，返回true；否则，返回false。

思路：每次push，都将之前已存在的元素做一遍出队入队操作，这样刚push进的数位于队头。

class MyStack: def __init__(self): self.queue=deque() def push(self, x: int) -> None: n=len(self.queue) self.queue.append(x) for _ in range(n): self.queue.append(self.queue.popleft()) def pop(self) -> int: return self.queue.popleft() def top(self) -> int: return self.queue[0] def empty(self) -> bool: return len(self.queue) == 0

二、用栈实现队列

读者来到图书馆排队借还书，图书管理员使用两个书车来完成整理借还书的任务。书车中的书从下往上叠加存放，图书管理员每次只能拿取书车顶部的书。排队的读者会有两种操作：

• push(bookID)：把借阅的书籍还到图书馆。
• pop()：从图书馆中借出书籍。

为了保持图书的顺序，图书管理员每次取出供读者借阅的书籍是最早归还到图书馆的书籍。你需要返回每次读者借出书的值。

如果没有归还的书可以取出，返回-1。

示例 1：

输入： ["BookQueue", "push", "push", "pop"] [[], [1], [2], []] 输出：[null,null,null,1] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.pop(); // return 1, queue is [2]

思路：两个栈结合。是不用来回倒腾的，只需要在 B 栈没元素了，再从 A 栈 补充即可。

class CQueue: def __init__(self): self.A, self.B = [], [] def appendTail(self, value: int) -> None: self.A.append(value) def deleteHead(self) -> int: if self.B: return self.B.pop() if not self.A: return -1 while self.A: self.B.append(self.A.pop()) return self.B.pop()

自己写的一版时间复杂度高的版本（上面的优化代码真的是妙极了）：

class CQueue: def __init__(self): self.stack = [] self.temStack = [] def appendTail(self, value: int) -> None: self.stack.append(value) def deleteHead(self) -> int: while self.stack: self.temStack.append(self.stack.pop()) res=self.temStack.pop() if self.temStack else -1 while self.temStack: self.stack.append(self.temStack.pop()) return res