栈

(1)逆波兰表达式求值

oj链接
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(int i = 0;i < tokens.length;i++) {String str = tokens[i];if(!isOperations(str)) {//不是运算符  说明是数字,压入栈stack.push(Integer.parseInt(str));}else {//是运算符int num2 = stack.pop();int num1 = stack.pop();switch(str) {case "+":stack.push(num1+num2);break;case "-":stack.push(num1-num2);break;case "*":stack.push(num1*num2);break;case "/":stack.push(num1/num2);break;}}}return stack.pop();}/*判断当前字符串是不是一个运算符 */private boolean isOperations(String str) {return (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/"));}
}

(2)有效的括号

oj链接
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();//1. 遍历字符串for(int i = 0;i < s.length();i++) {char ch = s.charAt(i);//2.是不是左括号if(ch == '(' || ch == '[' || ch == '{') {stack.push(ch);}else {//3.右括号//3.1 栈为空if(stack.isEmpty()) {return false;}//3.2 栈不为空char ch2 = stack.peek();//左括号if(ch == ')' && ch2 == '('  || ch == ']'&& ch2 == '[' || ch == '}' && ch2 == '{') {stack.pop();}else {return false;}}}//字符串遍历完了 栈还是不为空return stack.isEmpty();}
}

(3)栈的压入、弹出序列

牛客网链接
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000
2. -1000<=pushV[i]<=1000
3. pushV 的所有数字均不相同

public boolean IsPopOrder (int[] pushA, int[] popA) {Stack<Integer> stack = new Stack<>();//j是出栈的下标int j = 0;//i是入栈的下标for (int i = 0; i < pushA.length; i++) {stack.push(pushA[i]);while (!stack.empty() && j < popA.length && stack.peek() == popA[j]) {stack.pop();j++;}}//return j >= popA.length;return stack.empty();}

(4)最小栈

oj链接
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

class MinStack {Stack<Integer> stack;Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if(minStack.empty()) {minStack.push(val);} else {int peekNum = minStack.peek();if(val<=peekNum) {minStack.push(val);}}}public void pop() {int val = stack.pop();if(val == minStack.peek()) {minStack.pop();}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

队列

(1)用栈实现队列

oj链接
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

class MyQueue {private Stack<Integer> s1 ;private Stack<Integer> s2 ;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}public int pop() {if(empty()) {return -1;}if(s2.isEmpty()) {//弹出s1当中所有的元素 放到s2中while(!s1.isEmpty()) {s2.push(s1.pop());}}return s2.pop();}public int peek() {if(empty()) {return -1;}if(s2.isEmpty()) {//弹出s1当中所有的元素 放到s2中while(!s1.isEmpty()) {s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}

(2)用队列实现栈

oj链接
请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
两个队列

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll();}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}

一个队列

class MyStack {Queue<Integer> queue;/** Initialize your data structure here. */public MyStack() {queue = new LinkedList<Integer>();}/** Push element x onto stack. */public void push(int x) {int n = queue.size();queue.offer(x);for (int i = 0; i < n; i++) {queue.offer(queue.poll());}}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue.poll();}/** Get the top element. */public int top() {return queue.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue.isEmpty();}
}

(3)设计循环队列

oj链接
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
数组(创建时多一个元素)
当front与rear相等的时候,不知道是为空还是为满
所以front前面的元素不用来存放,front==rear时判空,(rear+1) % elem.length == front为满

class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {elem = new int[k+1];}//入队操作public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] = value;rear = (rear+1) % elem.length;return true;}//删除队头元素public boolean deQueue() {if(isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}//得到队头元素 不删除public int Front() {if(isEmpty()) {return -1;}return elem[front];}//得到队尾元素 不删除public int Rear() {if(isEmpty()) {return -1;}int index = (rear == 0) ? elem.length-1 : rear-1;return elem[index];}//判空 front和rear相遇public boolean isEmpty() {return front == rear;}public boolean isFull() {return (rear+1) % elem.length == front;}
}

链表

class MyCircularQueue {private ListNode head;private ListNode tail;private int capacity;private int size;public MyCircularQueue(int k) {capacity = k;size = 0;}public boolean enQueue(int value) {if (isFull()) {return false;}ListNode node = new ListNode(value);if (head == null) {head = tail = node;} else {tail.next = node;tail = node;}size++;return true;}public boolean deQueue() {if (isEmpty()) {return false;}head = head.next;  size--;return true;}public int Front() {if (isEmpty()) {return -1;}return head.val;}public int Rear() {if (isEmpty()) {return -1;}return tail.val;}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == capacity;}
}