义乌市网站建设代理莆田高端网站建设

当前位置： 首页 > news >正文

义乌市网站建设代理,莆田高端网站建设,百度提交网站收录入口,织梦搭建网站教程前言#xff1a;上一篇我们介绍了顺序表和链表 #xff08;https://blog.csdn.net/iiiiiihuang/article/details/132615465?spm1001.2014.3001.5501#xff09;#xff0c; 这一篇我们将介绍栈和队列#xff0c;栈和队列都是基于顺序表和链表来实现的 目录 栈#xff… 前言上一篇我们介绍了顺序表和链表 https://blog.csdn.net/iiiiiihuang/article/details/132615465?spm1001.2014.3001.5501 这一篇我们将介绍栈和队列栈和队列都是基于顺序表和链表来实现的 目录 栈Stack 什么是栈
栈的方法 和 使用 栈的模拟实现  先初始化一下栈  往栈里插入元素 push) 栈是否为空(empty) 弹出栈顶元素删除(pop) 获取栈顶元素 (peek) 模拟实现完整代码  栈的应用场景 1. 改变元素的序列

1. 将递归转化为循环 补充
   队列Queue  什么是队列
   队列的方法  队列模拟实现  初始化  offer  poll peek 完整代码链式队列  循环队列  认识循环队列  如何把数组看作是一个循环呢rear 从 7 – 0)  设计一个循环队列 https://leetcode.cn/problems/design-circular-queue/ 初始化  判断队列是否是空的和是否是满的  入队  出队 得到队头元素 得到队尾元素 完整代码 循环队列 双端队列 (Deque) 面试题 1. 用队列实现栈   2. 用栈实现队列 1. 用队列实现栈 代码实现 入栈 出栈  获取栈顶元素  判断栈空 完整代码  2. 用栈实现队列  我直接上代码了  栈Stack 什么是栈 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 后进先出原则先进的后出后进的先出  。我们举一个生活中的例子 比如这有个圆筒一端封闭一端开口然后往圆筒里放乒乓球 你想拿乒乓球先拿到的肯定是后放的那如果你想要拿到最底下的你肯定得把上面的都拿走才行。也就是 栈的后进先出原则 先进的后出后进的先出 栈的方法 和 使用 栈的方法很少只有这些  使用 没什么好说的 栈的模拟实现  栈这种数据结构可以用数组来实现也可以用链表来实现这里我们用数组实现。 先初始化一下栈  往栈里插入元素 push) 和顺序表异曲同工先看看满没满满了要扩容再入栈  栈是否为空(empty) 弹出栈顶元素删除(pop) 就很简单 顺序表那搞懂这些方法很简单的 获取栈顶元素 (peek) 模拟实现完整代码  import java.util.ArrayList; import java.util.Arrays;/*** Author: iiiiiihuang/ public class MyStack {private int[] elem;private int usedSize;private static final int DEFAULT_CAPACITY 10;//默认容积public MyStack() {this.elem new int[DEFAULT_CAPACITY];}/** 往栈里插入元素* param val*/public void push(int val) {isFull();this.elem[usedSize] val;usedSize;}private void isFull() {if(usedSize this.elem.length) {this.elem Arrays.copyOf(this.elem, 2this.elem.length);}}/** 弹出栈顶元素* return/public int pop() {if(empty()) {throw new EmptyException(栈为空);}int pop this.elem[usedSize - 1];usedSize–;return pop;}/** 获取栈顶元素* return/public int peek() {if(empty()) {System.out.println(栈为空);return 0;}int peek this.elem[usedSize - 1];return peek;}/** 栈是否为空* return/public boolean empty() {return usedSize 0;} } 栈的应用场景 1. 改变元素的序列 我们去牛客上找两道题做做  根据我们上面介绍栈 遵循 先进后出原则 我们可以得出答案不可能的出栈顺序是 D 选项 因为FE出来了下一个出来的必须是 D这种情况下C不可能比D先出。  2. 将递归转化为循环   比如逆序打印链表  1.递归方法  2.循环方法  运行结果  补充
   用数组实现栈出栈入栈都是O(1), 那用链表如何实现栈呢 1.假设用单链表单向实现栈  尾插        入栈尾插法 入栈是 O(n)       出栈因为栈后进的先出这就相当于删除链表的尾巴节点时间复杂度还是O(n);  头插        入栈头插法 O(1)       出栈相等于删除头节点时间复杂度O(1) 2.假设用双向链表实现栈  前后都能找到 尾插        入栈尾插法 入栈是 O(1)       出栈时间复杂度还是O(1)  头插        入栈头插法 O(1)       出栈时间复杂度O(1) 上述我们可知用链表实现栈时双向链表实现栈是最好的不管从那边入栈出栈 时间复杂度都是O(1)。 那使用链式栈时就可以这样使用如果这是个栈那peek的内容就是 4.  是 4.  那为啥会这样你看LinkedList,里本来就有栈里的一些方法push…..  push 用的是头插法  所以如果是顺序栈你可以用Stack, 如果是链式栈你就用LinkedList  队列Queue  什么是队列 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头 举例说明  假如有一条单行隧道车辆必须从入口进 入队列从出口出出队列。那先驶出隧道的车辆肯定是先进去的后驶出的肯定是后进去的这就是 队列的先进先出原则 通过上述介绍我们发现我们可以把 双向链表当成是一个 队列 (单链表也行双链表更简单) 队尾进队头出时间复杂度O(1) ps:Queue 普通队列Deque 双端队列两边都可以进出LinkedList 可以当作普通队列双端队列链表栈究极打工人 队列的方法  在Java中Queue是个接口底层是通过链表实现的。  队列方法少的嘞  offer (入队列)  peek  poll  ………  addremove element (和peek一个意思是一组  offer,  poll,  peek 是一组 队列模拟实现  队列的实现使用 顺序结构 和 链式结构 都行但链式结构更简单一点。 我们这里拿双链表去写 (前面的链表学会了这里很简单的信手拈来 初始化  offer  调试一看 插进去了  poll peek 完整代码链式队列  /** Author: iiiiiihuang/ public class MyQueue {static class ListNode {private int val;private ListNode prev;private ListNode next;public ListNode(int val) {this.val val;}}private ListNode front;//头private ListNode rear;//尾private int usedSize;//计数/** 插入— 头插法* param val/public void offer(int val) {ListNode node new ListNode(val);if(front null) {front node;rear node;} else {node.next front;front.prev node;node front;}usedSize;}/** 删除 – 尾删* return/public int poll() {if(front null) {throw new EmptyException(队列为空);}if(front rear) {int poll front.val;front null;rear null;usedSize–;return poll;}int poll rear.val;rear rear.prev;rear.next null;usedSize–;return poll;}/** 获取队头* return/public int peek() {if(front null) {throw new EmptyException(队列为空);}return rear.val;} } 循环队列   实际中我们有时还会使用一种队列叫循环队列。 环形队列通常使用数组实现。  认识循环队列  。。。。。  这就有意思了  front 和 rear 第一次在一起的时候 队列 是空的第二次 在一起的时候是队列是满的 那这怎么判断呢其实有很多方法去判断 1.计数  usedSize len  2.标记flag  3.浪费一个空间来区分常用  浪费一个空间就类似下面这样 如何把数组看作是一个循环呢rear 从 7 – 0)  就是把 rear   换成 rear 1 % len  余数肯定都是小于 len的len 数组长度rear 会越界的 (看不懂自己带数据算算) 设计一个循环队列 https://leetcode.cn/problems/design-circular-queue/ 根据这个来  初始化  判断队列是否是空的和是否是满的  入队  出队 得到队头元素 得到队尾元素 不能直接rear - 1哦 那现在我们放到力扣里运行一下链接在上边 错了 为什么我们看看我什么 数组容量是 3 预期结果成功 插入了 3个而我们的程序只能插入两个因为我们的浪费掉了一个空间 。 所以我们应该多给一个空间  在运行一下 通过了当然你要是觉得这样奇怪你也可以用 usedSize,很多方法啦 完整代码 循环队列 class MyCircularQueue {private int[] elem;private int front;//头private int rear;//尾public MyCircularQueue(int k) {this.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;}int ret elem[front];return ret;}public int Rear() {if(isEmpty()) {return -1;}int index (rear 0) ? elem.length - 1 : rear - 1;//不能直接rear - 1哦return elem[index];}public boolean isEmpty() {return front rear;}public boolean isFull() {if((rear 1) % this.elem.length front) {return true;}return false;} } 双端队列 (Deque)   双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double   ended queue” 的简称。 那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 Deque是一个接口使用时必须创建LinkedList的对象 。 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口 1. DequeInteger stack new ArrayDeque();//双端队列的线性实现数组 2. DequeInteger queue new LinkedList();//双端队列的链式实现  面试题 1. 用队列实现栈   2. 用栈实现队列 1. 用队列实现栈 225. 用队列实现栈 - 力扣LeetCode  1.首先一个栈是不够用的它俩的出栈原则不一样栈先进后出队列先进先出一个队列实现不了呀 对不上。 2.所以我们需要两个队列当 2 个队列都为空的时候说明模拟栈为空。 3.当要出栈的时候出 45 我们要把 122334入到第二个队列里去然后再把第一个队列里的 45 出队列
   结论就是”出栈“的时候出不为空的 队列出队列size - 1 个俩队列轮流最后那一个就是我们要 ”出栈“的元素 4.“入栈” 的时候入到不为空的队列 思路有了我们开始写代码 代码实现 入栈 出栈  用for 循环的时候注意一下不要写成 i queue.size() - 1,因为queue.size()一直在变。你先记录一下 获取栈顶元素  我们可以定义一个临时量来存放栈顶元素 里面的元素一直被覆盖那最后出队列的元素就覆盖了之前的全部元素就是栈顶元素。  注意这里可别写成 queue1.offer(queue2.poll), 跳两回啦。 判断栈空 完美通过  完整代码  import java.util.LinkedList; import java.util.Queue;/** Author: iiiiiihuang/ public class MyStack {private QueueInteger queue1;private QueueInteger queue2;public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}/** 入栈操作* param x/public void push(int x) {if(!queue1.isEmpty()){queue1.offer(x);} else if(!queue2.isEmpty()) {queue2.offer(x);}else {queue1.offer(x);}}/** 出栈* return/public int pop() {//先判断栈空不空if(empty()) {return -1;}if(!queue1.isEmpty()) {int len queue1.size() - 1;while (len 0) {int tmp queue1.poll();queue2.offer(tmp);len–;}return queue1.poll();} else {int len queue2.size() - 1;while (len 0) {int tmp queue2.poll();queue1.offer(tmp);len–;}return queue2.poll();}}/** 获取栈顶元素* return/public int top() {int tmp -1;if(empty()) {return -1;}if(!queue1.isEmpty()) {int len queue1.size();while (len 0) {tmp queue1.poll();queue2.offer(tmp);len–;}return tmp;} else {int len queue2.size();while (len 0) {tmp queue2.poll();queue1.offer(tmp);len–;}return tmp;}}public boolean empty() {return queue1.isEmpty() queue2.isEmpty();} } 2. 用栈实现队列  232. 用栈实现队列 - 力扣LeetCode 思路差不多  1.两个栈实现同理  2.入队的时候 把所有元素 全部放到第一个栈当中 3.出队的时候 把所有的元素 全部倒到第二个栈当中然后出第二个栈顶元素就行了.记得判空 我直接上代码了  import java.util.Stack;/** Author: iiiiiihuang/ public class MyQueue {private StackInteger stack1;private StackInteger stack2;public MyQueue() {stack1 new Stack();stack2 new Stack();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if(stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()) {return -1;}if(stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() stack2.isEmpty();} }先别急着走点个关注先 点赞评论收藏支持一下ヾ(≧▽≦)oヾ(≧▽≦*)o