栈
一. 栈的概念
栈(Stack）：是一种特殊的线性表，它只能在表的一端（称为栈顶）进行插入和删除操作。
可以将栈理解成一摞盘子，只能从上面进行取走，还放在最上面
栈顶：进行插入和删除的位置
栈底： 不能进行插入和删除
栈顶的元素会发生改变，但是栈底的元素相对来说是固定的
特点：
后进先出（LIFO）：先进入栈的元素，会最后一个取出
操作的局部性：栈的操作只涉及栈顶元素，不会影响到栈中的其他元素。
二. 栈的基本操作
1. 栈内方法的实现
（1）增加
public void push(int val){if(isFull()){//扩容elem = Arrays.copyOf(elem,elem.length+1);}elem[usedSize++] = val;}主要操作：
- 先判满，如果满则进行扩容，然后赋值，不满则直接进行赋值
其中usedSize表示栈中元素的个数
（2）删除
public Object pop(){Object o = null;if(!isempty()){
// usedSize表示下一个该放的位置o = elem[usedSize-1];usedSize--;}else {System.out.println("栈为空");return null;}return o;}主要操作：
- 先进行判空，如果栈为空，则返回null,不为空则进行删除操作，删除操作：usedSize--，
（3）获取
public Object peak(){Object o = null;if(!isempty()){o = elem[usedSize-1];}else {System.out.println("栈为空");return null;}return o;}主要操作：
判空，为空则返回null，否则返回栈顶元素
（4）判空
public Boolean isempty(){if(usedSize!=0){return false;}return true;}元素为0，则表示为空
（5）判满
Boolean isFull(){if(usedSize>=elem.length){return true;}return false;}如果大于栈的容量，则表示栈满
2. 栈内方法的使用
push（）：数据入栈
pop（）：数据出栈
peak（）：查看栈顶元素
empty（）：判断栈中是否还有元素
public class Text_1 {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();//存放数据stack.push(1);stack.push(2);//删除数据stack.pop();//删除最后进来的一个元素//获取stack.peek();//获取最后一个元素，不删除//判断栈是否为空stack.empty();}
}通过创建Stack对象，使用Stack内的方法操作
三. 实现方式
1. 基于数组实现
优点：
- 访问速度快：数组支持随机访问，时间复杂度为O(1)。
- 空间利用率高：不需要额外的指针存储空间。
缺点：
- 大小固定：数组的大小在创建时需要预先定义，无法动态扩展。
- 可能浪费空间：如果栈的使用量远小于数组大小，会浪费存储空间。
- 可能栈溢出：如果栈的使用量超过数组大小，会发生栈溢出。
2. 基于链表实现
优点：
- 动态扩展：链表的大小可以动态变化，不需要预先定义。
- 不会栈溢出：只要内存足够，栈可以无限扩展。
缺点：
- 访问速度慢：链表不支持随机访问，每次操作都需要遍历。
- 额外空间开销：每个节点需要额外存储一个指针。
单向列表：
在单向链表的插入中，分为两种，头插法和尾插法
头插法的时间复杂度为O（1）---- 头插法只需要修改头节点的指针和新节点的指针
尾插法的时间复杂度为O（n）---- 每次插入操作都需要遍历整个链表以找到最后一个节点。
双向链表：
双向链表的头插法和尾插法，时间复杂度都为O（1）
注意：我们一般使用的基于链表的栈都为双向链表
总结：
| 不同点 | 基于数组的栈 | 基于链表的栈 |
| 空间大小 | 预先定义大小，可能浪费空间或溢出 | 动态扩展，不会溢出，但需要额外指针空间 |
| 访问速度 | O(1)，访问速度快 | O(1)，访问速度快，但链表操作稍复杂 |
| 灵活性 | 固定大小，不适合动态变化 | 动态大小，适合动态变化 |
四. 栈的应用
（1）逆波兰数的运算
图分析
主要步骤为：
- 后缀式中的元素依次入栈
- 如果遇到运算符，则取出栈中的两个元素，取出的第一个元素，放在第二位，取出的第二个元素放在第一位，进行运算，
- 运算后得到的结果放入栈内。
代码实现
public class Text_3 {public int evalRPN(String[] tokens){Stack<Integer> stack = new Stack<>();int num = 0;for(String s:tokens){//检查是不是运算符if(!isOperation(s)){//字符串类型变为整型stack.push(Integer.parseInt(s));}else{//取出栈里面的数据int x2 = stack.pop();int x1 = stack.pop();switch (s){case "+":num = x1+x2;break;case "-":num = x1-x2;break;case "*":num = x1*x2;break;case "/":num = x1/x2;break;}//将运算后的结果返回栈内stack.push(num);}}//结果为栈内第一个元素return stack.peek();}public boolean isOperation(String s){if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){return true;}return false;}
}（2）用栈得到最小数
最小数不是固定的，会随着添加的数据进行改变
图分析：
主要步骤：
入栈操作：
- 每次执行入栈操作，不管stack是否为空都要进行入栈操作，
- 在入栈的时候，进行判断：如果stack为空（stack栈为空，则minstack栈一定为空），则minstack和stack都要进行入栈操作
- minstack不为空，需要对入栈的元素进行判断，如果小于minstack栈顶元素，则入栈
出栈操作：
- 每次执行出栈操作的时候，stack栈都要执行出栈操作
- 在每次stack出栈的时候，要进行判断，如果出栈的元素和minstack的栈顶元素相同，则minstack也要进行出栈操作
代码实现：
class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {if(minStack.empty()){//为空，都要入栈minStack.push(val);}else {//不为空进行判断if(val<=minStack.peek()){minStack.push(val);}}stack.push(val);}public void pop() {if(!stack.empty()){int x = stack.pop();if(x == 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();}
}队列
一. 队列的概念
队列是一种线性表，只允许在表的一端（队尾，rear）进行插入操作，在另一端（队头，front）进行删除操作。
类似于现实生活中排队，新来的人总是排在队尾，而排在队头的人会先接受服务然后离开队伍。
队头：允许删除的一端
队尾：允许插入的一端。
特点：
先进先出（FIFO）：最先进入队列的元素会最先被移除，一种先来先服务的原则。
二. 队列的基本操作
1.队列内方法的实现
基于链表的队列实现
（1）入队
//插入操作 采用头插法public void offer(int val){ListNode cur = new ListNode(val);if(front ==null){front = rear = cur;}else {cur.next= front;cur.prev = null;front.prev = cur;front = cur;}usedSize++;}
主要步骤：采用头插法
-
如果队列为空，将头指针（front）和尾指针（rear）都指向新节点。
-
否则，使用头插法将新节点插入到链表头部。
（2）出队
public int poll(){//为空if(front ==null){return -1;}int ret = rear.val;//只有一个if(front ==rear){front = null;rear = null;usedSize--;return ret;}rear = rear.prev;rear.next = null;usedSize--;return ret;}
主要步骤：
-
如果队列中只有一个元素，将头指针和尾指针都置为null；
-
否则，将rear指针前移一位，并将新的尾指针的next 置为null。
（3）获取
public int peak(){if(front ==null){return -1;}return rear.val;}（4）判空
public boolean isEmpty(){if(usedSize ==0){return true;}return false;}如果队列内元素为空，则返回true
2. 队列内方法的使用
入队操作：add( )和offer( )
出队操作：remove( )和poll( )
获取队头元素：peek( )和element（）
获取队列元素个数：size( )
public class Text_1 {public static void main(String[] args) {//底层通过链表实现Queue<Integer> queue = new LinkedList<Integer>() ;//入队queue.add(2);queue.offer(1);System.out.println(queue);//出队queue.remove();System.out.println(queue);
// queue.poll();//获取队列第一个元素System.out.println(queue.peek());System.out.println(queue.element());//获取队列元素System.out.println(queue.size());}
}
通过对Queue接口实例化，这意味着LinkedList类为Queue接口中定义的所有方法都提供了具体的实现。
三. 实现方式
1. 基于数组实现
数组实现的队列使用一个固定大小的数组来存储队列中的元素，通过两个指针（队头指针和队尾指针）来管理队列的插入和删除操作。
数组实现的队列需要解决“队列溢出”和“队列空间浪费”的问题，所以一般采用循环队列的方式
循环队列
在循环队列中如何区分空和满？
- 通过添加 size 属性记录
- 保留一个位置
其中rear表示插入的位置，front表示删除的位置
空队列：
当rear==front的时候处于空队列
满队列：
当（rear+1）%长度 = front
注意：
在申请空间的时候，一定要在申请大小的基础上加1，因为一个空间不存放数据，用于判断队列的空或满
（1）判满
public boolean isFull(){if((rear+1)% elem.length ==front){return true;}return false;}（2）判空
public boolean isEmpty(){if(rear == front ){return true;}return false;}（3）出队
public boolean deQueue(){if(isEmpty()){return false;}elem[front]= 0;front = (front+1)%elem.length;return true;}主要操作：
- 判空，如果为空则表明无法进行出队操作
- 不为空，则将front下标的元素置为0，下标加1（不能直接加1操作，要取模）
（4）入队
public boolean enQueue(int val){if(isFull()){return false;}else {elem[rear] = val;rear = (rear+1)%elem.length;}return true;}主要操作：
- 判满，如果满了则不能进行入队操作
- 不满，则将元素赋值在rear下标的位置，下标加1（不能直接加1操作，要取模）
（5）获取
返回队首元素
public int Front(){if(isEmpty()){return -1;}return elem[front];}返回队尾元素
public int Rear(){if(isEmpty()){return -1;}int index = 0;if(rear ==0){index = elem.length-1;}else {index = rear-1;}return elem[index];}注意：不为空，才能获取
优点：
- 空间利用率高，通过循环队列设计避免了空间浪费。
- 访问速度快，所有操作的时间复杂度均为O(1)。
缺点：
- 队列大小固定，需要提前定义容量。
- 如果队列容量不足，可能会导致队列溢出。
2. 基于链表的队列实现
具体的实现过程上面已经进行了说明
优点：
- 动态扩展，不会出现队列溢出的问题。
- 所有操作的时间复杂度均为O(1)。
缺点：
- 占用空间较大，需要一些空间存放指针
四. 队列的应用
（1）
主要操作：
- 将元素依次放入stack1，在将stack1中的元素依次放入stack2中，这时候会发现栈顶的元素和队列第一个元素相等
class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue() {this.stack1 = new Stack<>();this.stack2 = new Stack<>();}//增加操作public void push(int x) {stack1.push(x);}public int pop() {if(stack2.isEmpty()){while (!stack1.isEmpty()){int tmp = stack1.pop();stack2.push(tmp); }}return stack2.pop();}public int peek() {if(stack2.isEmpty()){while(!stack1.isEmpty()){int tmp = stack1.pop();stack2.push(tmp);}}return stack2.peek();}public boolean empty() {if(stack1.isEmpty()&& stack2.isEmpty()){return true;}return false;}
}（2）用队列实现栈
主要操作：
入队操作：
如果两个队列都为空，那么入队到第一个
如果一个空，一个不为空，那么元素入队到不为空的队列中
出队操作：
将元素依次入队到queue1中，在将 queue1中size（）-1的元素依次入队到queue2中，queue1中剩下的这个元素就是栈顶元素
代码实现：
class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {//如果为空，在que1加，否则那个有数据加到那个if(empty()){queue1.offer(x);}else {if(!queue1.isEmpty()){queue1.offer(x);}else {queue2.offer(x);}}}public int pop() {//删除操作，将最后一个元素前面的所有元素移到另一个队列中储存，
// 最后一个元素不移，删除最后一个元素if(empty()){return -1;}if(!queue1.isEmpty()){int size = queue1.size();while(size-1>0){int tmp = queue1.poll();queue2.offer(tmp);size--;}return queue1.poll();}else {int size = queue2.size();while(size-1>0){int tmp = queue2.poll();queue1.offer(tmp);size--;}return queue2.poll();}}public int top() {//获取操作，将所有的元素移过去，记住最后一个元素的值，并返回if(empty()){return -1;}int tmp= -1;if(!queue1.isEmpty()){int size = queue1.size();while(size>0){tmp = queue1.poll();queue2.offer(tmp);size--;}return tmp;}else {int size = queue2.size();while(size>0){tmp = queue2.poll();queue1.offer(tmp);size--;}return tmp;}}public boolean empty() {if(queue1.isEmpty()&&queue2.isEmpty()){return true;}return false;}
}