做全国家电维修网站到哪里做,网站seo服务商,备案 几个网站,给网站增加功能怎么做Hi~#xff01;这里是奋斗的明志#xff0c;很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~~ #x1f331;#x1f331;个人主页#xff1a;奋斗的明志 #x1f331;#x1f331;所属专栏#xff1a;数据结构 #x1f4da;本系列文章为个人学… Hi~这里是奋斗的明志很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~~ 个人主页奋斗的明志 所属专栏数据结构 本系列文章为个人学习笔记在这里撰写成文一为巩固知识二为展示我的学习过程及理解。文笔、排版拙劣望见谅。 文章目录 一、队列(Queue)1.概念2.队列的使用 二、队列模拟实现1.用双链表实现队列2.循环队列利用数组设计2.1循环队列图解2.2代码展示 三、双端队列 (Deque)四、用队列实现栈面试题1.题目2.解析3.代码展示 五、用栈实现队列面试题1.题目2.解析3.代码展示 总结 一、队列(Queue) 1.概念 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头 Head/Front 2.队列的使用 在Java中 Queue是个接口底层是通过链表实现的。
方法功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中有效元素个数boolean isEmpty()检测队列是否为空 代码如下示例 public static void main(String[] args) {QueueInteger q new LinkedList();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); //从队尾入队列 System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列 并将删除的元素返回if (q.isEmpty()) {System.out.println(队列空);} else {System.out.println(q.size());}
} 二、队列模拟实现 队列中既然可以存储元素那底层肯定要有能够保存元素的空间通过前面线性表的学习了解到常见的空间类型有两种顺序结构 和 链式结构。 思考下 队列的实现使用顺序结构还是链式结构好 1.用双链表实现队列
进队 出队 代码如下示例 package queuedemo;public class MyQueue {//用双链表实现队列//结点类static class ListNode {public int val;public ListNode next;public ListNode prev;//提供构造方法public ListNode(int val) {this.val val;}}public ListNode head;//头结点public ListNode last;//尾结点/*** 1.尾插法* 相当于入队*/public void offer(int val) {ListNode node new ListNode(val);if (head null) {head last node;} else {last.next node;node.prev last;last last.next;}}/*** 2.头删* 相当于出队*/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;head.prev null;return val;}public boolean empty() {return head null;}public int peek(){if (head null){return -1;}return head.val;}
}
2.循环队列利用数组设计 实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。 如何区分空与满
通过添加 size 属性记录保留一个位置使用标记 2.1循环队列图解 2.2代码展示
设计循环队列 package queuedemo;//利用数组设计循环队列
public class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {//构造方法进行数组初始化this.elem new int[k];}/*** 入队操作** param value* return*/public boolean enQueue(int value) {if (isFull()) {return false;}elem[rear] value;//例如 (k - 1 1) % k 0rear (rear 1) % elem.length;return true;}/*** 出队操作** return*/public boolean deQueue() {//先判断空不空if (isEmpty()) {return false;}front (front 1) % elem.length;return true;}/*** 得到队头元素不删除* return*/public int Front() {//先判断空不空if (isEmpty()) {return -1;}return elem[front];}/*** 得到队尾元素不删除* return*/public int Rear() {//先判断空不空if (isEmpty()) {return -1;}int index (rear 0) ? elem.length - 1 : rear - 1;return elem[index];}public boolean isEmpty() {return front rear;}/*** 判断是否满了** return*/public boolean isFull() {return (rear 1) % elem.length front;}
}
三、双端队列 (Deque) 双端队列deque是指允许两端都可以进行入队和出队操作的队列 deque 是“double ended queue” 的简称。 那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 Deque是一个接口使用时必须创建LinkedList的对象。 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口。
DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现四、用队列实现栈面试题
用队列实现栈
1.题目 2.解析 构造方法 MyStack() 初始化两个队列 queue1 和 queue2这两个队列用来辅助实现栈的操作。 压栈操作 push(int x) 如果当前栈为空即两个队列都为空直接将元素 x 放入 queue1。 如果其中一个队列不为空将元素 x 放入非空的队列中保持一个队列为空一个队列非空的状态以便后续操作。 弹出栈顶元素 pop() 首先判断栈是否为空如果为空直接返回 -1。 如果 queue1 非空将 queue1 中除了最后一个元素外的所有元素依次转移到 queue2 中然后弹出 queue1 的最后一个元素作为栈顶元素返回。 如果 queue2 非空类似地操作将 queue2 中除了最后一个元素外的所有元素转移到 queue1 中然后弹出 queue2 的最后一个元素返回。 获取栈顶元素 top() 同样先判断栈是否为空为空则返回 -1。 如果 queue1 非空将 queue1 中的所有元素依次转移到 queue2 中并记录最后一个转移的元素作为栈顶元素返回。 如果 queue2 非空类似地操作将 queue2 中的所有元素依次转移到 queue1 中并记录最后一个转移的元素返回。 判断栈是否为空 empty() 如果 queue1 和 queue2 都为空则栈为空返回 true否则返回 false。
这种使用两个队列来模拟栈的实现方式是经典的算法题目可以有效地实现栈的各种操作。 3.代码展示
class MyStack {//利用队列实现栈//不能使用双端队列public QueueInteger queue1;public QueueInteger queue2;public MyStack() {//在构造方法里面实例化this.queue1 new LinkedList();this.queue2 new LinkedList();}/*** 压栈操作* param x*/public void push(int x) {if (empty()){queue1.offer(x);return;}if (!queue1.isEmpty()){queue1.offer(x);}else {queue2.offer(x);}}/*** 弹出栈顶元素* return*/public int pop() {if (empty()){//说明模拟的栈是空的return -1;}//找到不为空的元素出size - 1 个元素if (!queue1.isEmpty()){int size queue1.size();for (int i 0; i size - 1; i) {queue2.offer(queue1.poll());}return queue1.poll();}else {int size queue2.size();for (int i 0; i size - 1; i) {queue1.offer(queue2.poll());}return queue2.poll();}}public int top() {if (empty()){//说明模拟的栈是空的return -1;}//找到不为空的元素出size - 1 个元素if (!queue1.isEmpty()){int size queue1.size();int tmp -1;for (int i 0; i size; i) {tmp queue1.poll();queue2.offer(tmp);}return tmp;}else {int size queue2.size();int tmp -1;for (int i 0; i size; i) {tmp queue2.poll();queue1.offer(tmp);}return tmp;}}public boolean empty() {return queue1.isEmpty() queue2.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj new MyStack();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.top();* boolean param_4 obj.empty();*/五、用栈实现队列面试题
1.题目
用栈实现队列 2.解析 stack1 和 stack2这两个栈用来实现队列的操作。 stack1 用于存储入队的元素。 stack2 在需要出队或查看队头元素时用来辅助操作。 入队方法 push(int x): 直接将元素 x 压入 stack1 中即将元素添加到队列的末尾。 出队方法 pop(): 首先检查队列是否为空如果为空则返回 -1。 如果 stack2 为空即队列中的元素都在 stack1 中则将 stack1 中的所有元素逐个弹出并压入 stack2然后从 stack2 弹出栈顶元素作为出队元素返回。 如果 stack2 非空则直接从 stack2 弹出栈顶元素作为出队元素返回。 查看队头元素方法 peek(): 首先检查队列是否为空如果为空则返回 -1。 如果 stack2 为空则将 stack1 中的所有元素逐个弹出并压入 stack2然后返回 stack2 的栈顶元素作为队头元素但不移除它。 如果 stack2 非空则直接返回 stack2 的栈顶元素。 判断队列是否为空方法 empty(): 如果 stack1 和 stack2 都为空则队列为空返回 true否则返回 false。
总结 这段代码通过两个栈 stack1 和 stack2 实现了队列的基本功能其中 stack1 用于入队操作而 stack2 在需要出队或查看队头元素时扮演辅助作用。这种实现方式保证了入队操作的时间复杂度为 O(1)出队和查看队头元素的平均时间复杂度为 O(1)空间复杂度为 O(n)其中 n 是队列中的元素个数。 3.代码展示 package queuedemo;import java.util.Stack;public class MyQueue1 {//用栈实现队列//两个栈public StackInteger stack1;public StackInteger stack2;public MyQueue1() {this.stack1 new Stack();this.stack2 new Stack();}/*** 入队列** param x*/public void push(int x) {stack1.push(x);}/*** 出队列** return*/public int pop() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}return stack2.pop();}return stack2.pop();}/*** 队头元素** return*/public int peek() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}return stack2.peek();}return stack2.peek();}public boolean empty() {return stack1.isEmpty() stack2.isEmpty();}
} 总结
数组下标循环的小技巧
下标最后再往后(offset 小于 array.length): index (index offset) % array.length 下标最前再往前(offset 小于 array.length): index (index array.length - offset) % array.length
