网站建设销售怎么样,网络规划设计师教程pdf,扬州市邗江区建设局网站,建筑工程承包合同书目录
一、栈
1、栈的定义 2、栈的模拟实现#xff08;顺序栈#xff09;
1、创建一个顺序结构的栈
2、实现压栈方法#xff08;push#xff09; 3、模拟实现pop方法#xff08;出栈#xff09;
4、模拟实现peek(查看)
5、测试上述方法
3、栈的应用场景
1、改变元…目录
一、栈
1、栈的定义 2、栈的模拟实现顺序栈
1、创建一个顺序结构的栈
2、实现压栈方法push 3、模拟实现pop方法出栈
4、模拟实现peek(查看)
5、测试上述方法
3、栈的应用场景
1、改变元素的序列 2、逆序打印链表
3、逆波兰表达式求值后缀表达式求值 4、括号匹配
5、出栈入栈次序匹配
6、最小栈
4、栈的链式存储结构
1、链栈优点 2、实现链栈的进栈和出栈
二、对列
1、概念 2、队列的基本方法
3、链式对列的模拟实现
1、单链表实现队列 2、使用双链表实现队列
3、单链表模拟实现队列
4、对列的顺序存储结构
1、循环队列
4、双端队列
1、定义
5、Java集合的使用
三、 栈和队列的练习
1、用队列实现栈 2、用栈实现队列 一、栈
1、栈的定义 栈一种特殊的线性表其只允许在固定的一段进行插入和删除元素操作。栈顶Top:线性表允许进行插入删除的那一端。栈底Bottom:固定的不允许进行插入和删除的另一端。空栈不含任何元素的空表。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。出战栈的删除操作叫做出栈出数据在栈顶。2、栈的模拟实现顺序栈
方法功能Stack()构造一个空的栈E pushE e将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()查看栈顶元素int size()获取栈中有效元素个数boolean empty()检测栈是否为空
1、创建一个顺序结构的栈
public class MyStack {public int[] elem;public int usedSize;public MyStack(){this.elem new int[10];}
}
2、实现压栈方法push //压栈public void push(int val){if(isFull()){//扩容elem Arrays.copyOf(elem,2*elem.length);}elem[usedSize] val;//后置,先赋值后运算}public boolean isFull(){//判断栈是否已满return usedSize elem.length;} 3、模拟实现pop方法出栈 //出栈public int pop(){if(isEmpty()){//栈为空报异常throw new EmptyException(栈是空的!);}
//写法一int val elem[usedSize-1];usedSize--;
//写法二// int val elem[--usedSize];//因为usedSize记录的是元素的个数先减1得到数组的最后一个元素的下标return val;//返回出栈元素}public boolean isEmpty(){return usedSize 0;} 4、模拟实现peek(查看)
因为只是查看栈顶元素所以usedSize不变。 public int peek(){if(isEmpty()){throw new EmptyException(栈是空的);}return elem[usedSize - 1];}
5、测试上述方法
public class Test {public static void main(String[] args) {MyStack stack new MyStack();stack.push(1);//进栈stack.push(7);stack.push(6);stack.push(8);Integer a stack.pop();//出栈System.out.println(a);Integer b stack.peek();//查看System.out.println(b);Integer b2 stack.peek();System.out.println(b2);System.out.println(stack.isEmpty());//查看栈是否为空} 3、栈的应用场景
1、改变元素的序列 1️⃣. 若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是C A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1 2️⃣.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈然后再依次出栈则元素出栈的顺序B。 A: 12345ABCDE B: EDCBA54321 CABCDE12345 D: 54321EDCBA 2、逆序打印链表
1、递归的方式逆序打印链表 在归的时候才会打印链表的值回归的时候从后往前这样就实现了逆序打印链表 public class MySingleLIst {class Node{public int val;//存储数据public Node next;//存储下一个节点的地址public Node(int val) {this.val val;}}public Node head;//递归打印链表public void display(Node pHead){if(pHead null){//pHead为空return;}if(pHead.next null){//pHead只有一个节点System.out.print(pHead.val );}//上述两个if可以做为递归的结束条件display(pHead.next);//自己调用自己递归}
}2、通过栈的方式逆序输出 public void display1() {//将链表当中的节点保存在栈中StackNode stack new Stack();//申请一个栈这个栈中放的是一个一个的节点Node cur head;
//在进行测试的时候通过链表的方式将值放入链表的节点当中while (cur ! null) {//cur遍历链表若链表不为空将cur所指的节点放入到栈中stack.push(cur);cur cur.next;//向后走}//遍历栈while (!stack.isEmpty()) {Node top stack.pop();System.out.println(top.val );}System.out.println();}3、逆波兰表达式求值后缀表达式求值 逆波兰表达式求值也叫后缀表达式求值将中缀表达式转为后缀表达式。 中缀表达式我们平时常写的表达式例如1((23)*4)-5 后缀表达式将上述的中缀表达式转为后缀表达式为1 2 3 4 * 5 - 中缀表达式转后缀表达式1((23)*4)-5 第一步添加括号 第二步挪动运算符号到相应的括号外 第三步去掉括号 后缀表达式求值的算法思想 从左至右扫描表达式遇到数字时将数字压入栈遇到运算符时弹出栈顶的两个数用运算符对他们做相应的计算此顶元素 — 运算符 —栈顶元素并将结果入栈重复上述过程直到表达式最右端最后运算得到的值即为表达式的结果。 举例1 2 3 4 * 5 -
扫描到的元素栈的状态栈底 -栈顶说明11数字入栈读取下一个元素21 2数字入栈读取下一个元素31 2 3数字入栈读取下一个元素1 5运算符弹出两个操作数进行计算235结果入栈41 5 4 数字入栈读取下一个元素*1 20运算符弹出两个操作数进行计算5*4 20结果入栈。21运算符弹出两个操作数进行计算12021结果入栈521 5 数字入栈读取下一个元素-16运算符弹出两个操作数21-5 16结果入栈结束16串已读完结果为栈中唯一的元素❗❗❗ 注意在将元素压入栈中之后读取下一个数据的时候遇到的是运算符弹出操作数的时候将栈顶元素放在运算符的右边次顶元素放在运算符的左边。 【代码示例】
public class Test { public int evalRPN(String[] tokens){StackInteger stack new Stack();for(String x:tokens){//循环遍历元素if(!isOperation(x)){//判断不是运算符stack.push(Integer.parseInt(x));//x在遍历的时候定义的String类型要放入栈中栈指定的类型是Integer需要将其转为整数}else{//若是运算符int num2 stack.pop();int num1 stack.pop();switch(x){//判断运算符是那个运算符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 x){if(x.equals() || x.equals(-) || x.equals(/) || x.equals(*)){return true;}return false;}
} 4、括号匹配
先来看一下不匹配的情况 【代码思路】 这个问题使用栈来解决规定将左括号放入栈中当遇到右括号的时候将栈中的栈顶元素弹出若两个括号匹配就进行下一组比较若不匹配程序结束【代码示例】
public class Test { public boolean isValid(String s){StackCharacter stack new Stack();for (int i 0; i s.length(); i) {char ch s.charAt(i);//若ch拿到左括号入栈若ch拿到右括号则继续向下走if(ch { || ch [ || ch (){//如果都是左括号入栈stack.push(ch);}else{//如果遇到右括号if(stack.empty()){//判断栈空还是不空若空则是右括号多return false;}
//通过将ch拿到的值和ch2拿到的值比较若拼配弹出不匹配结束。char ch2 stack.peek();//若不是空则通过查看操作来看一下if(ch2 ( ch ) || ch2 { ch }|| ch2 [ ch ] ){stack.pop();}else{return false;}}}if(!stack.empty()){//判断栈若不为空返回falsereturn false;}return true;//若为空返回true}
} 5、出栈入栈次序匹配
【题目描述】 输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列。 【解题思路】 给定两个整数序列第一个序列表示入栈第二个用来和入栈后的栈顶元素相比较若相等则出栈若不想等则结束代码。 【代码示例】
public class Test {public boolean isPopOrder(int [] pushA,int [] popA ){if(pushA null){return false;}if(popA null){return false;}StackInteger stack new Stack();int j 0;//通过遍历将pushA的值压入栈中压一个值和popA中一个值比较一次for (int i 0; i pushA.length; i) {stack.push(pushA[i]);while(j popA.length !stack.empty() stack.peek().equals(popA[j])){stack.pop();j;}}return stack.empty();//最后检查栈是否为空}
}
【画图理解】 6、最小栈
【题目要求】
设计一个支持 push pop teek 操作并能在常数时间内检索到最小元素的栈。常数时间内要求的是编写这个方法的时间复杂度为O(1).
【代码思路】 【代码示例】
import java.util.Stack;
public 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()) {//如果val小于等于最小栈的栈顶元素minStack.push(val);}}}public void pop() {if(!stack.empty()){//若普通栈不为空才能将栈中元素弹出int val stack.pop();//这里发生了拆箱数值范围扩大在下面比较的时候可以直接使用若val是Integer类型是可以使用equals来比较//维护最小栈if(val minStack.peek()) {minStack.pop();}}}//这个方法就是查看栈中的元素public int top() {if(!stack.empty()) {//栈不为空进入return stack.peek();//返回查看到的栈顶元素}return -1;//栈为空返回-1}public int getMin() {return minStack.peek();//获取最小元素直接返回最小栈的栈顶元素}
}4、栈的链式存储结构 我们不仅可以使用顺序表实现栈也可以通过链表来实现栈。以单链表实现栈为例可以从链表的头部也可以是尾部插入或删除节点实现进栈和出栈。但是我们以顺序表实现栈的时候进栈和出栈时间复杂度都为O(1)那么这里我们就需要考虑用单链表实现栈的时候时间复杂度是否也可以达到O(1)。当然双链表实现栈的时候时间复杂度就是O(1)由于双链表存在一个last指针永远指向链表的结尾所以删除和插入节点都不需要遍历链表时间复杂度为O(1).下面我们来了解一下单链表实现栈单链表实现栈通过头插法和头删法来实现栈的入栈和出栈1、链栈优点 采用链式存储的栈称为链栈链栈的优点是便于斗个栈构想存储空间和提高其效率且不存在栈满的情况。通常采用单链表实现并规定所有操作都是在单链表的表头进行的。 2、实现链栈的进栈和出栈 由于栈是先进后出的原则所以用单链表实现的时候从头部插入头部删除。进栈使用的头插法。出栈的时候使用的头删法使用headNext记录下一个节点将首节点删除之后head要引用新的首节点。public class MySingleLIst {class Node {public int val;//存储数据public Node next;//存储下一个节点的地址public Node(int val) {this.val val;}}public Node head;//进栈public void push(int val) {Node node new Node(val);node.next head;node head;}//出栈public Object pop() {if (head null) {return null;}Node headNext head.next;head.next null;head headNext;headNext headNext.next;return head.val;} 二、对列
1、概念 队列只允许在一段进行插入数据操作在另一端进行删除操作的特殊线性表。 队列具有先进先出FIFO(Frist In Frist Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一段称为队头Head/Front 2、队列的基本方法
方法功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中的有效元素个数boolean isEmpty()检测队列是否为空
3、链式对列的模拟实现
1、单链表实现队列 单链表实现队列使用last记录单链表的最后一个节点在队头使用头删法出队列队尾使用尾插法进入队列 。这样可以保证在进行出入队列时时间复杂度为O(1). ❗❗❗注意这种实现队列的方式还是有一定的局限性他只能从尾巴插入头部删除。 2、使用双链表实现队列 双向链表实现队列链表的头和尾都可以实现进入队列和删除队列他的时间复杂度为O(1) ❗❗❗注释 所以说双向链表是最常用的链表。因为双向链表实现队列非常简单只需要在模拟实现双向链表的时候加入头删法和尾删法就可以用双向链表实现队列。这里我们用单链表来模拟实现队列3、单链表模拟实现队列
public class MyQueue {//实现队列static class Node {//实现队列当中的节点public int val;public Node next;public Node(int val) {this.val val;}}public Node head;public Node last;public int usedSize;//入队public void offer(int val) {Node node new Node(val);if (head null) {//当没有单链表的时候插入一个节点head和last都指向这个节点。head node;last node;} else {//当链表不为空的时候尾插法实现入栈last.next node;//链接node节点last node;//last指针后移}usedSize;//记录队列当中有多少个元素}//出队public int poll(){if(empty()){//队列是否为空若为空返回-1或者抛异常不为空将元素抛出。//这里可以抛异常也可以直接返回-1return -1;//若链表为空则返回-1.}int ret head.val;//将出队列的值记录下来head head.next;//将head引用向后移头节点没有被引用别回收实现了出队的操作if(head null){//当head后移将元素删完headnull时队列当中应该没有元素了所
//以last也要置为空否则last还引用队列当中的元素,理论上对列没有空。但是这个方法有
//usedSize计数不加if判断最终实现的效果上没有问题last null;} usedSize--;return ret;}public boolean empty(){//判断链表是否为空return usedSize 0;}//查看队头元素public int peek(){if(empty()){throw new EmptyException(队列为空);}return head.val;}//查看队列当中的元素个数public int getUsedSize(){return usedSize;}
}测试
public class Test {public static void main(String[] args) {MyQueue myQueue new MyQueue();myQueue.offer(1);myQueue.offer(2);myQueue.offer(3);myQueue.offer(4);System.out.println(myQueue.peek());System.out.println(myQueue.poll());System.out.println(myQueue.getUsedSize());} 4、对列的顺序存储结构
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素并附设两个指针队头指针front指向队头元素。队尾指针rear指向队尾元素的下一个位置。
通过数组模拟入队列时的操作 模拟出队列时的操作 顺序队列的缺点就是会出现假溢出的问题。为了解决顺序队列的“假溢出”也就是空间只能用一次严重浪费的问题数据结构引出了循环队列的概念1、循环队列
循环队列就是将顺序队列臆造为一个环状的空间即把存储队列元素的表从逻辑上视为一个环。 通过上图可以看到当队列为空或者满的时候 队头指针front和队尾指针rear都会指向同一个节点换句话说两个指针会重合。那么这里就会产生两个问题 ❓❓❓rear从7下标到0下标或者说两个指针相遇此时队列到底是空还是满❓❓❓循环队列实际上还是以数组的形式实现的环形只不过是方便了理解臆造的。rear从7下标如何到0下标第一个问题判断队列是否已满。 第一种方法在实现循环对列的时候定义一个usedSize用来记录数组中元素的个数想要判断循环对列是否已满可以直接输出usedSzie的值进行判断。这种方法不浪费空间。第二种方法牺牲一个空间如上图当rear走到7下标位置判断rear的下一个位置是否为front若是则判断队列已满若不是队列没满。第二个问题从7下标如何到0下标位置这个问题的解决前提就是牺牲一个空间的方法 rear存在从7下标位置到0下标位置同样在出队列的时候front也存在这样的问题。 这里使用取余的方式rear (rear 1)%array.len 添加几个元素则rear向后挪动几步因为取余1%8 12%82...9%8 1。当除数小于被除数时结果都是除数本身。 总结 判断队列是否已满的问题也是可以通过第二个问题当中的公式来进行判断的 rear1%array.len front 【代码示例】
public 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) {//1、检查队列是否已满if(isFull()){return false;}//2、没满elem[rear] value;//这里不能使用后移在走到最后一个下标位置的时候通过结果不会变为0后移就会数组越界。//rear;//这种写法当rear走到最后一个位置的时候取余之后结果为0rear指向0下标位置rear (rear1)%elem.length;return false;}//出队列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;//判断若只有一个元素,则用elem.length - 1计算数组下标若数组中有多个元素则使用rear - 1来计算数组下标return elem[index];}//判断是否为空public boolean isEmpty() {return front rear;}//判断是否已满public boolean isFull() {
// if((rear1)%elem.length front){
// return true;
// }
// return false;return (rear1)%elem.length front;
//这里两种写法都可以}
}4、双端队列
1、定义
双端队列deque是指允许两端都可以进行入队和出队操作的队列如下图所示。其元素的逻辑结构仍是线性结构。将队列的两端给别成为前端和后端两端都可以入队和出队。 Deque是一个接口使用时必须创建LinkedList的对象。 在实际工程中使用Deque接口是比较多的栈和队列都可以使用该接口。 由于ArrayDeque和ListedList都实现了Deque接口所以双端队列可以实现链式的也可以实现线性结构的 DequeInteger queue1 new ArrayDeque();//双端队列的线性实现
DequeInteger queue2 new LinkedList();//双端队列的链式实现 5、Java集合的使用
通过之前的学习我们知道通过LinkedList可以实现很多数据结构
比如通过LinkedList实现链表栈队列。
DequeInteger deque new LinkedList();//此时LinkedList就被当作了双端队列
QueueInteger queue new LinkedList();//此时LinkedList就被当作了普通队列
LinkedListInteger stack new LinkedList();//此时LinkedList就被当做了链式栈
ListInteger list new LinkedList();//此时LinkedList被当作了链表单向、双向LinkedList当中这些数据结构的方法都存在使用的时候只需要调用相应的数据结构的方法就行。 三、 栈和队列的练习
1、用队列实现栈
队列数据的操作方式是先进的先出栈的数据操作方式是先进的后出。
两种数据结构的操作方式是相反的所以要用队列实现栈那么就要用两个队列来实现。 import java.util.LinkedList;
import java.util.Queue;public class MyStack2 {private QueueInteger qu1;private QueueInteger qu2;public MyStack2() {qu1 new LinkedList();qu2 new LinkedList();}//入队列public void push(int x) {if(!qu1.isEmpty()){//qu1不为空qu1.offer(x);}else if(!qu2.isEmpty()){//qu2不为空qu2.offer(x);}else{//qu1和qu2都为空qu1.offer(x);}}//出队列public int pop() {if(empty()){return -1;//判断两个队列都为空,意味着当前的栈为空}if(!qu1.isEmpty()){//qu1队列不为空int size qu1.size();for(int i 0;i size - 1;i){int val qu1.poll();//记录出qu1队列的值qu2.offer(val);//将qu1中出来的值放入到qu2中}return qu1.poll();}else{//qu2队列不为空int size qu2.size();for(int i 0;i size - 1;i){int val qu2.poll();//记录出qu1队列的值qu2.offer(val);//将qu1中出来的值放入到qu2中}return qu2.poll();}}//peek,查看栈顶元素public int top() {if(empty()){return -1;//判断两个队列都为空,意味着当前的栈为空}if(!qu1.isEmpty()){//qu1队列不为空int size qu1.size();//在循环出队列的时候队列当中的元素在减少要使用一
//个在循环外的变量记录队列当中开始元素的个数不能直接将qu1.size()作为循环的结束条件,
//若是将其作为循环的结束条件则循环次数就会减少int val -1;for(int i 0;i size - 1;i){val qu1.poll();//记录出qu1队列的值qu2.offer(val);//将qu1中出来的值放入到qu2中}return val;}else{//qu2队列不为空int size qu2.size();int val -1;for(int i 0;i size - 1;i){val qu2.poll();//记录出qu1队列的值qu2.offer(val);//将qu1中出来的值放入到qu2中}return val;}}public boolean empty() {return qu1.isEmpty() qu2.isEmpty();}}2、用栈实现队列 【代码示例】
import java.util.Stack;
public class MyQueue2 {private StackInteger stack1;private StackInteger stack2;public MyQueue2() {stack1 new Stack();stack2 new Stack();}//入队列public void push(int x) {stack1.push(x);}//出队列public int pop() {if(empty()){//两个栈都为空即队列为空return -1;}if(stack2.empty()){//如果第二个栈为空while(!stack1.empty()){//若第一个栈不为空进入循环stack2.push(stack1.pop());//将第一个栈中所有的元素弹出依次压入第二个栈中}}return stack2.pop();//弹出第二个栈中的栈顶元素这样就实现了出队列}//查看队列的首元素public int peek() {if(empty()){//两个栈都为空即队列为空return -1;}if(stack2.empty()){//如果第二个栈为空while(!stack1.empty()){//若第一个栈不为空进入循环stack2.push(stack1.pop());//将第一个栈中所有的元素弹出依次压入第二个栈中}}return stack2.peek();}public boolean empty() {return stack1.isEmpty()stack2.isEmpty();//判断两个栈是否都为空}
}
