app与网站的区别,怎样做企业手机网站首页,适合新手做的网站,wordpress vip解析文章目录 栈和队列栈基本概念栈的模拟实现集合框架中的栈栈的创建栈的方法栈的遍历 栈的应用及相关练习括号匹配逆波兰表达式求值出栈入栈次序匹配最小栈 几个含栈概念的区分 队列基本概念队列的模拟实现循环队列双端队列集合框架中的队列队列的创建队列的方法队列… 文章目录 栈和队列栈基本概念栈的模拟实现集合框架中的栈栈的创建栈的方法栈的遍历 栈的应用及相关练习括号匹配逆波兰表达式求值出栈入栈次序匹配最小栈 几个含栈概念的区分 队列基本概念队列的模拟实现循环队列双端队列集合框架中的队列队列的创建队列的方法队列的遍历 队列的应用及相关练习用队列实现栈用栈实现队列 栈和队列
栈
基本概念
栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作即 “先进后出”
栈顶即进行数据插入和删除操作的一端栈底即与栈顶相对的另一端。
栈的插入操作叫做压栈/进栈/入栈栈的删除操作叫做出栈/退栈/弹出。栈的插入和删除操作都在栈顶一端。 了解了基本的概念后我们尝试做一道小题体会栈的先进后出的特性 进栈序列为1234 并且进栈的过程中可以出栈则不可能的出栈序列是 A. 1,4,3,2 B. 2,3,4,1 C. 3,1,4,2 D. 3,4,2,1 想象现在有一个栈最好还是画图对于A1进1出2进3进4进4出3出2出满足对于B1进2进2出3进3出4进4出1出满足对于C1进2进3进3出此时栈顶元素为2只能先出2才能出1所以该序列不可能为出栈序列不满足对于D1进2进3进3出4进4出2出1出满足
所以答案为C 栈的模拟实现
了解了栈以及栈的特性思考怎么实现一个栈使其满足栈的特性
其实使用数组和链表都可以我们需要实现的方法包括
入栈操作出栈操作获取栈顶元素获取栈中的有效元素个数判断栈是否为空
接下来我们就分别使用数组和链表实现一个栈
【数组实现栈】
实现一个类类中定义一个数组成员变量为了满足栈的特性数组只允许尾插和尾删
大体框架如下
public class MyStackByArray {public int[] elem;//栈public int capacity;//栈的容量public int usedSize;//栈的有效元素个数public MyStackByArray() {this.elem new int[10];this.capacity 10;}//入栈public void push(int data) {}//出栈并返回出栈元素public int pop() {}//获取栈顶元素public int peek() {}//获取栈中的有效元素public int size() {}//检测栈是否为空public boolean empty() {}
}public int size()
返回成员变量usedSize即可 //获取栈中的有效元素public int size() {return this.usedSize;}public boolean empty() //检测栈是否为空public boolean empty() {return this.usedSize 0;}public void push(int data)
由于数组下标从0开始所以成员变量usedSize其实就是下一次入栈的下标位置。入栈前我们要判断栈是否满满了要扩容之后进行入栈即可 //入栈public void push(int data) {//栈满则扩容if(this.capacity usedSize) {this.elem Arrays.copyOf(elem, this.capacity * 2);this.capacity * 2;}//入栈this.elem[this.usedSize] data;this.usedSize;}public int pop()
出栈前我们判断栈是否为空当为空时我们选择抛出一个自定义异常StackIsException
public class StackIsEmptyException extends RuntimeException {public StackIsEmptyException(String message) {super(message);}
}如果不为空执行出栈注意出栈直接让usedSize--即可不需要特意将栈顶元素置成0因为当下次入栈时会覆盖掉此元素 //出栈并返回出栈元素public int pop() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException(The Stack Is Empty!: 栈为空!);}//出栈this.usedSize--;return this.elem[this.usedSize];}public int peek()
获取栈顶元素判断为空为空抛出异常否则返回 //获取栈顶元素public int peek() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException(The Stack Is Empty!: 栈为空!);}return this.elem[this.usedSize - 1];}完整代码
public class MyStackByArray {public int[] elem;public int capacity;public int usedSize;public MyStackByArray() {this.elem new int[10];this.capacity 10;}//入栈public void push(int data) {//栈满则扩容if(this.capacity usedSize) {this.elem Arrays.copyOf(elem, this.capacity * 2);this.capacity * 2;}//入栈this.elem[this.usedSize] data;this.usedSize;}//出栈并返回出栈元素public int pop() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException(The Stack Is Empty!: 栈为空!);}//出栈this.usedSize--;return this.elem[this.usedSize];}//获取栈顶元素public int peek() {//判断栈是否为空if(empty()) {throw new StackIsEmptyException(The Stack Is Empty!: 栈为空!);}return this.elem[this.usedSize - 1];}//获取栈中的有效元素public int size() {return this.usedSize;}//检测栈是否为空public boolean empty() {return this.usedSize 0;}
}【链表实现栈】
对于出栈我们选择头删因为尾删得遍历链表找到倒数第二个结点效率较低
对于入栈我们选择头插因为出栈选择的是头删要满足先进后出必须选择头插。
代码比较简单我们直接给出完整实现
public class MyStackByLinkedList {//链表结点类static class ListNode {public int val;public ListNode next;public ListNode(int val) {this.val val;}}//链表第一个结点的引用public ListNode head;//入栈public void push(int data) {ListNode newNode new ListNode(data);if(head null) {head newNode;return;}newNode.next head;head newNode;}//出栈并返回出栈元素public int pop() {if(empty()) {throw new StackIsEmptyException(The Stack Is Empty!: 栈为空!);}int ret head.val;head head.next;return ret;}//获取栈顶元素public int peek() {if(empty()) {throw new StackIsEmptyException(The Stack Is Empty!: 栈为空!);}return head.val;}//获取栈中的有效元素public int size() {int count 0;ListNode cur head;while(cur ! null) {count;cur cur.next;}return count;}//检测栈是否为空public boolean empty() {return head null;}
}集合框架中的栈
集合框架中顺序表对应ArrayList链表对应LinkedList那么栈对应什么呢
栈的创建
栈对应三个Stack、LinkedList、ArrayDeque即这三个类都可以作为栈
Stack类就是原生的栈类。只有无参构造方法LinkedList实现了Deque接口Deque接口是双端队列接口其中包含了操作栈的方法所以LinkedList可作为链栈类。构造方法有两个无参构造和利用其他容器的构造ArrayList也实现了Deque接口实现了操作栈的方法是基于数组的数据结构。构造方法有三个无参构造、指定初始容量的构造、利用其他容器的构造 public static void main(String[] args) {StackInteger stack0 new Stack();//StackLinkedListInteger stack1 new LinkedList();//LinkedListArrayDequeInteger stack2 new ArrayDeque();//ArrayDeque}栈的方法
方法功能E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek()获取栈顶元素int size()获取栈中的有效元素的个数boolean empty()检测栈是否为空
注意如果使用LinkedList或ArrayDeque实现栈那么判空的方法为boolean isEmpty()而不是boolean empty()
栈的遍历
关于栈的遍历有三种方法分别是迭代器、for-each和方法遍历
对于Stack、LinkedList和ArrayDeque来说利用方法遍历的结果是一致的都是按照先进后出’的原则并且这也是最常用的方法 public static void main(String[] args) {StackInteger s1 new Stack();LinkedListInteger s2 new LinkedList();ArrayDequeInteger s3 new ArrayDeque();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println(Stack);while(!s1.empty()) {System.out.print(s1.pop() );}System.out.println();System.out.println(LinkedList);while(!s2.isEmpty()) {System.out.print(s2.pop() );}System.out.println();System.out.println(ArrayDeque);while(!s3.isEmpty()) {System.out.print(s3.pop() );}System.out.println();}Stack使用迭代器打印的顺序是从栈底到栈顶并不是出栈顺序这是因为Stack是基于数组实现的每次入栈都是在尾部而LinkedList和ArrayDeque是按照出栈顺序打印的这是因为它们入栈都是在头部/顶部进行的头插 public static void main(String[] args) {StackInteger s1 new Stack();LinkedListInteger s2 new LinkedList();ArrayDequeInteger s3 new ArrayDeque();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println(Stack);IteratorInteger it1 s1.iterator();while(it1.hasNext()) {System.out.print(it1.next() );}System.out.println();System.out.println(LinkedList);IteratorInteger it2 s2.iterator();while(it2.hasNext()) {System.out.print(it2.next() );}System.out.println();System.out.println(ArrayDeque);IteratorInteger it3 s3.iterator();while(it3.hasNext()) {System.out.print(it3.next() );}System.out.println();}for-each遍历的结果与迭代器遍历的结果一致 public static void main(String[] args) {StackInteger s1 new Stack();LinkedListInteger s2 new LinkedList();ArrayDequeInteger s3 new ArrayDeque();s1.push(1);s1.push(2);s1.push(3);s2.push(1);s2.push(2);s2.push(3);s3.push(1);s3.push(2);s3.push(3);System.out.println(Stack);for(Integer x : s1) {System.out.print(x );}System.out.println();System.out.println(LinkedList);for(Integer x : s2) {System.out.print(x );}System.out.println();System.out.println(ArrayDeque);for(Integer x : s3) {System.out.print(x );}System.out.println();}栈的应用及相关练习
栈的先进后出’的特性使得栈的应用场景十分广泛比如将序列逆序、递归转化为非递归等等。
下面是几道关于栈的经典题目
括号匹配
给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
class Solution {public boolean isValid(String s) {//补充代码}
}【思路】
遍历字符串的每个字符如果是左括号就入栈如果是右括号就从栈中弹出一个元素看左右括号是否匹配。
最终结果不匹配的原因可能是
只有左括号 或 只有右括号 或 左右括号数量不一致左右括号类型不匹配
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();int i 0;for(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 top stack.pop();switch(top) {case (:if(ch ! )) {return false;}break;case [:if(ch ! ]) {return false;}break;case {:if(ch ! }) {return false;}break;}}}}if(!stack.empty()) {return false;}return true;}
}原题链接20. 有效的括号 - 力扣LeetCode 逆波兰表达式求值
给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
class Solution {public int evalRPN(String[] tokens) {//补充代码}
}【思路】
逆波兰表达式也叫后缀表达式即将运算符写在操作数的后面。我们平时习惯使用中缀表达式举个简单的例子
对于中缀表达式(1 2) * 3转化为后缀表达式1 2 3 *
对于上面的后缀表达式的计算过程为 寻找运算符即找到了然后将前的两个操作数执行运算得到3此时表达式化简为3 3 *继续向后找到*运算符将前面两个操作数执行*运算得到9此时9就是表达式的结果。
了解了后缀表达式的求解我们就可以解决这道题目
遍历字符串数组如果是数字就入栈如果是运算符就不入栈并从栈中弹出两个元素执行运算将结果入栈以此循环最终栈中会剩余一个元素这个元素就是表达式的结果
注意的问题
题目给的是字符串数组进行运算时要将字符串类型转换为int类型弹出时先弹出的是右操作数后弹出的是左操作数注意两者的顺序以免计算出错
class Solution {public int evalRPN(String[] tokens) {StackString stack new Stack();for(int i 0; i tokens.length; i) {String s tokens[i];if(s.equals() || s.equals(-) || s.equals(*) || s.equals(/)) {int op2 Integer.valueOf(stack.pop());int op1 Integer.valueOf(stack.pop());switch(s) {case :stack.push(String.valueOf(op1 op2));break;case -:stack.push(String.valueOf(op1 - op2));break;case *:stack.push(String.valueOf(op1 * op2));break;case /:stack.push(String.valueOf(op1 / op2));break;} }else {stack.push(s);}}return Integer.valueOf(stack.pop());}
}原题链接150. 逆波兰表达式求值 - 力扣LeetCode 出栈入栈次序匹配
输入两个整数序列第一个序列表示栈的压入顺序请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序序列4,5,3,2,1是该压栈序列对应的一个弹出序列但4,3,5,1,2就不可能是该压栈序列的弹出序列。
0pushV.length popV.length 1000-1000pushV[i]1000pushV 的所有数字均不相同
public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型一维数组 * param popV int整型一维数组 * return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {//补充代码}
}【思路】
遍历入栈序列每次将该次遍历到的元素入栈然后判断当前的栈顶元素是否与出栈序列的元素相等即是否可以出栈如果可以就出栈出栈一次后遍历出栈序列的指针也要后移直到不能出栈了继续遍历入栈序列遍历完成后如果栈为空说明匹配。 public boolean IsPopOrder (int[] pushV, int[] popV) {// write code hereStackInteger stack new Stack();int j 0;for(int i 0; i pushV.length; i) {stack.push(pushV[i]);while(j popV.length !stack.isEmpty() stack.peek() popV[j]) {stack.pop();j;}}return stack.isEmpty();}注意
while循环判断是否可以出栈前要判断栈是否为空否则可能会抛出栈空异常j popV.length在本题目中可以不写因为题目保证两个序列长度相等如果测试用例给出的长度不一定相等那就需要加上
原题链接栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com) 最小栈
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
class MinStack {public MinStack() {}public void push(int val) {}public void pop() {}public int top() {}public int getMin() {}
}
【思路】
维护两个栈一个是普通的栈一个是存放最小值的栈它的栈顶元素就是当前状态下的普通栈中的最小值具体操作
当入栈时普通的栈直接入栈如果最小值栈为空或者最小值栈的栈顶元素入栈元素那么最小值栈也入栈该元素
当出栈时普通的栈直接出栈同时判断普通栈的出栈元素是否与当前最小值栈的栈顶元素一致如果一致最小值栈也弹出元素一次
当想要获取当前栈中的最小元素时直接返回最小值栈的栈顶元素
如此维护了两个栈。
class MinStack {public StackInteger stack;public StackInteger minStack;public MinStack() {stack new Stack();minStack new Stack();}public void push(int val) {stack.push(val);if(minStack.empty() || minStack.peek() val) {minStack.push(val);}}public void pop() {if(stack.empty()) {return;}if(stack.pop().equals(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();}
}注意 最小值栈入栈的条件当入栈元素与当前最小值栈的栈顶元素相等时也要入栈相当于有多个相等的最小值。 这一条是笔者在解决该问题时出现的问题如果我将pop()方法改成如下代码是否可行 public void pop() {if(stack.empty()) {return;}if(stack.pop() minStack.peek()) {minStack.pop();}}不可行 因为Stack类中的pop()和peek()方法返回的是类型实参的类型即实现泛型时里传入的类型是引用类型如果像上面这样书写本质上是对两个引用类型使用比较引用类型比较的是地址而不是值所以不可行 但是对于该题目泛型实现时传入的是Integer类型通过比较时可能会出现true的情况这是因为Integer有缓存机制 缓存机制 Java对于Integer类型的对象在值位于-128到127之间时有特殊的缓存处理。JVM会为这个范围的每个数字缓存一个Integer对象。 例如Integer a 127; Integer b 127; System.out.println(a b); // 输出 true因为a和b都指向同一个缓存的对象。 对于超出该范围的数字即使值相同也会创建不同的对象实例所以会比较返回false。 如 Integer c 128; Integer d 128; System.out.println(c d); // 输出 false。 我们无法保证题目给出的值在缓存区间内所以不可以像上面那样书写我们可以使用equals方法判断它们的值是否相等就如答案所示或者这么写 public void pop() {if(stack.empty()) {return;}int tmp stack.pop();if(tmp minStack.peek()) {minStack.pop();}}上面这个代码将Stack类中的pop方法的返回值用int类型的一个变量接收返回值是Integer类型所以会自动拆箱为int类型再用int类型与peek方法返回值的Integer类型使用比较而当使用比较Java中的Integer类型与int类型时会将Integer类型拆箱为int类型所以本质上是两个int类型的比较可行 原题链接155. 最小栈 - 力扣LeetCode 几个含栈概念的区分
区分栈、虚拟机栈和栈帧
栈、虚拟机栈和栈帧是Java虚拟机JVM中的三个相关但不同的概念它们在定义功能、数据结构以及生命周期等方面存在明显的区别
定义功能 Java栈通常指的是一种后进先出LIFO的数据结构用于存储程序执行过程中的临时数据。例如方法的局部变量和返回地址等。虚拟机栈特指JVM为每个线程分配的独立内存区域用于存放栈帧即方法调用的信息。它与线程同时创建和销毁主要支持方法的调用和执行。栈帧是虚拟机栈中的一个元素对应于正在执行的每个方法。每个方法执行时都会创建一个对应的栈帧包含局部变量表、操作数栈、动态链接以及方法出口等信息。 数据结构 Java栈作为一种数据结构其实现可以基于数组或链表主要用于算法中数据的临时存储。虚拟机栈作为JVM内部的一个运行时数据区其内部由多个栈帧组成每个栈帧对应一个方法调用的相关信息。栈帧具有固定的数据结构包括局部变量表、操作数栈等这些组成部分在编译期间就已经确定大小。 生命周期 Java栈根据程序逻辑进行入栈和出栈操作使用完毕后即可销毁。虚拟机栈与线程绑定线程结束时对应的虚拟机栈也会被销毁。栈帧在方法调用时创建方法执行完毕或异常终止时销毁。 存储内容 Java栈可用于存储任何类型的对象如基本类型、引用类型等。虚拟机栈专门用于存储方法调用的相关信息如局部变量、操作数等。栈帧具体存储了方法的局部变量表、操作数栈、动态链接以及方法的返回地址等信息。 应用场景 Java栈广泛应用于各类算法中如深度优先搜索、递归计算等。虚拟机栈在JVM的执行引擎中应用用于支持方法的调用和执行。栈帧直接关联到每个方法的具体执行过程记录了方法执行所需的全部信息。
总的来说Java栈、虚拟机栈和栈帧各自承担着不同的功能和角色。Java栈是一个通用的数据结构而虚拟机栈和栈帧则是JVM内部专门设计的机制用于支持方法的调用和执行。这三者共同协作确保了Java程序能够高效、安全地运行。 队列
基本概念
队列是只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表其特点概括为 “先进先出”就像现实生活中的排队一样在最早排队的总是先出队。
队头进行删除操作的一端队尾进行插入操作的一端 注意区分栈和队列。 队列的模拟实现
了解了队列的基本概念后思考怎样实现一个队列使用数组还是链表
假设使用数组通常我们会定义一个队头变量和队尾变量以方便入队和出队操作入队操作使用尾插那么出队操作就必须是头删。当队列不为空每次出队队头变量要不断地向后移动最终会导致数组的前半部分空间都被浪费了且队列容量越来越少所以简单的数组实现队列是不方便的如果要使用数组那么最好实现成循环队列后面会讲。
一般来说队列使用链表实现问题是入队和出队操作怎么实现对于单链表定义两个引用分别指向队头和队尾如果出队采用尾删那么我们就得遍历链表找到倒数第二个结点让它的next为null效率较低所以出队采用头删相应地入队采用尾插从而达到先进先出的特点并且保证了入队和出队的时间复杂度都是O(1)。
但如果是双向链表那么就不需要考虑上面的问题入队出队操作都是O(1)我们这里采用双向链表模拟实现一个队列
实现如下双向链表的头删、尾插操作较为简单
public class MyQueue {//链表结点类static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val val;}}public ListNode head;//队头引用public ListNode tail;//队尾引用private int size;//队列有效元素个数//入队public void offer(int data) {ListNode newNode new ListNode(data);if(tail null) {head newNode;tail newNode;size;return;}tail.next newNode;newNode.prev tail;tail newNode;size;}//出队并返回出队元素public int poll() {if(this.head null) {throw new QueueIsEmptyException(The Queue Is Empty!: 队列为空!);}int ret head.val;if(head tail) {head null;tail null;}else {head.next.prev null;head head.next;}size--;return ret;}//获取队头元素public int peek() {if(this.head null) {throw new QueueIsEmptyException(The Queue Is Empty!: 队列为空!);}return this.head.val;}//获取队列中的有效元素个数public int size() {return this.size;}//判断队列是否为空public boolean isEmpty() {return this.head null;}}循环队列
前面提到单纯的数组实现队列会导致空间的浪费以及队列大小的缩减这时候引出了循环队列的概念
循环队列是一种优化的队列数据结构旨在解决顺序队列中存在的“假溢出”问题。
循环队列采用了头尾相接的环状存储结构通过将顺序队列的数组视为一个循环结构使得当存储空间的最后一个位置已被使用时新元素可以继续从第一个位置开始存储形成一个逻辑上的环。这种设计极大地提高了存储空间的利用率。
接下来我们就讲解一下循环队列的思想关于循环队列我们要解决两大问题 当存储空间的最后一个位置已被使用时新元素怎样继续从第一个位置开始存储? 怎样区分循环队列的 空 和 满 两个状态 【问题一】
在实现循环队列时我们仍然会定义两个指针rear(指向队尾这个队尾实际上是下一次入队的位置而不是指队尾元素)、front(指向队头即队头元素)于是就可能会出现下图的情况 此时存储空间的最后一个位置已被使用rear指向了最后位置后面的一个位置此位置不能入新元素了而此时由于进行过出队操作数组的前面还有剩余空间可以使用我们就得想办法让空闲空间被利用到即让rear重新回到数组开始的位置怎么办
传统的rear 1肯定不行我们采用这样的语句 rear (rear 1) % lenlen就是数组长度。对于上面的情况我们代入公式
rear (8 1) % 9得到0此时rear就重新回到了数组0下标位置这个公式在任何位置都是可以的。有了这个公式front和rear就可以循环起来了。 【问题二】
怎样区分循环队列的 空 和 满 两个状态 我们看如下图表示的情况为了突出循环我们将数组在视觉上改成环 图1表示队列为空图2表示队列已满但是两种情况下都是rear front怎么区分呢
我们有三种解决方案
定义成员变量size表示队列中的有效元素个数当size和数组长度相等时表示满为0时表示空定义一个boolean类型的标记最开始为false当入队新元素后变为true当出队元素后rear front说明最后一个元素出队了将其置为false。这样当rear front 标记为false时表示空当rear front 标记为true时表示满浪费一个空间即留出一个空间不放元素当rear front时表示空当(rear 1) % len front(下一个位置是队头)时表示满 解决完上面的两个问题我们以第二种解决方案动手实现一下分析与注意事项在代码后面
public class CircularQueue {public int[] elem;//数组private boolean flag;//标记public int rear;//队尾指针public int front;//队头指针public CircularQueue() {elem new int[10];}public void offer(int data) {if(rear front flag true) {System.out.println(队列已满);return;}elem[rear] data;rear (rear 1) % elem.length;flag true;}public int poll() {if(isEmpty()) {throw new QueueIsEmptyException(The Queue Is Empty!: 队列为空!);}int ret elem[front];front (front 1) % elem.length;if(rear front) {flag false;}return ret;}public int peek() {if(isEmpty()) {throw new QueueIsEmptyException(The Queue Is Empty!: 队列为空!);}return elem[front];}public int size() {if(rear front) {return rear - front;}else if(rear front) {return rear (elem.length - front);}else {return flag true ? elem.length : 0;}}public boolean isEmpty() {return rear front flag false;}
}rear实际上指向下一次入队的位置而不是指向队尾元素而front是指向队头元素offer方法最后一定要将标记置为truepoll方法内部在front因出队改变后要检查是否要将标记置为false即检查该次出队的是否是队列中最后一个元素size方法考虑的就比较多了循环队列的思想导致rear和front的相对位置会发生变化如代码分为rear front、rear front以及rear front特别注意第三种相等的情况可能是满了也可能是空这要根据标记判断。 不妨做个练习尝试使用问题二中的其他方案设计循环队列
class MyCircularQueue {public MyCircularQueue(int k) {}public boolean enQueue(int value) {}public boolean deQueue() {}public int Front() {}public int Rear() {}public boolean isEmpty() {}public boolean isFull() {}
}给出以浪费一个空间方案完成该题目的代码
class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {elem new int[k 1];}public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] value;rear (rear 1) % elem.length;return true;}public boolean deQueue() {if(isEmpty()) {return false;}front (front 1) % elem.length;return true;}public int Front() {if(isEmpty()) {return -1;}return elem[front];}public int Rear() {if(isEmpty()) {return -1;}if(rear 0) {return elem[elem.length - 1];}return elem[rear - 1];}public boolean isEmpty() {return rear front;}public boolean isFull() {return (rear 1) % elem.length front;}
}既然要浪费一个空间那么我们在构造方法初始化数组时要创建一个比参数大1个空间的数组保证一部分测试用例能够顺利通过。Rear方法要求返回队尾元素由于我们的rear是队尾元素之后的一个位置所以我们必须向前一个位置找这里就有一个特殊情况当rear 0此时不能减一前一个应该是数组最后一个下标的位置所以有如上代码。
原题链接622. 设计循环队列 - 力扣LeetCode 双端队列
双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 在集合框架中双端队列对应Deque接口在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口。
实现双端队列可以用LinkedList链式实现或ArrayDeque线性实现 public static void main(String[] args) {DequeInteger deque1 new LinkedList();//链式实现DequeInteger deque2 new ArrayDeque();//线性实现}所以到这里我们发现
LinkedList可以作为链表、栈、(普通)队列、双端队列
ArrayList可以作为栈、(普通)队列、双端队列 集合框架中的队列
集合框架中的队列是Queue接口Deque接口继承自它LinkedList和ArrayDeque都实现了该接口。 队列的创建
我们可以通过ArrayDeque或者LinkedList创建一个队列 public static void main(String[] args) {QueueInteger queue1 new LinkedList();//链式队列QueueInteger queue2 new ArrayDeque();//线性队列}队列的方法
方法功能boolean offer(E e)入队列E poll()出队列E peek()获取队头元素int size()获取队列中有效元素个数boolean isEmpty()检测队列是否为空 队列的遍历 public static void main(String[] args) {QueueInteger queue1 new LinkedList();queue1.offer(1);queue1.offer(2);queue1.offer(3);queue1.offer(4);queue1.offer(5);System.out.println(for-each);for(Integer x : queue1) {System.out.print(x );}System.out.println();System.out.println(迭代器);IteratorInteger it queue1.iterator();while(it.hasNext()) {System.out.print(it.next() );}System.out.println();System.out.println(while);while(!queue1.isEmpty()) {System.out.print(queue1.poll() );}System.out.println();}队列的应用及相关练习
用队列实现栈
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
class MyStack {public MyStack() {}public void push(int x) {}public int pop() {}public int top() {}public boolean empty() {}
}【思路】
以画图文字介绍 现在我们要模拟出栈如图向栈中依次加入21、56、23、11此时栈顶元素应为11出栈时要弹出11。
我们只有两个队列所以让不为空的队列中的元素出队直到只剩1个元素这个元素就是栈顶元素将它弹出此时如果再次入队 此时如果再添加新元素继续向非空队列添加而它就是新的栈顶元素如果接着出栈就重复上面的工作将元素出队到空队列直到只剩一个元素弹出。
所以有 入栈 向非空队列中添加元素初始都为空时随意选择 出栈 非空队列将元素出到空队列中直到只剩下一个元素这个元素就是栈顶元素弹出 class MyStack {public QueueInteger q1;public QueueInteger q2;public MyStack() {q1 new LinkedList();q2 new LinkedList();}public void push(int x) {if(!q1.isEmpty()) {q1.offer(x);}else if(!q2.isEmpty()){q2.offer(x);}else{q1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size q1.size();for(int i 0; i size - 1; i) {q2.offer(q1.poll());}return q1.poll();}else{int size q2.size();for(int i 0; i size - 1; i) {q1.offer(q2.poll());}return q2.poll();}}public int top() {if(empty()) {return -1;}if(!q1.isEmpty()) {int size q1.size();int ret 0;for(int i 0; i size; i) {ret q1.poll();q2.offer(ret);}return ret;}else{int size q2.size();int ret 0;for(int i 0; i size; i) {ret q2.poll();q1.offer(ret);}return ret;}}public boolean empty() {return q1.isEmpty() q2.isEmpty();}
}原题链接225. 用队列实现栈 - 力扣LeetCode 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
class MyQueue {public MyQueue() {}public void push(int x) {}public int pop() {}public int peek() {}public boolean empty() {}
}【思路】 如上图如果不再添加新元素按照图解思路出队得到序列[10, 44, 31, 12, 101, 88, 36]满足队列的先进先出。
class MyQueue {public StackInteger sIn;public StackInteger sOut;public MyQueue() {sIn new Stack();sOut new Stack();}public void push(int x) {sIn.push(x);}public int pop() {if(empty()) {return -1;}if(sOut.empty()) {while(!sIn.empty()) {sOut.push(sIn.pop());}}return sOut.pop();}public int peek() {if(empty()) {return -1;}if(sOut.empty()) {while(!sIn.empty()) {sOut.push(sIn.pop());}}return sOut.peek();}public boolean empty() {return sIn.empty() sOut.empty();}
}原题链接232. 用栈实现队列 - 力扣LeetCode 完
