栈（Stack）和队列（Queue）是计算机科学中常用的数据结构，它们在算法和程序设计中扮演着重要的角色。下面是它们的理论基础：
栈的理论基础：
栈是一种具有特定行为的抽象数据类型（Abstract Data Type，ADT）。栈的特点是遵循后进先出（Last-In-First-Out，LIFO）的原则，也就是最后入栈的元素最先出栈。栈的操作有两个主要的操作：压入（Push）和弹出（Pop）。
1.压入（Push）操作：将元素添加到栈的顶部，成为新的栈顶。
2.弹出（Pop）操作：将栈顶的元素移除，并返回该元素的值。
栈还具有一个重要的属性，即栈顶指针（Top），它指向栈顶元素。当栈为空时，栈顶指针指向一个特殊的空值。
栈可以通过数组或链表来实现。使用数组实现的栈称为顺序栈（或称为数组栈），使用链表实现的栈称为链式栈。
队列的理论基础：
队列也是一种具有特定行为的抽象数据类型（ADT）。队列的特点是遵循先进先出（First-In-First-Out，FIFO）的原则，也就是最先入队的元素最先出队。队列的操作有两个主要的操作：入队（Enqueue）和出队（Dequeue）。
入队（Enqueue）操作：将元素添加到队列的尾部。
出队（Dequeue）操作：将队列头部的元素移除，并返回该元素的值。
队列还具有两个指针，即头指针（Front）和尾指针（Rear）。头指针指向队列的第一个元素，尾指针指向队列的最后一个元素。
队列可以通过数组或链表来实现。使用数组实现的队列称为顺序队列（或称为数组队列），使用链表实现的队列称为链式队列。
此外，还有一些常用的变种队列，例如循环队列（Circular Queue）和优先级队列（Priority Queue）。
栈和队列的应用非常广泛，它们在算法、操作系统、编译器等领域都有重要的作用。例如，在算法中，深度优先搜索（DFS）通常使用栈来实现，而广度优先搜索（BFS）通常使用队列来实现。
用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾
- int pop() 从队列的开头移除并返回元素
- int peek() 返回队列开头的元素
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
class MyQueue: def __init__(self): self.stack_in=[] self.stack_out=[] def push(self, x: int) -> None: self.stack_in.append(x) def pop(self) -> int: if self.empty(): return None if self.stack_out: return self.stack_out.pop() else: for i in range(len(self.stack_in)): self.stack_out.append(self.stack_in.pop()) return self.stack_out.pop() def peek(self) -> int: ans=self.pop() self.stack_out.append(ans) return ans def empty(self) -> bool: return not (self.stack_in or self.stack_out) # Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()
用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
class MyStack: def __init__(self): self.que = deque() def push(self, x: int) -> None: self.que.append(x) def pop(self) -> int: if self.empty(): return None for i in range(len(self.que)-1): self.que.append(self.que.popleft()) return self.que.popleft() def top(self) -> int: # 写法一： # if self.empty(): # return None # return self.que[-1] # 写法二： if self.empty(): return None for i in range(len(self.que)-1): self.que.append(self.que.popleft()) temp = self.que.popleft() self.que.append(temp) return temp def empty(self) -> bool: return not self.que # Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty()
