232.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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
思路
- 两个栈实现队列，栈为s1、s2
- s1作为队列出口，当push时若s1非空，需要s1->s2 ， s1.push，s2->s1 ;
- 保证s2始终是空栈，用作每次push倒换数据的辅助空间
复杂度
- 时间 push O(n)
- 空间 O(n)
import java.util.Stack;
//leetcode submit region begin(Prohibit modification and deletion)
class MyQueue {
Stack<Integer> s1 = new Stack<Integer>() ;
Stack<Integer> s2 = new Stack<Integer>() ;
int size ;
int front ;
public MyQueue() {
}
public void push(int x) {
if(s1.empty()){
front = x ;
}
//s1->s2
while (!s1.empty()) {
s2.push(s1.pop());
}
//s2.push
s2.push(x);
//s2->s1
while (!s2.empty()) {
s1.push(s2.pop());
}
}
public int pop() {
int r = s1.pop();
if(!s1.empty()){
front = s1.peek();
}
return r ;
}
public int peek() {
return front;
}
public boolean empty() {
return s1.empty();
}
}
均摊时间解法
思路
- 栈s2存储队列顺序数据，s1存储栈顺序数据，push时从s1进入，若s2为空，则s1->s2
- pop时，从s2 出，s2为空，s1->s2，摊分push的时间复杂度，两个栈可能同时有数据
- 平均时间复杂度O(1)
- 空间复杂度O(n)
import java.util.Stack;
//leetcode submit region begin(Prohibit modification and deletion)
class MyQueue {
Stack<Integer> s1 = new Stack<Integer>() ;
Stack<Integer> s2 = new Stack<Integer>() ;
int front ;
public MyQueue() {
}
public void push(int x) {
if(s1.empty()){
front = x ;
}
s1.push(x);
}
public int pop() {
if(s2.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
return s2.pop() ;
}
public int peek() {
if(!s2.empty()){
return s2.peek();
}
return front;
}
public boolean empty() {
return s1.empty()&& s2.empty();
}
}
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
思考
- 队列先进先出，把队列循环一遍，就可以实现把队首元素移至队尾（核心点）
- 每移动一个元素至队尾，则需要更新
top指针==队首元素
复杂度
- 时间O(n)
pop时队列循环了一遍 - 空间O(n)
import javax.sound.midi.Soundbank;
import java.util.LinkedList;
//leetcode submit region begin(Prohibit modification and deletion)
class MyStack {
Deque<Integer> que = new LinkedList<Integer>();
int top = 0 ;
public MyStack() {
}
public void push(int x) {
top = x ;
que.push(x);
}
public int pop() {
int size = que.size() - 1;
while(size>0){
int v = que.pop();
//队首元素即为栈结构的top
top = que.peek() ;
que.push(v);
size--;
}
return que.pop();
}
public int top() {
return top ;
}
public boolean empty() {
return que.isEmpty() ;
}
}
20.有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
输入：s = "([{}])"
输出：true
思考
- 成对出现的符号，用栈存储“另一半”，栈顶元素一定是和当前元素相同，主要是结合栈结构和符号的规律技巧
复杂度
- 时间 O(n)
- 空间 O(n)
import java.util.Stack;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean isValid(String s) {
if(s.length()%2!=0) return false;
//栈实现
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
switch (c){
//迭代左边符号，将右边符号存入栈
case '(':
stack.push(')');
break;
case '[':
stack.push(']');
break;
case '{':
stack.push('}');
break;
default:
//若迭代到右边符号，则校验栈顶元素是否相同
if(stack.isEmpty() || c != stack.pop()){
return false;
}
}
}
if (!stack.isEmpty()) {
return false;
}
return true;
}
}
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
思路
- “消消乐”思想，用栈存储已经遍历过的字符，下一个字符与栈顶比较，相同的话“抵消”，出栈
复杂度
- 时间 O(n)
- 空间 O(n)
import java.util.Stack;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public String removeDuplicates(String s) {
if(s.length() == 1) return s;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!stack.isEmpty() && c == stack.peek()) {
stack.pop();
}else{
stack.push(c);
}
}
char[] strs = new char[stack.size()];
int idx = stack.size() -1 ;
while (!stack.isEmpty()) {
strs[idx] = stack.pop();
idx -- ;
}
return new String(strs);
}
}
总结
- 两栈实现队列
- 保证一个栈为空，每次push时，将主栈数据“倒腾”到空栈，当前元素入主栈，再把元素倒腾回来，时间复杂度固定为O(n)
- 两个栈同时存在数据，一个栈S1存储“队列顺序”数组，作为出口，栈S2顺序存储入口，当S1为空时，一次性把S2数据“倒腾”至S1，每次从s1出栈，s2入栈，平均了时间复杂度
- 队列实现栈
- 一个队列循环（size-1）再入栈，即可将队尾元素移至队首
pty()) {
strs[idx] = stack.pop();
idx – ;
}
return new String(strs);
}
}
### 总结
+ 两栈实现队列
+ 保证一个栈为空，每次push时，将主栈数据“倒腾”到空栈，当前元素入主栈，再把元素倒腾回来，时间复杂度固定为O(n)
+ 两个栈同时存在数据，一个栈S1存储“队列顺序”数组，作为出口，栈S2顺序存储入口，当S1为空时，一次性把S2数据“倒腾”至S1，每次从s1出栈，s2入栈，平均了时间复杂度
+ 队列实现栈
+ 一个队列循环（size-1）再入栈，即可将队尾元素移至队首
+ “**消消乐**”思想，可用栈存储待“消除”的符号，难点在于找到栈初始化的规律，技巧在于多画图分析
本文含有隐藏内容，请 开通VIP 后查看