建设外贸型网站流程,七宝网站建设,网络管理培训课程,乐都区公司网站建设文章目录 一、栈1.1 什么是栈1.2 栈的使用#xff08;1#xff09;底层代码#xff08;2#xff09;方法#xff08;3#xff09;栈的应用 二、队列2.1 什么是队列2.2 队列的使用#xff08;1#xff09;底层代码的实现#xff08;2#xff09;队列的使用 2.3 双端队… 文章目录 一、栈1.1 什么是栈1.2 栈的使用1底层代码2方法3栈的应用 二、队列2.1 什么是队列2.2 队列的使用1底层代码的实现2队列的使用 2.3 双端队列2.4 练习 一、栈
1.1 什么是栈
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。 栈中的数据元素遵守后进先出LIFOLast In First Out的原则 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出栈栈的删除操作叫做出栈。出数据在栈顶。JVM虚拟机栈 VS 栈 JVM虚拟机栈系统的一块内存栈数据结构 1.2 栈的使用
1底层代码
import java.util.Arrays;public class MyStack {private int[] elem; //stack的底层是数组private int usedSize;public MyStack() {this.elem new int[5];}//压栈public void push(int val) {if(isFull()) { //判断里面的空间是否为满的情况elem Arrays.copyOf(elem,2*elem.length);}elem[usedSize] val;usedSize;}public boolean isFull() {return usedSize elem.length;}//出栈public int pop() {//1、判断栈不为空if(empty()) {//抛出异常throw new StackEmptyException(栈为空);}//2、开始删除return elem[--usedSize]; //elem[useSize]的数字没有被删掉后续如果有push的话会把值该赋给掉}//获取栈顶元素public int peek() {//1、判断栈不为空if(empty()) {//抛出异常throw new StackEmptyException(栈为空);}//2、开始删除return elem[usedSize-1];}public boolean empty() {return usedSize 0;}
}2方法
方法功能Stack()构造一个空的栈E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空
3栈的应用
改变元素的序列 进栈过程中可以出栈 和 依次入栈然后再依次出栈 对元素出栈的顺序的改变 将递归转化为循环
//递归方式
public void show(ListNode head) {if(head null) {return;}if(head.next null) {System.out.println(head.val);return;}show3(head.next);System.out.println(head.val);
}//循环方式
public void show2() {StackListNode stack new Stack();ListNode cur head;while (cur ! null) {stack.push(cur);cur cur.next;}//依次出栈while (!stack.empty()) {ListNode tmp stack.pop();System.out.println(tmp.val);}
}逆波兰表达式求值
class Solution {public int evalRPN(String[] tokens) {DequeInteger stack new LinkedListInteger();int n tokens.length;for (int i 0; i n; i) {String token tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 stack.pop();int num1 stack.pop();switch (token) {case :stack.push(num1 num2);break;case -:stack.push(num1 - num2);break;case *:stack.push(num1 * num2);break;case /:stack.push(num1 / num2);break;default:}}}return stack.pop();}public boolean isNumber(String token) {return !(.equals(token) || -.equals(token) || *.equals(token) || /.equals(token));}
}有效的括号
class Solution {public boolean isValid(String s) {StackCharacter 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;}else {char tmp stack.peek();if (ch ) tmp ( || ch } tmp { || ch ] tmp [) {stack.pop();}else {return false;}}}}if (!stack.empty()) {return false;}return true;}
}栈的压入、弹出序列
import java.util.Stack;public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {StackInteger stack new Stack();int j 0;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 stack.empty();}
}最小栈
class MinStack {
private StackInteger stack ;private StackInteger 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();}}栈、虚拟机栈、栈帧有什么区别呢 栈是数据结构 虚拟机栈是内存 栈帧是调用方法是在虚拟机栈开辟的一个内存 二、队列
2.1 什么是队列 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(FirstIn First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头Head/Front 抽象场景食堂排队买饭 2.2 队列的使用
1底层代码的实现 在Java中Queue是个接口底层是通过链表实现的 队列可以通过数组和链表实现 如果是双向链表那么入队和出队均可以达到O(1)不管从哪边进如果是单链表并且记录了最后一个节点的位置的情况下我们可以采用从尾入队从头出队的方式都是O(1)。如果是从头进从尾出那么出队的复杂度为O(n)
2队列的使用
❤️创建 Queue是个接口在实例化时必须实例化LinkedList的对象因为LinkedList实现了Queue接口。
QueueInteger q new LinkedList();❤️方法
方法功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中有效元素个数boolean isEmpty()检测队列是否为空
❤️队列的模拟实现
顺序结构 双向链表
public class Queue {// 双向链表节点public static class ListNode{ListNode next;ListNode prev;int value;ListNode(int value){this.value value;}}ListNode first; // 队头ListNode last; // 队尾int size 0;// 入队列---向双向链表位置插入新节点public void offer(int e){ListNode newNode new ListNode(e);if(first null){first newNode;// last newNode;}else{last.next newNode;newNode.prev last;// last newNode;}last newNode;size;}// 出队列---将双向链表第一个节点删除掉public int poll(){// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除int value 0;if(first null){return -1;}else if(first last){last null;first null;}else{value first.value;first first.next;first.prev.next null;first.prev null;}--size;return value;}// 获取队头元素---获取链表中第一个节点的值域public int peek(){if(first null){return -1;}return first.value;}public int size() {return size;}public boolean isEmpty(){return first null;}
}单向链表
public class MyQueue {static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val val;}}public ListNode head;public ListNode last;private int usedSize;public void offer(int val) {ListNode node new ListNode(val);if(head null) {head node;last node;}else {last.next node;last last.next;}usedSize;}public int getUsedSize() {return usedSize;}public int poll() {if(head null) {return -1;}int val -1;if(head.next null) {val head.val;head null;last null;return val;}val head.val;head head.next;usedSize--;return val;}public int peek() {if(head null) {return -1;}return head.val;}}循环结构 环形队列通常使用数组实现 class MyCircularQueue {private int[] elem;private int front;//队头下标private int rear;//队尾下标public MyCircularQueue(int k) {this.elem new int[k1];}//入队public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] value;rear (rear1) % elem.length;return true;}//出队public boolean deQueue() {if(isEmpty()) {return false;}front (front1) % 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 (rear1) % elem.length front;}
}解析
数组下标循环 下标最后再往后(rear 1) % elem.length; 下标最前再往前(front 1) % elem.length;如何区分空和满 满 通过添加 useSize 属性记录,当useSIze len 的时候为满 保留一个位置用这个位置来表示满 使用标记 空 front rear 时为空
2.3 双端队列
双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队也可以从队尾出队和入队 Deque是一个接口使用时必须创建相关的对象。
DequeInteger stack new ArrayDeque(); 双端队列的线性实现底层是数组
DequeInteger queue new LinkedList(); 双端队列的链式实现底层是链表2.4 练习
一、用队列实现栈
import java.util.LinkedList;
import java.util.Queue;class MyStack {private QueueInteger qu1;private QueueInteger 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 (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();qu1.offer(x);}return qu2.poll();//最后一个数据返回}return -1;}//peek方法public int top() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int currentSize qu1.size();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();qu1.offer(x);}return x;//最后一个数据返回}return -1;}public boolean empty() {return qu1.isEmpty() qu2.isEmpty();}
}二、用栈实现队列
class MyQueue {private StackInteger s1;private StackInteger s2;public MyQueue() {s1 new Stack();s2 new Stack();}public void push(int x) {s1.push(x);}public int pop() {if(!s2.empty()) {return s2.pop();}else {while(!s1.empty()) {int val s1.pop();s2.push(val);}return s2.pop();}}public int peek() {if(!s2.empty()) {return s2.peek();}else {while(!s1.empty()) {int val s1.pop();s2.push(val);}return s2.peek();}}public boolean empty() {return s1.empty() s2.empty();}
}
