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

数据结构5.0

news 2025/5/10 11:55:05

大家好，今天是队列的知识哦~

一、概念

1.0单链表

2.0双链表

3.0数组

二、队列的方法

1.0 offer方法

2.0 poll方法

3.0 peek方法

4.0 isEmpty方法

三、队列的题目

1.0 用队列实现栈

2.0 用栈实现队列

3.0 设计循环队列

一、概念

数组、单链表和双链表都可以实现队列

1.0单链表

入栈操作：单链表是头插时间复杂度O（1）出栈操作：单链表是删除头节点

这样实现了队列先进先出的特点

2.0双链表

头插尾删可以实现队列

尾插头删也可以实现队列

只要保证特性满足队列的特性即可

源码里面是尾插头删

3.0数组

队尾入队头出如果放到数组里面很难搞队尾已经到了数组长度的极限了，队头删了还有空间

我们会发现如果把数组前面当作队头数组最后当作队尾

当队尾一直遍历到数组末尾不能加数据了但是随着队头出数组还是有空间的呀

如果把数组卷起来头尾相连得到一个循环数组这样就能更大化的利用空间了

这里我们的rear补药rear++

用下面这个公式可以是rear循环走：rear=(rear+1)%len front也一样不会越界

有关这个部分的内容放到下面的题目里面了 622. 设计循环队列 - 力扣（LeetCode）

二、队列的方法

Queue是个接口，底层是通过链表实现的

方法预览：

1.0 offer方法

入队列我们用的是双链表源码里面的offer是用的头插法

所以逻辑和我们双链表的头插几乎一样

这个usedSize 可以搞一个

代码这里是尾插

下面是代码：

public void offer (int e){
ListNode newNode = new ListNode(e);
if(front ==null){front = rear = node;}else{last.next = node;node.prev = last;last = node;}uesdSize++;
}

2.0 poll方法

同理类似双链表的删除头节点的方法

下面是代码：

 public int poll(){if(front == null){return -1;}int ret = front.val;;if(front == rear){front = null;rear = null;usedSize--;}front = front.next;front.prev= null;usedSize--;return ret;}

3.0 peek方法

获取队头元素也就是获取双链表头结点元素

要注意分情况讨论

public int peek(){if(front == null){return -1;}return front.val;}

4.0 isEmpty方法

public boolean isEmpty(){return usedSize == 0;
}

三、队列的题目

1.0 用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

思路分析：

如何用队列实现栈呢？如何用队列让先进的后出

方法有很多种这里我们讲解一个方法用交换法

两个队列队列1和队列2 存入的时候都存到queue1里面

要实现pop方法和top方法的时候明确我们要删除的是后进的那个元素

我们将队列1添加的元素出队到队列2 剩下最后一个元素（这个元素就是后进的那个）

用popped记录下后删除然后交换队列把那些在队列2的元素交换回来

top方法的大体思路同样如此哦这里就不再赘述了多犯错误多调试比较快

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue1.offer(x);}public int pop() {while(queue1.size()>1){queue2.offer(queue1.poll());}int popped=queue1.poll();Queue<Integer> temp = queue1;queue1=queue2;queue2=temp;return popped;}// while(queue1.isEmpty()){// queue2.offer(queue1.getLast());// }// queue2.poll();public int top() {// return queue2.peek();while(queue1.size()>1) {queue2.offer(queue1.poll());}int top = queue1.peek();queue2.offer(queue1.poll());Queue<Integer> temp = queue1;queue1=queue2;queue2=temp;return top;}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}}

2.0 用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

思路分析：

要达到的目标是用栈模拟实现队列先进先出的结构

栈的结构是先进后出

我们可以用两个栈一个用来push 一个用来pop和peek

我们要实现先进先出把栈1里面的元素push到栈2里面

此时栈2的栈顶元素就是先进的元素然后用栈2的pop方法peek方法就可以达到目的

要注意的点是：判断栈2是否为空

有时候栈2的元素还没有pop完呢栈1里面又加入新的元素了

这个时候我们pop也是从栈2里面出毕竟栈2的元素比栈1早进

然后直到栈2为空了我们想要pop了再把栈1的元素push到栈2pop

所以pop方法和peek方法要先判断栈2是否为空

下面是代码：

class MyQueue {private Stack<Integer>  stack1;private Stack<Integer> stack2;public MyQueue() {stack1= new Stack<>();stack2= new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()){return -1;}// 为什么要判断 stack是否为空呢 难道还能中途//确保stack1 的元素只会在stack为空时倒入    //如果stack1里面有元素 stack2里面也有元素 stack里面的早 所以弹stack2//stack2为空了再倒入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();}
}

3.0 设计循环队列

622. 设计循环队列 - 力扣（LeetCode）

我们定义了一个数组之后开始往里面放元素呀

rear和front都在数组0下标放入一个元素队头front不变队尾rear往后面加

这样直到数组满了对应上面图片第一张此时rear从7下标到了0小标这个时候的处理方法有三种

第一种是定义usedSize来记录 uedSize和len的比较

第二种是可以使用标记定义一个flag类型的变量相遇的时候flag定义为false或者true

第三种是浪费一个空间来区分我们重点讲解这个内容

如果rear的下一个就是front 证明就是满的

rear如何实现循环着走数组呢？

rear=（rear+1）%len; 这个公式满足了rear在数组里面循环不会出现数组越界异常

最后 front也得因为删除队列元素而在数组里面循环当然这个是后话

下面开始各种方法的讲解：

（1）判断满空的方法：为什么是rear=front呢因为这里的rear和front因为数组是循环的

它们的位置不是固定的在开头

（2）判断满：用到rear的循环走公式碰到了front

就是要判断 (rear+1)%elem.length == front;

（3）构造器为什么要k+1 呢因为我们用的方法是浪费一个空间所以创建的时候就多一个

这样就能有k个位置存放元素了

（4）入队 enQueue：入队的时候我们首先要判断满了没有 rear位置放上元素和rear位置的更新

要注意的地方是：我们不能使用rear++ 代码里面用哪个公式是为了实现rear的循环

（5）出队 deQueue : 出队我们首先要判断是不是空呢注意出队的时候直接更新front节点就可以

要注意的地方是：front 也得循环着走所以也用到了那个公式

（6）从队首获得元素：这里的注意点是还是要提前判断循环队列是不是空的呢

（7）从队尾获得元素：这个要注意的是分类讨论根据情况

如果rear的下标不是0 那么返回的是rear前面的元素 rear-1 前面我们也讲过 rear指向下一个

可插入的位置

如果rear的下标是0 那么返回的是数组长度下标减一这个特殊情况在图片上面有所呈现

下面是代码：

class MyCircularQueue {int rear ;//队尾下表int front ;//队头下标int elem[] ;public MyCircularQueue(int k) {//构造器 设置队列的长度为kthis.elem= new int[k+1];// rear= (rear+1)%elem.length;}public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear]=value;//rear++;  这样容易越界rear= (rear+1)%elem.length;return true;}public boolean deQueue() {//出 front往后面走就可以了// 空的 不能出if(isEmpty()){return false;}//不空 front往后走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];}public boolean isEmpty() {return front == rear;}public boolean isFull() {if((rear+1)%elem.length == front){return true;}return false;}
}

以上就是队列的知识咯~ 遍历一个节点

感谢大家的支持