今天我们刷一些栈队列的题目，大家还是先看题，后看题解。
思路：创建两个栈，一个栈所有元素都算，另一个栈只放小的元素，第二个栈中如果要放的元素比栈顶的元素小就放，这样我们直接pop第二个栈就能得到最小栈
class MinStack {
public Stack<Integer> stack;
public Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(minStack.isEmpty()){
minStack.push(val);
}
else{
if(stack.peek()<=minStack.peek()){
minStack.push(val);
}
}
}
public void pop() {
int a = stack.pop();
if(a==minStack.peek()){
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
if(minStack.isEmpty()){
return -1;
}
return minStack.peek();
}
}思路：我们要看括号匹配，无非就是看{},(),[]是否匹配。我们可以创建一个栈，先放我们的左括号，如果碰到了右括号就让栈里的，左括号出列看看是否与当前右括号匹配，另外，如果在没有左括号的情况下出现了右括号也是不行的。
class Solution {
public boolean isValid(String s) {
Stack<Character> stack1 = new Stack<>();
for(int i=0;i<s.length();i++){
char a = s.charAt(i);
if(a=='{' || a=='[' || a=='('){
stack1.push(a);
}
if(a=='}' || a==']' || a==')'){
if(stack1.isEmpty()){
return false;
}
char c = stack1.peek();
if((c=='{' && a=='}') || (c=='[' && a==']') || (c=='(' && a==')')){
stack1.pop();
}
else{
return false;
}
}
}
return stack1.isEmpty();
}
}3.栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
思路：先创建一个栈，遍历左数组，如果不等于右数组就把左数组中的元素放到栈中，如果相等了，就开始循环比对，pop Stack中对应的元素，如果最后栈为空就是正确的
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param pushV int整型一维数组
* @param popV int整型一维数组
* @return bool布尔型
*/
public boolean IsPopOrder (int[] pushV, int[] popV) {
Stack<Integer> stack1 = new Stack<>();
int j = 0;
for(int i=0;i<pushV.length;i++){
stack1.push(pushV[i]);
while(!stack1.isEmpty()&& j<popV.length && stack1.peek()==popV[j]){
stack1.pop();
j++;
}
}
return stack1.isEmpty();
}
}
4.150. 逆波兰表达式求值 - 力扣（LeetCode）
注释：在写代码之前，我们先了解下中缀表达式如何转后缀表达式
例如(1+2)*3 + 4怎么转成后缀表达式呢，教大家一个方法，先乘除后加减的加括号，再把符号移到括号后面，我来演示一下。
((1+2)*3)+4 (((1+2)*3)+4) ( ( 12+*3 ) + 4 ) ( 12+3* + 4 ) 12+3*4+
这有什么用呢，计算机是怎么计算这个算式的呢，他是去使用后缀表达式的。
思路：我们会创建一个栈，遇到数字就往里放，遇到符号，pop的第一个数字放到右边，第二个放到左边，让它进行对应符号位的计算，再放回栈，最后得到的数就是运算结果
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack1 = new Stack<>();
for(int i=0;i<tokens.length;i++){
if(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") ||
tokens[i].equals("/")){
int value2 = stack1.pop();
int value1 = stack1.pop();
if(tokens[i].equals("+")){
stack1.push(value1+value2);
}
if(tokens[i].equals("-")){
stack1.push(value1-value2);
}
if(tokens[i].equals("*")){
stack1.push(value1*value2);
}
if(tokens[i].equals("/")){
stack1.push(value1/value2);
}
}
else{
int a = Integer.parseInt(tokens[i]);
stack1.push(a);
}
}
return stack1.peek();
}
}思路：用队列实现栈，栈是先进后出，而队列是先进先出，所以我们最少需要两个队列来实现栈。
1，我们每次入栈列都把元素放到空的队列中
2，我们每次出栈都把不为空的队列中size-1个元素放到空的栈中，在把为一个元素的栈出队，就实现了队列模仿栈。
class MyStack {
public Queue<Integer> queue1;
public Queue<Integer> queue2;
public MyStack() {
queue1 = new ArrayDeque();
queue2 = new ArrayDeque();
}
public void push(int x) {
if(empty()){
queue1.offer(x);
}
else if(queue1.isEmpty()){
queue2.offer(x);
}
else if(queue2.isEmpty()){
queue1.offer(x);
}
}
public int pop() {
if(queue1.isEmpty()){
while(queue2.size()>1){
queue1.offer(queue2.poll());
}
return queue2.poll();
}
if(queue2.isEmpty()){
while(queue1.size()>1){
queue2.offer(queue1.poll());
}
return queue1.poll();
}
return -1;
}
public int top() {
int tmp = 0;
if(queue1.isEmpty()){
while(queue2.size()>0){
tmp = queue2.peek();
queue1.offer(queue2.poll());
}
return tmp;
}
if(queue2.isEmpty()){
while(queue1.size()>0){
tmp = queue1.peek();
queue2.offer(queue1.poll());
}
return tmp;
}
return -1;
}
public boolean empty() {
return queue1.isEmpty() && queue2.isEmpty();
}
}思路：反过来，用栈实现队列也一样我们使用一个栈肯定是不够的，我们创建两个栈一个用来入栈，一个用来出栈，push操作我们只把元素存到inStack，pop操作我们把push的元素都拿过来之后出栈第一个元素，再把所有的元素放回inStack。
class MyQueue {
public Stack<Integer> instack;
public Stack<Integer> outstack;
public MyQueue() {
instack = new Stack<>();
outstack = new Stack<>();
}
public void push(int x) {
instack.push(x);
}
public int pop() {
if(empty()){
return -1;
}
while(instack.size()>0){
outstack.push(instack.pop());
}
int a = outstack.pop();
while(outstack.size()>0){
instack.push(outstack.pop());
}
return a;
}
public int peek() {
if(empty()){
return -1;
}
while(instack.size()>0){
outstack.push(instack.pop());
}
int a = outstack.peek();
while(outstack.size()>0){
instack.push(outstack.pop());
}
return a;
}
public boolean empty() {
return instack.isEmpty() && outstack.isEmpty();
}
}思路：我们用数组来设计循环队列，把数组想象成一个环，
让head当做头，rear往后走，留一个零我们不放数据，让head和rear的移动作为队列元素的移动，当head==rear时，队列为空，当rear的下一个元素是head时，队列为满，rear的移动为入栈，head的移动为出栈，
class MyCircularQueue {
public int[] str;
public int front;
public int rear;
public MyCircularQueue(int k) {
str = new int[k+1];
front =0;
rear = 0;
}
public boolean enQueue(int value) {
if(isFull()){
return false;
}
str[rear] = value;
rear = (rear+1)%str.length;
return true;
}
public boolean deQueue() {
if(isEmpty()){
return false;
}
front = (front+1)%str.length;
return true;
}
public int Front() {
if(isEmpty()){
return -1;
}
return str[front];
}
public int Rear() {
if(isEmpty()){
return -1;
}
if(rear==0){
return str[str.length-1];
}
return str[rear-1];
}
public boolean isEmpty() {
return front==rear;
}
public boolean isFull() {
return (rear+1)%str.length==front;
}
}