网站建设费用说明,北京电力建设公司待遇,门户网站开发建设技术,跨境电商开发公司特点 只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出 FIFO(First In First Out) 入队列#xff1a;进行插入操作的一端称为 队尾#xff08; Tail/Rear #xff09; 出队列#xff1a;进行删除操作的一端称…特点 只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出 FIFO(First In First Out) 入队列进行插入操作的一端称为 队尾 Tail/Rear 出队列进行删除操作的一端称为 队头 手搓一个队列 链式队列 开始动手
队列属于插入元素后需要从头部来删除我们可以用双链表来模拟它
尾巴进头部出
接下来整个的过程跟双链表差不多大家可以参考我之前一篇博客
链表3双链表_cx努力编程中的博客-CSDN博客 初始化 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;public int usedSize;
offer
尾插法 public boolean offer(int val){ListNode node new ListNode(val);if(head null){head node;last node;}else{last.next node;node.prev last;last last.next;}usedSize;return true;}
poll public int poll(){//没有节点if(head null){return -1;}int retVal head.val;//只有一个节点if(head.next null){head null;last null;return retVal;}//两个及以上的节点head head.next;head.prev null;usedSize--;return retVal;}
peek public int peek(){if(head null){return -1;}return head.val;}
empty和size public boolean empty(){return head null;}public int size(){return usedSize;} 数组队列
622. 设计循环队列 - 力扣LeetCode
简单介绍一下
假设有一个容量为5的数组要操作12 23 34 45 56 67 78 7个数字 队头front队尾rear先放在0位置分别往后遍历
每次加入一个元素rear就每次弹出一个元素front就 但是这会出现一个问题
当我们加到56这个元素之后rear跑到数组外面去了越界了
极限一点当我们把当前队列的元素全部poll之后front也跑到数组外面去了
其实队列弹出元素后前面的必然会是空的我们可以让rear走到前面来
整个队列弹空了之后也把front移到前面的空格处
如图我们依次往队列加45 56 12 23 34此时rear走到数组末端我们把45弹出rear就可以重新回到数组头 这么一看整个数组队列就是一个循环一个圈 我们依次加入元素每次加入rear就往后走 rear走了一圈又和front相遇了此时问题来了
1. 队列此时是空的还是满的
1使用usedSize来记录放入一个元素usedSize
2浪费一个空间来表示满
相当于你要过河总得扔个石头试试深浅的道理一样在front前面开辟一块空间什么元素都不放当rear走到这块空间时判断一下rear下一个元素位置是不是front是的话就证明队列满了
3使用标记
第一次相遇起始位置标记一下第二次相遇的时候就证明它满了
2. rear怎么从7下标来到0下标
公式rear (rear 1) % len
front (front 1) % len public boolean isEmpty() {return front rear;}public boolean isFull() {return (rear1) % elem.length front;}
入队和出队 public MyCircularQueue(int k) {elem new int[k];}//入队public boolean enQueue(int value) {if(isFull()){return false;}elem[rear] value;rear (rear1) % 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;}int index (rear 0) ? elem.length - 1:rear-1;return elem[index];}
得到队尾元素的部分要注意一下不能直接rear-1因为如果rear0的时候rear-1-1是不合法的 你以为结束了吗当我们把这段代码放入到力扣里面我们发现报错了报错结果 在执行3的入队操作时预期的是true而我们输出了false
当我们空间为3的时候确实只能存2个元素因为存第3个元素空间会被浪费
那我们可以投机地改一下代码 或者使用usedSize就没有浪费空间这么一说了
代码具体就是定义完usedSizeenQueue就usedSizedeQueue就usedSize-- 双端队列
指的是在队列两边都可以进行入队和出队的操作 链式队列就能实现这个功能 那数组队列也可以实现吗 ArrayDeque的底层也是有这些头插尾插方法的 这两个不仅仅可以当作队列也可以当作栈。这两个当作栈的情况比较多 队列题目
225. 用队列实现栈 - 力扣LeetCode
请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。
实现 MyStack 类
void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。
我们知道队列和栈的出栈顺序本来就是矛盾的所以一个队列实现不了栈但是两个队列可以啊
假设我们要操作12 23 34 45这四个数把前3个数加入后栈要弹出元素就是34第一个出 观察到qu2队列是空的那qu1就把12和23分别弹出来扔到qu2里面存储起来qu1再把34弹出这样就实现了栈弹出34的操作
解题步骤
1.入栈哪个队列不为空就放到哪个队列里面两个都为空就扔到qu1里面
2.出栈哪个队列不为空就出size-1个元素并扔到空队列里面
3.当两个队列都为空的时候栈就是空的
整个代码
class MyStack {private QueueInteger qu1;private QueueInteger qu2;public MyStack() {qu1 new LinkedList();qu2 new LinkedList();}public void push(int x) {if(!qu1.isEmpty()){qu1.offer(x);}else if(!qu2.isEmpty()){qu2.offer(x);}else{//两个队列都是空的指定放到qu1里面qu1.offer(x);}}public int pop() {if(empty()){return -1;}if(!qu1.isEmpty()){int size1 qu1.size();//让一个size1记录qu1的大小防止循环的时候循环条件里的size没有变化for (int i 0; i size1-1; i) {int x qu1.poll();qu2.offer(x);}return qu1.poll();}else{int size2 qu2.size();for (int i 0; i size2-1; i) {int x qu2.poll();qu1.offer(x);}return qu2.poll();}}public int top() {if(empty()){return -1;}if(!qu1.isEmpty()){int size1 qu1.size();int x -1;for (int i 0; i size1; i) {x qu1.poll();qu2.offer(x);}return x;}else{int x -1;int size2 qu2.size();for (int i 0; i size2; i) {x qu2.poll();qu1.offer(x);}return x;}}public boolean empty() {return qu1.isEmpty() qu2.isEmpty();}
} 232. 用栈实现队列 - 力扣LeetCode
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作push、pop、peek、empty
实现 MyQueue 类
void push(int x) 将元素 x 推到队列的末尾int pop() 从队列的开头移除并返回元素int peek() 返回队列开头的元素boolean empty() 如果队列为空返回 true 否则返回 false
和上面那道题同理一个栈实现不了队列所以我们要用两个栈
1.入队的时候放到s1里面
2.出队的时候都出s2当中的元素当s2没有元素的时候把s1里面的元素全部倒过来
整个的代码
class MyQueue {private StackInteger s1;private StackInteger s2;public MyQueue() {s1 new Stack();s2 new Stack();}public void push(int x) {s1.push(x);}public int pop() {if(empty()){return -1;}if(s2.empty()){while(!s1.empty()){s2.push(s1.pop());}}return s2.pop();}public int peek() {if(empty()){return -1;}if(s2.empty()){while(!s1.empty()){s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.empty() s2.empty();}
}
