队列是先进先出的,就像排队一样,谁在前谁先获得服务
栈是一种先进后出的数据结构
一、用栈实现队列
题目:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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(双端队列)来模拟一个栈,只要是标准的栈操作即可。
示例 1:
输入: ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 1, 1, false]解释: MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false
思路:
如何用栈实现先进先出的操作呢?
由于栈底元素是第一个入栈的,为了让他在栈结构中变成第一个出栈的元素,可以设置两种栈,一种负责入栈,一种负责出栈, 如果要实现先进先出,可以让元素先进入栈(push),当需要返回首元素时(peek)将入栈中的元素传进出栈中,这样出栈中第一个出去的元素就是入栈中的栈底元素了
代码:
class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn = new Stack<>();stackOut = new Stack<>();}public void push(int x) {stackIn.push(x);}public int pop() {dumpstackIn();return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}private void dumpstackIn() {if (!stackOut.isEmpty())return;while (!stackIn.isEmpty()) {stackOut.push(stackIn.pop());}}
}
解释每个方法的功能:
-
构造函数
MyQueue()
:- 初始化两个栈
stackIn
和stackOut
,stackIn
用于入队操作,stackOut
用于出队操作。
- 初始化两个栈
-
push(int x)
方法:- 将元素
x
压入stackIn
中,实现入队操作。
- 将元素
-
pop()
方法:- 调用
dumpstackIn()
方法确保stackOut
中有元素(如果为空的话),然后弹出stackOut
的栈顶元素,即实现出队操作。
- 调用
-
peek()
方法:- 同样调用
dumpstackIn()
方法确保stackOut
中有元素,然后返回stackOut
的栈顶元素,即查看队首元素但不移除。
- 同样调用
-
empty()
方法:- 判断两个栈是否都为空,如果都为空则队列为空。
-
辅助方法
dumpstackIn()
:- 当需要从
stackOut
取元素时,确保stackOut
中有元素,如果stackOut
为空,则将stackIn
中的所有元素逐个弹出并压入stackOut
,以实现从队列头部取元素。
- 当需要从
以示例进行代码分析:
输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]
初始化队列,创建一个空队列
MyQueue myQueue = new MyQueue();
push操作,队列变为[1]
myQueue.push(2);
再次push操作,队列变为[1,2]
myQueue.push(1);
peek操作,返回队首元素,即为1
myQueue.peek();
pop移除队首元素并返回,此时队列变为:[2]
myQueue.pop();
empty判断队列是否为空,此时队列为:[2],不为空,因此返回false
myQueue.empty();
二、用队列实现栈
题目:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push
、top
、pop
和 empty
)。
实现 MyStack
类:
void push(int x)
将元素 x 压入栈顶。int pop()
移除并返回栈顶元素。int top()
返回栈顶元素。boolean empty()
如果栈是空的,返回true
;否则,返回false
。
注意:
- 你只能使用队列的标准操作 —— 也就是
push to back
、peek/pop from front
、size
和is empty
这些操作。 - 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
示例:
输入: ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出: [null, null, null, 2, 2, false]解释: MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
思路:
队列实现栈的方法有很多,可以像栈实现队列一样用两个队列,一个存储一个输出,但是这种方法比较麻烦一些,用一个队列实现一个栈会更加简单,如何实现呢,由于队列是先进先出的,栈顶元素的返回即为队列中刚进队的队头元素, 如何用一个队列实现返回队头元素呢,只需要将队列中其他的元素全部出队,然后再次进队,留下的唯一元素就是所需的对头元素了,即为栈顶的元素
代码:
class MyStack {Queue<Integer> queue;// 辅助方法:重新排列队列中的元素,将队列头部的元素移到尾部public void rePosition() {int size = queue.size();size--; // 将队列最后一个元素移到队首之前的所有元素挪动到末尾while (size-- > 0) {queue.add(queue.poll()); // 将队列的头部元素移到尾部}}// 构造函数:初始化一个空队列public MyStack() {queue = new LinkedList<>();}// 入栈操作:将元素加入队列尾部public void push(int x) {queue.add(x);}// 出栈操作:调用 rePosition() 将队列头部元素移到尾部,然后移除队列的头部元素并返回public int pop() {rePosition();return queue.poll(); // 弹出队列的头部元素}// 获取栈顶元素:调用 rePosition() 将队列头部元素移到尾部,然后获取队列的头部元素并返回,再将该元素重新加入队列尾部public int top() {rePosition();int result = queue.poll(); // 弹出队列的头部元素queue.add(result); // 将该元素重新加入队列尾部,模拟栈的操作return result; // 返回栈顶元素}// 判断栈是否为空:判断队列是否为空public boolean empty() {return queue.isEmpty();}
}
解释每个方法的功能:
-
构造函数
MyStack()
:- 初始化一个空的队列
queue
,用来存储栈的元素。
- 初始化一个空的队列
-
rePosition()
方法:- 重新排列队列中的元素,将队列的头部元素移到尾部,以实现栈的后进先出特性。它通过将队列中的前面的元素依次移动到队列尾部来完成。
-
push(int x)
方法:- 将元素
x
加入队列的尾部,实现栈的入栈操作。
- 将元素
-
pop()
方法:- 调用
rePosition()
方法将队列的头部元素移到尾部,然后移除队列的头部元素并返回,模拟栈的出栈操作。
- 调用
-
top()
方法:- 调用
rePosition()
方法将队列的头部元素移到尾部,然后获取队列的头部元素并返回,再将该元素重新加入队列的尾部。这样可以返回栈顶元素但不移除它,模拟栈的获取栈顶元素操作。
- 调用
-
empty()
方法:- 判断队列是否为空,从而判断栈是否为空。
以示例进行代码分析:
输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]
创建栈对象,返回值为空
MyStack myStack = new MyStack();
将元素1入栈,此时栈中元素为[1]
myStack.push(1);
将元素2入栈,此时栈中元素为[1,2]
myStack.push(2);
调用top方法,返回栈顶元素,返回值为2
myStack.top();
调用pop方法移除并返回栈顶元素,移除返回的元素为2,此时栈中元素为[1]
myStack.pop();
调用empty方法判断,此时栈中不为空,因此返回false
myStack.empty();
三、有效的括号
题目:
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
思路:
可以使用栈结构存储对应左括号的右括号类型,当检索到右括号时与栈顶匹配,分为三种情况
第一种:遍历完所有元素后,栈中仍有元素,说明有相应的左括号没有右括号来匹配(左括号数量多于右括号)
第二种:遍历过程中,栈中没有要匹配的字符
第三种,遍历过程中,发现栈已经为空(右括号多于左括号)
当字符串全部遍历完且栈为空,说明左右括号均匹配
代码:
public boolean isValid(String s) {Stack<Character> stack = new Stack<>();char c;for (int i = 0; i < s.length(); i++) {//使用一个 for 循环遍历字符串 s 的每个字符,从头到尾依次处理每个字符。c = s.charAt(i);//如果当前字符 c 是左括号 '(', '[', '{',则将对应的右括号 ')', ']', '}' 推入栈中//这样,栈中存放的就是遇到的左括号所对应的期望右括号。if (c == '(')stack.push(')');else if (c == '[')stack.push(']');else if (c == '{')stack.push('}');//如果当前字符 c 是右括号 ')', ']', '}',则检查栈顶的字符是否与 c 匹配//如果栈为空(即没有左括号与之对应),或者栈顶字符与 c 不匹配,说明当前的括号序列不合法,直接返回 false。//如果栈顶字符与 c 匹配,则将栈顶元素弹出,表示找到了一个匹配的括号对。else if (stack.isEmpty() || stack.peek() != c) {return false;} else {stack.pop();}}//最后,检查栈是否为空。//如果栈为空,说明所有的左括号都找到了对应的右括号,返回 true,表示输入的字符串 s 是有效的括号序列;否则返回 false,表示存在未匹配的括号return stack.isEmpty();
}
今天的学习就到这里了