用栈实现队列
仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
思路：两个栈一个负责写入，一个负责弹出。核心是弹出栈要保持和队列一样的顺序。
当popStack为空时，将pushStack依次弹出写入popStack，这样子倒序就变为正序了。当popStack不为空时，则只需要弹出顶部的元素即可。pushStack仅需要写入即可。
class MyQueue {
private Stack<Integer> popStack = new Stack();
private Stack<Integer> pushStack = new Stack();
public MyQueue() {
}
public void push(int x) {
pushStack.push(x);
}
public int pop() {
if (popStack.isEmpty()) {
while (!pushStack.isEmpty()) {
popStack.push(pushStack.pop());
}
}
return popStack.pop();
}
public int peek() {
if (popStack.isEmpty()) {
while (!pushStack.isEmpty()) {
popStack.push(pushStack.pop());
}
}
return popStack.peek();
}
public boolean empty() {
return pushStack.isEmpty() && popStack.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
用队列实现栈
仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
思路：
核心点在于需要让一个队列保持栈一样的顺序，另一个队列作为辅助使用。这样子的话在插入的时候，就得先将值插入辅助队列，然后将popQueue一次插入tempQueue中。此时tempQueue就是栈的顺序了，但是我们约定popQueue才是负责输出的，因此要再依次将
tempQueue移动到popQueue；
class MyStack {
private Queue<Integer> popQueue=new LinkedList<>();
private Queue<Integer> tempQueue=new LinkedList<>();
public MyStack() {
}
public void push(int x) {
tempQueue.offer(x);
while (!popQueue.isEmpty()){
tempQueue.offer(popQueue.poll());
}
while (!tempQueue.isEmpty()){
popQueue.offer(tempQueue.poll());
}
}
public int pop() {
return popQueue.poll();
}
public int top() {
return popQueue.peek();
}
public boolean empty() {
return popQueue.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
有效的括号
public boolean isValid(String s) {
if(s.length()%2!=0){
return false;
}
Stack<Character> stack=new Stack();
char[] arr=s.toCharArray();
for(char c:arr){
if(c=='('||c=='['||c=='{'){
stack.push(c);
}else{
if(stack.isEmpty()){
return false;
}
if((c==')'&&stack.peek()!='(')
||(c==']'&&stack.peek()!='[')
||(c=='}'&&stack.peek()!='{')
){
break;
}
stack.pop();
}
}
return stack.isEmpty();
}
删除字符串中的所有相邻重复项
public String removeDuplicates(String s) {
Stack<Character> stack = new Stack<>();
char[] arr = s.toCharArray();
for (char c : arr) {
if (stack.isEmpty()) {
stack.push(c);
} else if (stack.peek() == c) {
stack.pop();
} else {
stack.push(c);
}
}
char[] result = new char[stack.size()];
for (int i = result.length - 1; i >= 0; i--) {
result[i] = stack.pop();
}
return new String(result);
}
滑动窗口最大值
思路：
使用一个单调队列，来存储单调递减的元素；这样可以保证在每个窗口的最大值是单调队列首位
当窗口向右移动时，会有入队和出队两个操作，因此，单调队列也需要有入队和出队的逻辑。针对于出队而言，单调队列的队首元素已经不在窗口范围，那就要移除队首。针对于入队操作，需要保证新入队的这个值保持单调队列的性质，因此要从单调队列的队尾一直弹出小于这个值的元素。
public static int[] maxSlidingWindow(int[] nums, int k) {
if (k == 1) {
return nums;
}
Deque<Integer> queue = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!queue.isEmpty() && nums[i]>nums[queue.peekLast()]) {
queue.pollLast();
}
queue.offer(i);
}
int[] result = new int[nums.length - k + 1];
for(int i=k;i<nums.length;i++){
if(queue.peekFirst()<i-k+1){
queue.pollFirst();
}
while (!queue.isEmpty() && nums[i]>nums[queue.peekLast()]) {
queue.pollLast();
}
result[i-k]=nums[queue.peekFirst()];
}
return result;
}