怎么建立网站卖东西,荆州网站建设流程,做网赌网站,深圳品牌网站建设服务费用目录
一、栈
#xff08;1#xff09;用数组实现
#xff08;2#xff09;用单链表实现
#xff08;3#xff09;用标注尾结点的单链表实现
#xff08;4#xff09;用双向链表实现
2、栈的实际应用
#xff08;1#xff09;改变元素的序列
#xff08;21用数组实现
2用单链表实现
3用标注尾结点的单链表实现
4用双向链表实现
2、栈的实际应用
1改变元素的序列
2将递归转化为循环逆序打印链表
3括号匹配
4逆波兰表达式求值
5出栈入栈次序匹配
6最小栈
二、队列
1、队列的使用 2、队列的模拟实现
3、循环队列
4、双端队列Deque 三、面试题
1、用栈实现队列
2、用队列实现栈 一、栈 栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作
进行数据插入和删除操作的一端称为栈顶另一端称为栈底
栈中的数据元素遵守后进先出的原则
压栈/进栈/入栈栈的插入操作出栈栈的删除操作 方法 功能Stack()构造一个空的栈E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空 1、栈的模拟实现
1用数组实现
2用单链表实现 若使用尾插法则入栈时间复杂度为O(n)出栈时间复杂度为O(n)若使用头插法则入栈复杂度为O(1)出栈复杂度为O(1)
3用标注尾结点的单链表实现 尾插法入栈O(1)出栈O(n)因为删除尾结点依旧要遍历到前一个结点改变其next值头插法入栈O(1)出栈O(1)
4用双向链表实现
无论尾插还是头插时间复杂度都为O(1) LinkedListInteger stacknew LinkedList();stack.push(1);// addFirst(e);stack.push(2);stack.push(3);System.out.println(stack.peek());//拿到头结点3
2、栈的实际应用
1改变元素的序列
2将递归转化为循环逆序打印链表 //1、递归方式void reverseprintList1(Node head){if(head!null){printList(head.next);System.out.print(head.val );}}
//2、循环方式void reverseprintList2(Node head){if(headnull){return;}StackNode s new Stack();// 将链表中的结点保存在栈中Node cur head;while(cur!null){s.push(cur);cur cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val );}}
3括号匹配 给定一个只包含 ( 、 ) 、 { 、 } 、 [ 、 ] 的字符串s判断括号是否匹配。匹配条件左括号必须与相同类型的右括号闭合不可交错排列 匹配示例(){}[]、({}[])、([{}])、()[{}] public boolean isValid(String s) {StackCharacter stacknew StackCharacter();for (int i 0; i s.length(); i) {char cs.charAt(i);if (c( || c[ || c{){//c为左括号就添加进来等着对称匹配stack.push(c);}else {//c为右括号//此时栈中可能有左括号等着匹配也可能为空无法匹配if (stack.empty()){return false;}//不为空则栈中存放的是左括号那就判断c与栈顶元素是否匹配因为两括号必须要对称匹配char topstack.peek();if (c) top( || c] top[ || c} top{){//对称匹配了则弹出此左括号stack.pop();}else {//遇到一个右括号无法与栈顶左括号对称匹配则无法匹配return false;}}}//如果s遍历完发现栈中不为空即栈中仍有残存左括号未进行匹配不匹配if (!stack.empty()){return false;}//否则匹配return true;}
4逆波兰表达式求值
中缀表达式转化为后缀表达式技巧 public int evalRPN(String[] tokens) {StackInteger stacknew Stack();for (String s : tokens) {if (!isOperation(s)) {//压入数字字符stack.push(Integer.parseInt(s));}else {//运算符则弹出栈顶2个元素进行操作先弹出的放运算符右边int num2stack.pop();int num1stack.pop();switch (s){case :stack.push(num1num2);break;case -:stack.push(num1-num2);break;case *:stack.push(num1*num2);break;case /:stack.push(num1/num2);break;}}}return stack.pop();}private boolean isOperation(String s) {if (s.equals() || s.equals(-) || s.equals(*) || s.equals(/)){//是运算符return true;}return false;}
5出栈入栈次序匹配 public boolean IsPopOrder (int[] pushV, int[] popV) {StackInteger stacknew Stack();int j0;for (int i 0; i pushV.length; i) {stack.push(pushV[i]);while (!stack.empty() jpopV.length stack.peek()popV[j]){stack.pop();j;}}return stack.empty();}
6最小栈
class MinStack {private StackInteger stack;private StackInteger minStack;//存储阶段性最小值private int minValue;public MinStack() {stacknew Stack();minStacknew Stack();}public void push(int val) {stack.push(val);if (minStack.empty()){minStack.push(val);}else {if (valminStack.peek()){minStack.push(val);}}}public void pop() {if (!stack.empty()){int retstack.pop();if (minStack.peek()ret){minStack.pop();}}}public int top() {//获取stack栈顶元素if (stack.empty()){return -1;}return stack.peek();}public int getMin() {//获取minStack栈顶元素if (minStack.empty()){return -1;}return minStack.peek();}
} 栈一种数据结构。是一种特殊的线性表只允许在栈顶进行插入和删除操作栈顶的数据元素遵守后进先出的原则虚拟机栈JVM内存管理的一部分用于管理函数调用的内存和回收。属于线程私有确保每个线程的内存隔离和安全。栈帧函数调用过程中的内存管理单元。包含局部变量表、操作栈等信息。每个方法在运行时JVM都会创建一个栈帧并将其压入虚拟机栈中当方法调用结束时对应的栈帧会从虚拟机栈中出栈确保函数调用的顺利进行和结束后的资源释放 二、队列 队列只允许在一端进行插入和删除数据操作在另一端进行删除数据操作的特殊线性表
进行插入操作的一端称为队尾进行删除操作的一端称为队头队列遵守先进先出的原则
1、队列的使用
在Java中Queue是个接口底层是通过链表实现的 方法 功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中有效元素个数boolean isEmpty()检测队列是否为空
Queue是个接口在实例化时必须实例化LInkedList的对象因为LinkedList实现了Queue接口 QueueInteger q new LinkedList();// 从队尾入队列q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);System.out.println(q.size());//5System.out.println(q.peek()); // 获取队头元素 1q.poll();//弹出队头元素 1System.out.println(q.poll()); // 从队头出队列并将删除的元素返回 2if(q.isEmpty()){System.out.println(队列空);}else{System.out.println(q.size());//3} 2、队列的模拟实现
队列中既然可以存储元素那底层肯定要有能够保存元素的空间。通过前面线性表的学习了解到常见的空间类型有2种顺序结构和链式结构。那是用哪种结构实现比较好呢
1双向链表实现
2数组实现 如果rearelem.length-1之后发现数组前面还有位置还可以往前面插入元素就好了这时候也就是我们的循环队列
3、循环队列
数组设计循环队列 4、双端队列Deque
双端队列是指允许两端都可以进行入队和出队操作的队列 Deque是一个接口使用时必须创建LinkedList对象 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口
DequeIntegerstack newArrayDeque();//双端队列的线性实现
DequeIntegerqueuenewLinkedList();//双端队列的链式实现 三、面试题
1、用栈实现队列 class MyQueue {StackInteger inStack;StackInteger outStack;public MyQueue() {inStacknew Stack();outStacknew Stack();}public void push(int x) {inStack.push(x);}public int pop() {if (empty()){return -1;//队列此时为空}if (outStack.empty()){while (!inStack.empty()){outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {if (empty()){return -1;}if (outStack.empty()){while (!inStack.empty()){outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {return inStack.empty() outStack.empty();}
}
2、用队列实现栈 class MyStack {private QueueInteger qu1;private QueueInteger qu2;public MyStack() {qu1new LinkedList();qu2new LinkedList();}//入栈入到不为空的队列都为空则入到qu1即可public void push(int x) {if (!qu1.isEmpty()){qu1.offer(x);}else if (!qu2.isEmpty()){qu2.offer(x);}else {qu1.offer(x);}}//出栈出不为空的队列size-1个。最后一个元素就是要出栈的元素public int pop() {if (empty()){return -1;//栈为空}if (!qu1.isEmpty()){int sizequ1.size();for (int i 0; i size - 1; i) {qu2.offer(qu1.poll());}return qu1.poll();}else {int sizequ2.size();for (int i 0; i size - 1; i) {qu1.offer(qu2.poll());}return qu2.poll();}}public int top() {int tmp-1;if (empty()){return -1;//栈为空}if (!qu1.isEmpty()){int sizequ1.size();for (int i 0; i size; i) {tmpqu1.poll();qu2.offer(tmp);//出的最后一个元素存在tmp即为栈顶元素}return tmp;}else {int sizequ2.size();for (int i 0; i size; i) {tmpqu2.poll();qu1.offer(tmp);}return tmp;}}public boolean empty() {return qu2.isEmpty() qu1.isEmpty();}
}
