栈的压入，栈的弹出 

 

输入两个整数序列，第一个序列表示栈的压入序列，判断第二个序列是否可能是该栈的弹出序列，假设压入栈中的所有数字均不相等，如pushA:1，2，3，4，5是某栈的压入序列，序列popA:4，5，3，2，1是该栈序列对应的一个弹出的一个弹出序列。

结论：栈为空的时候，说明是可能的出栈序列。

1.神魔时候入栈？

每次都入栈

2.神魔时候出栈？

栈不为空并且栈顶元素和k下标相等的时候可以出栈

3.定义i，j,都遍历完说明就是了

    public static boolean IsPopOrder(int[] pushA,int[] popA){Stack<Integer> stack=new Stack<>();int j=0;for (int i = 0; i < pushA.length; i++) {stack.push(pushA[i]);while(!stack.isEmpty()&&stack.peek()==popA[j]&&j<popA.length) {stack.pop();j++;}//在while里面判断的时候，stac弹出的已经是引用类型，这里就发生了自动拆箱//但是在牛客网中提交并没有问题}return stack.isEmpty();}

 

最小栈

/****给定stack，和minStack* 1.当栈中第一次存放数据时，两个栈中都要存放元素* 2.从第二次开始，每次入栈，都要和栈顶元素进行比较，小于的话就入栈* 此操作保证了minStack中的栈顶元素时当时的较小值；* 3.出栈：每次出栈都要和栈顶元素进行比较，如果和栈顶元素一样，那麽就要两个栈都得出** **/

import java.util.Stack;class MinStack {private Stack<Integer> stack ;private 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 {if(val <= minStack.peek()) {minStack.push(val);}}}public void pop() {//栈为空 则不能进行弹出元素if(stack.empty()) {return;}int val = stack.pop();if(val == minStack.peek()) {minStack.pop();}}//获取栈顶元素 和 最小栈没有关系public int top() {if(stack.empty()) {return -1;}return stack.peek();}//获取元素 不是删除元素public int getMin() {return minStack.peek();}public static void main(String[] args) {MinStack minStack1 = new MinStack();minStack1.push(-2);minStack1.push(0);minStack1.push(1);int x1 = minStack1.getMin();int x2 = minStack1.top();minStack1.pop();int x4 = minStack1.getMin();}
}

 

用队列实现栈

//栈：push,pop,peek;

//队列：offer,poll,peek

你觉得一个普通的队列能实现这个栈嘛？必然不能！

弄两个队列

1.push元素应该怎末放？

//放入不为空的队列

2.出栈？

将不为空的队列中的n-1个到另一个队列中。剩下的就是要出栈的元素

class MyStack {public Queue<Integer> qu1;public Queue<Integer> qu2;public MyStack() {qu1=new LinkedList<>();qu2=new LinkedList<>();}public void push(int x) {//只要放到不为空的队列中就行if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{qu1.offer(x);}}public int pop() {//两个队列都是空意味着栈是空的if(empty()){return -1;}//出不为空的队列if(!qu1.isEmpty()){//易错int currentSize=qu1.size();//注意：你的这个不能写死，如果全写在for中是不可以的，因为你的队列每弹出一个元素，大小都在变化for(int i=0;i<currentSize-1;i++){int x=qu1.poll();qu2.offer(x);}return qu1.poll();}if(!qu2.isEmpty()){int currentSize=qu2.size();for(int i=0;i<currentSize-1;i++){int x=qu2.poll();qu2.offer(x);}return qu2.poll();}return -1;}//peek（）方法public int top() {
//最后一个在x中存放的就是top元素if(empty()){return -1;}//出不为空的队列if(!qu1.isEmpty()){//易错int currentSize=qu1.size();//注意：你的这个不能写死，如果全写在for中是不可以的，因为你的队列每弹出一个元素，大小都在变化int x=-1;for(int i=0;i<currentSize;i++){x=qu1.poll();qu2.offer(x);}return x;}if(!qu2.isEmpty()){int currentSize=qu2.size();int x=-1;for(int i=0;i<currentSize;i++){x=qu2.poll();qu2.offer(x);}return x;}return -1;}public boolean empty() {return qu1.isEmpty()&&qu2.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();*/

 设计循环队列

以浪费一个空间判断

class MyCircularQueue {private int[] elem;private int front;//队头下标private int rear;//队尾下标public MyCircularQueue(int k) {this.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];}public boolean isEmpty() {return rear == front;}public boolean isFull() {return (rear+1) % elem.length == front;}// public static void main(String[] args) {//     MyCircularQueue myCircularQueue = new MyCircularQueue(3);//     System.out.println(myCircularQueue.enQueue(1));//     System.out.println(myCircularQueue.enQueue(2));//     System.out.println(myCircularQueue.enQueue(3));//     System.out.println(myCircularQueue.enQueue(4));//     System.out.println(myCircularQueue.Rear());//  2//     System.out.println(myCircularQueue.isFull());//     System.out.println(myCircularQueue.deQueue());//     System.out.println(myCircularQueue.enQueue(4));//     System.out.println(myCircularQueue.Rear());// }
}

成语解释