java">package StackSimulate;import java.util.Arrays;public class MyStack {private int usedSize;//栈里的有效元素//如果我们在栈外就不需要这个变量来访问元素的个数了，应该使用size();private int [] elem;//栈底层是由数组实现的，它继承的Vector底层就是数组实现的//当然单双链表也可以，但是单链表尾巴进就麻烦了，没有lastprivate static final int DEFAULT_CAPACITY = 10;public MyStack() {this.elem = new int [DEFAULT_CAPACITY];}//有效元素个数public int size(){return usedSize;}//压栈public void push(int val) {if (isFull()) {elem = Arrays.copyOf(elem, 2 * elem.length);}elem[usedSize] = val;usedSize++;}//判断栈是否满了private boolean isFull() {return usedSize == elem.length;}//判断栈是否为空public boolean empty() {return usedSize == 0;}//出栈public int pop() {if (empty()) {throw new EmptyException();}
//        usedSize--;  //这一步那个栈顶元素就已经没有了，就像5变成了4，
//        return elem[usedSize]; //这样写其实不好,因为这个元素我们认为没有了，但是你还是要去访问int oldVal = elem[usedSize -1];usedSize--;return oldVal;   //这样好一点，我们把这个元素保存起来了，然后返回}//返回栈顶元素public int peek() {if (empty()) {throw new EmptyException();}return elem[usedSize - 1];}}

1.3：模拟栈测试

java">import java.util.LinkedList;public class Test {public static void main(String[] args) {MyStack myStack = new MyStack();myStack.push(10);myStack.push(20);myStack.push(66);myStack.push(66);myStack.push(88);myStack.push(99);System.out.println(myStack.size());System.out.println("=======================");System.out.println(myStack.pop());//99System.out.println(myStack.pop());//88System.out.println(myStack.empty());//falseSystem.out.println(myStack.size());//4System.out.println(myStack.peek());//66System.out.println(myStack.size());//4myStack.pop();myStack.pop();myStack.pop();myStack.pop();//myStack.pop();//抛出异常System.out.println("===================");LinkedList<Integer> stack = new LinkedList<>();stack.push(100);stack.push(100);stack.push(222);stack.push(444);stack.push(666);System.out.println(stack.peek());//666System.out.println(stack);}
}

java">    // 递归方式public static void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}}// 循环方式public static void printList(Node head){if(null == head){return;}Stack<Node> s = new Stack<>();
// 将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val + " ");}}

java">class Solution {public boolean isValid(String s) {Stack<Character>stack = new Stack<>();for(int i = 0; i < s.length(); i++){char ch = s.charAt(i);if(ch =='(' || ch =='[' || ch =='{'){//左括号stack.push(ch);}else {if (stack.empty()) { //判断是否为空，防止栈为空，出现空指针异常return false;}char top = stack.peek();if ((ch == ')' && top == '(') || (ch == ']' && top == '[') || (ch == '}' && top == '{')) {//右括号 stack.pop();continue;//跳过后面的return} return false;}}if(stack.empty()){return true;}return false;}
}

1.5.3：逆波兰表达式求值

逆波兰表达式求值

java">class Solution {public int evalRPN(String[] tokens) {Stack <Integer> stack = new Stack<>();for(String s:tokens){if(isOpreations(s)){int ret1 = stack.pop();int ret2 = stack.pop();switch(s){case "+":{stack.push(ret1 + ret2);break;}case "-":{stack.push(ret2 - ret1);break;}case "*":{stack.push(ret1 * ret2);break;}case "/":{stack.push(ret2 / ret1);break;}}}else{stack.push(Integer.parseInt(s));}}return stack.pop();}public boolean isOpreations(String s){if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){return true;}return false;}
}

1.5.4：栈的压入、弹出序列

java">public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushA, int[] popB) {// write code hereStack<Integer> stack = new Stack<>();int j = 0;  //记得放外边for(int x : pushA){stack.push(x);while(!stack.empty() && j<popB.length && stack.peek() == popB[j] ){//这里一定要判断stack是否为空，你想想，我一直搁着pop，一会就pop完了// 最后i到5，j到1，你就算是判断你也stack.peek();就越界了// 其实 J < pop.length就够了，（!stack.empty()）相加就加stack.pop();j++;}}/*if(stack.empty()){return true;}return false;*/return stack.empty();}
}

1.5.5：最小栈

 最小栈

java">import java.util.*;
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);//不管怎么样你一定要push进去if(minStack.empty()){       // 最小栈里面的是空的，这个时候你放进去一个任意数，这个任意数就是最小值minStack.push(val);}if(val <= minStack.peek()){//等于也要加上minStack.push(val);}}public void pop() {if(! stack.empty()){ //根本不用担心minStack会空指针异常，最后Stack和MinStack都会剩下一个元素int ret = stack.pop();//不管怎么样你一定要pop出去，除非空指针了if( ret == minStack.peek()){//等于也要加上minStack.pop();}}}public int top() {if(stack.empty()){return -1;}return stack.peek();}public int getMin() {if(minStack.empty()){return -1;}return minStack.peek();}
}

1.6：栈、虚拟机栈、栈帧有什么区别呢？

栈（Stack）

1. 定义：栈是一种基本的线性数据结构，它按照后进先出（LIFO, Last In First Out）的原则存储和操作数据。

2. 特点：

   • 栈中的数据项只能在一端（栈顶）进行插入和删除操作。
   • 栈底固定，栈顶可以动态变化。
   • 栈具有有限的容量，当容量达到上限时，称为栈溢出。
   • 栈的操作简单高效，时间复杂度为O(1)。

3. 应用场景：栈在多种场景下都有应用，如撤销操作、浏览器的前进后退功能、逆序输出、中缀表达式转换为后缀表达式等。

虚拟机栈（Java Virtual Machine Stack）包含着栈帧

1. 定义：虚拟机栈是Java虚拟机中用于方法调用和执行的一块特殊作用的内存空间。

2. 特点：

   • 每个线程在创建时都会创建一个虚拟机栈，该栈是线程私有的。
   • 虚拟机栈中保存着一个个的栈帧（Stack Frame），每个栈帧对应着一次Java方法调用。
   • 虚拟机栈的访问速度仅次于程序计数器，是快速有效的分配存储方式。

java">public class MyQueue {//其实这就是双链表的不同实现方法的名字而已，没啥区别（就是里面的方法不一样罢了）//队列和栈里的方法极其相似class ListNode{int value;//队列里面的有效值ListNode pre;//前一个节点的地址ListNode next;public ListNode(int value) {this.value = value;}}ListNode front;  //头结点的地址ListNode rear;  //尾巴节点int usedSize;//尾巴进去public void offer(int data){ListNode node = new ListNode(data);if(rear == null){rear = node;front = node;}else{rear.next = node;node.pre = rear;rear = node;}usedSize++;}//头出public int poll(){if(front == null){throw new NullPointerException();}int ret = front.value;if(front == rear){front = null;rear = null;}else{front = front.next;front.pre = null;}usedSize--;return ret; //这里一定不能写front.value！！！}public int size(){return usedSize;}public int peek(){if(front == null){throw new NullPointerException();}int ret = front.value;return ret;}public boolean isEmpty(){return usedSize == 0;}
}

2.3.模拟队列测试：

java">public class Test {public static void main(String[] args) {MyQueue myQueue = new MyQueue();myQueue.offer(10);myQueue.offer(20);myQueue.offer(66);myQueue.offer(77);myQueue.offer(99);System.out.println(myQueue.peek());//10System.out.println(myQueue.poll());//10System.out.println(myQueue.peek());//20System.out.println("=================");System.out.println(myQueue.size());//4myQueue.poll();myQueue.poll();System.out.println(myQueue.isEmpty());//是否为空,falsemyQueue.poll();myQueue.poll();System.out.println(myQueue.isEmpty());//是否为空,true//myQueue.poll();//空指针异常
}
}

2.4.队列的方法的一些区别

队列的offer和add的区别在哪里？

1.返回值：
offer(E e): 返回boolean类型。如果元素成功被添加到队列中，则返回true；如果队列已满（对于某些有界队列），则返回false。
add(E e): 也返回boolean类型。如果元素成功被添加到队列中，则返回true。但如果队列已满（对于某些有界队列），则会抛出IllegalStateException异常。（）
异常处理：
offer(E e): 不会抛出异常，总是返回true或false来表示操作是否成功。
add(E e): 在队列已满的情况下会抛出IllegalStateException，不返回false。
使用场景：
offer(E e): 更常用于需要检查队列是否已满而不想处理异常的情况。
add(E e): 更适合在需要确保元素一定被添加且队列容量足够时使用，因为它在无法添加元素时会通过异常来通知调用者。

IllegalStateException：

 IllegalStateException：是 Java 中的一个运行时异常（RuntimeException 的子类），它表明某个应用程序对象当前处于不适当的状态，因此无法执行请求的操作。这个异常通常不是由系统抛出，而是由程序员在代码中显式地抛出。（譬如如果尝试在一个已经关闭的文件流上写入数据，可能会抛出 IllegalStateException。）

poll和remove方法的区别？

• poll（）方法：队列为空时不会抛出异常，总是返回null或移除的元素。
• remove()方法：在队列为空时会抛出NoSuchElementException异常。

peek()和element（）方法的区别?

• peek（）方法：队列为空时不会抛出异常，总是返回null或队顶的元素。
• element（）方法：在队列为空时会抛出NoSuchElementException异常。

NoSuchElementException异常：

这个异常通常在尝试访问某个不存在的元素时抛出，尤其是在使用迭代器（Iterator）、列表迭代器（ListIterator）、队列（Queue）等集合框架中的组件时。

Stack：可以本身就用new一个Stack这个结构，也可以用LinkedList（链式队列），ArrayDueue（双端队列）(底层是数组）。

Queue和Dueue：底层就是LinkedList，所以用LinkedList实现这两种结构都没问题，当然new一个ArrayDueue也完全没问题。

底层是数组的：可以是顺序表，栈，队列，双端队列

底层是链表的：单双链表，栈，队列，双端队列

2.4 循环队列（上面说的用数组实现）

设计循环队列

java">class MyCircularQueue {int front;int rear;int[] elem;public MyCircularQueue(int k) {elem = new int[k + 1];}//向循环队列插入一个元素。如果成功插入则返回真。public boolean enQueue(int value) {if(isFull()){  //插入元素，应该是rear出发，return false;}elem[rear] = value;rear = (rear +1) % elem.length;return true;}//从循环队列中删除一个元素。如果成功删除则返回真。public boolean deQueue() { if(isEmpty()){ return false;}front =  (front + 1) % elem.length;//我这个是为了防止本来在 7位置，你突然++ 就变成8了，但是我这个数组根本没有这个下标return true;}//返回队首元素public int Front() {if(isEmpty()){return -1;}return elem[front];  //这个front下标一直都有元素}//返回队尾元素public int Rear() {  //rear下标一直没有元素，返回上一个下标的元素。if(isEmpty()){return -1;}if(rear == 0){int cur = 0;cur = elem.length -1;return elem[cur];}return elem[rear -1];}//判断是否为空public boolean isEmpty() {return front == rear;}//判断是否满了public boolean isFull() {return (rear + 1) % elem.length == front;   // 这里可不是rear + 1 == front，一定要%elem.length}
}

三. 双端队列 (Deque)

java">        Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现(直接当成栈就完全没问题//毕竟你两边都能进出嘛stack.push(1);Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现Deque<Integer> stack1 = new LinkedList<>();//栈来玩玩啦，队列也可以//这里一定要注意，这里并不是栈本身的结构，只是这个名字(这里你可别new 一个Stack了，没实现这个接口）