本文共 5007 字,大约阅读时间需要 16 分钟。
算法的系列文章中,之前咱们已经聊过了「 数组和链表 」、「 堆栈 」,今天咱们再来继续看看「 队列 」这种数据结构。「 队列 」和「 堆栈 」比较类似,都属于线性表数据结构,并且都在操作上受到一定规则约束,都是非常常用的数据类型,咱们掌握得再熟练也不为过。
一、「 队列 」是什么?
队列(queue)是一种先进先出的、操作受限的线性表。
队列这种数据结构非常容易理解,就像我们平时去超市买东西,在收银台结账的时候需要排队,先去排队的就先结账出去,排在后面的就后结账,有其他人再要过来结账,必须排在队尾不能在队中间插队。
「 队列 」数据结构就是这样的,先进入队列的先出去,后进入队列的后出去。必须从队尾插入新元素,队列中的元素只能从队首出,这也就是「 队列 」操作受限制的地方了。
与堆栈类似,队列既可以用 「 数组 」 来实现,也可以用 「 链表 」 来实现。
下面主要介绍一下目前用的比较多的几种「 队列 」类型:
下面来依次了解一下:
当队列装满的时候,则是如下情况:
当需要做出队操作时,首先要判断队列是否为空,如果front指针和rear指针指向同一个位置(即front==rear)则说明队列是空的,无法做出队操作。如果队列不为空,则可以进行出队操作,将front指针所指向的元素出队,然后front指针递增加一(即向后移动了一位),加入上图的队列出队了2个元素:
所以对于数组实现的队列而言,需要用2个指针来控制(front和rear),并且无论是做入队操作还是出队操作,front或rear都是往后移动,并不会往前移动。入队的时候是rear往后移动,出队的时候是front往后移动。出队和入队的时间复杂度都是O(1)的。
当进行入队操作时,让新节点的Next指向rear的Next,再让rear的Next指向新节点,最后让rear指针向后移动一位(即rear指针指向新节点),如上图右边部分。
当然可以在数组尾部已满的这种情况下,去移动数据,把数据所有的元素都往前移动以填满前面的空间,释放出尾部的空间,以便尾部还可以继续插入新元素。但是这个移动也是消耗时间复杂度的。
循环队列也是一种线性数据结构,只不过它的最后一个位置并不是结束位。对于循环队列,头指针front始终指向队列的前面,尾指针rear始终指向队列的末尾。在最初阶段,头部和尾部的指针都是指向的相同的位置,此时队列是空的,如图:
当有新元素要插入到这个循环队列的时候(入队),新元素就会被添加到队尾指针rear指向的位置(rear和tail这两个英文单词都是表示队尾指针的,不同人喜欢的叫法不一样),并且队尾指针就会递增加一,指向下一个位置,如图:
当需要做出队操作时,直接将头部指针front指向的元素进行出队(我们常用 front 或 head 英文单词来表示头部指针,凭个人喜好),并且头部指针递增加一,指向下一个位置,如图:
上图中,D1元素被出队列了,头指针head也指向了D2,不过D1元素的实际数据并没有被删除,但即使没有删除,D1元素也不属于队列中的一部分了,队列只承认队头和队尾之间的数据,其它数据并不属于队列的一部分。
tail的下标就有重新变成了0,此时队列已经真的满了。
此时,头指针的下标已经大于尾指针的下标了,这也是正式循环队列的特性导致的。
二、「 队列 」的算法实践?
我们看看经常涉及到 队列 的 算法题(来源leetcode):
算法题1:使用栈实现队列的下列操作: push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。解题思路:堆栈是FILO先进后出,队列是FIFO先进先出,要使用堆栈来实现队列的功能,可以采用2个堆栈的方式。堆栈A和堆栈B,当有元素要插入的时候,就往堆栈A里插入。当要移除元素的时候,先将堆栈A里的元素依次出栈放入到堆栈B中,再从堆栈B的顶部出数据。如此便基于2个堆栈实现了先进先出的原则了。class MyQueue { private Stacks1 = new Stack<>(); private Stack s2 = new Stack<>(); private int fornt; /** Initialize your data structure here. */ public MyQueue() { } /** Push element x to the back of queue. */ public void push(int x) { if(s1.empty()) fornt = x; s1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { if(s2.empty()){ while(!s1.empty()){ s2.push(s1.pop()); } } return s2.pop(); } /** Get the front element. */ public int peek() { if(s2.empty()){ return fornt; } return s2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return s1.empty()&&s2.empty(); }} 入栈的时间复杂度为O(1),出栈的时间复杂度为O(1)算法题2:使用队列来实现堆栈的下列操作: push(x) -- 元素 x 入栈 pop() -- 移除栈顶元素 top() -- 获取栈顶元素 empty() -- 返回栈是否为空解题思路:由于需要使用FIFO的队列模拟出FILO的堆栈效果,因此需要使用2个队列来完成,队列A和队列B,当需要进行入栈操作的时候,直接往队列A中插入元素。当需要进行出栈操作的时候,先将队列A中的前n-1个元素依次出队移动到队列B中,这样队列A中剩下的最后一个元素其实就是我们所需要出栈的元素了,将这个元素出队即可。class MyStack { private Queue q1 = new LinkedList<>(); private Queue q2 = new LinkedList<>(); int front; /** Initialize your data structure here. */ public MyStack() { } /** Push element x onto stack. */ public void push(int x) { q1.add(x); front = x; } /** Removes the element on top of the stack and returns that element. */ public int pop() { while(q1.size()>1){ front = q1.remove(); q2.add(front); } int val = q1.remove(); Queue temp = q2; q2 = q1; q1 = temp; return val; } /** Get the top element. */ public int top() { return front; } /** Returns whether the stack is empty. */ public boolean empty() { return q1.size()==0; }}入栈的时间复杂度为O(1),出栈的时间复杂度为O(n)这道题其实还有另一个解法,只需要一个队列就可以做到模拟出堆栈,思路就是:当需要进行入栈操作的时候,先将新元素插入到队列的队尾中,再将这个队列中的其它元素依次出队,队列的特性当然是从队头出队了,但是出来的元素再让它们从队尾入队,这样依次进行,留下刚才插入的新元素不动,这个时候,这个新元素其实就被顶到了队头了,新元素入栈的动作就完成了。当需要进行出栈操作的时候,就直接将队列队头元素出队即是了。思路已经写出来了,代码的话就留给大家练习了哦。
以上,就是对数据结构「 队列 」的一些思考。
免费分享Java技术资料,需要的关注我后私信我即可
转载地址:http://tuusi.baihongyu.com/