赞
踩
队列是一个特殊的线性表,只允许在一端(队尾)进行插入数据操作,在另一端(对头)进行删除数据。队列具有先进先出FIFO(First In First Out)的特性。
入队:数据只能从队尾进队列 出队:数据只能从对头出队列
即:队尾进队头出
我们可以把队列想象为一个排队的队伍,从队尾开始排队,排到了再从队头出队:
实现队列,我们可以使用单链表、双向链表、数组来实现。
接下来我们来聊一聊如何设计循环队列。
循环队列又叫做环形队列,通常是由数组实现的。
我们定义front和rear分别指向队头和队尾,rear的位置就是入队元素要插入的位置,起始时front和rear都在0下标处。
循环队列就是将数组的两端相连接,这样即使有元素出队,出队元素的位置,rear指针也可以达到,能够让新元素入队,减少空间的浪费。
当在rear为7下标时,进行入队操作后(假设队列不为满),rear要来到0下标的位置,那么要进行的操作是:rear == (rear+1)% len
于是更新rear的操作为:rear == (rear+1)% len
如果基于以上的设计,那么循环队列为空和队列为满时的条件均为:rear == front
那么对于循环队列,该如何进行判空和判满呢?我们给出改善设计:
判空:rear == front
判满(三种方法):
我们通过一道OJ题来设计循环队列。(使用浪费一个空间的方法来判满)
代码:
- class MyCircularQueue {
- public int front;
- public int rear;
- public int[] elem;
-
- public MyCircularQueue(int k) {
- //题目要求我们k个位置均能存储数据
- //因为我们使用浪费一个空间的方法来判满,所以我们这里要开辟k+1个空间
- elem = new int[k + 1];
- }
-
- public boolean enQueue(int value) {
- if(isFull()) {
- //不满时才能入队
- return false;
- }
- //在rear位置插入数据,并更新rear
- elem[rear] = value;
- rear = (rear+1) % elem.length;
- return true;
- }
-
- public boolean deQueue() {
- if(isEmpty()) {
- //不空时才能出队
- return false;
- }
- //直接更新front即可,新数据入队会覆盖
- front = (front+1) % elem.length;
- return true;
- }
-
- public int Front() {
- if(isEmpty()) {
- return -1;
- }
- //front指向的位置就是队头元素
- return elem[front];
- }
-
- public int Rear() {
- if(isEmpty()) {
- return -1;
- }
- //当rear == 0时,需要做特殊处理
- //其余rear-1下标就是队尾元素的位置
- int index = rear == 0 ? elem.length - 1 : rear - 1;
- return elem[index];
- }
-
- public boolean isEmpty() {
- return rear == front;
- }
-
- public boolean isFull() {
- return (rear+1) % elem.length == front;
- }
- }
在Java中,Queue是一个接口,底层是用链表来实现的:
注意:Queue是一个接口,在实例化时必须实例化实现Queue接口的类的对象。
双端队列,元素可以在队头和队尾任意插入和删除元素,也就是说,元素可以从队头出队和入队,也可以从队尾出队和入队。
Java给出的双端队列Deque也是一个接口(Queue的扩展接口),在实例化时必须实例化实现Deque接口的类的对象。
在Java中,有多个类实现了Queue和Deque,这里我们只谈LinkedList和ArrayDeque。
我们可以使用LinkedList来实现队列和双端队列,为链式实现,底层为链表。
也可以使用ArrayDeque来实现队列和双端队列,为顺序实现,底层为数组。
同时,LinkedList和ArrayDeque中也实现了集合类Stack中的方法(Deque接口中包含了Stack的方法,而LinkedList和ArrayDeque实现了Deque接口),所以我们也可以使用LinkedList和ArrayDeque来实现栈。
注意:只有Deque接口中包含了Stack的方法,Queue接口没有包含。
也就是说,我们以后如果要构建栈、队列、双端队列...都可以通过LinkedList和ArrayDeque来实现,其方法更加丰富。
我们需要两个队列来模拟实现栈。
入栈:把数据放到不为空的队列当中,如果两个队列都为空,则随机放入即可。
出栈:两个队列必有一个为空,将不为空的队列中的size-1个元素移到空队列中,剩下的1个元素就是要模拟“出栈”的元素。
取栈顶元素:两个队列必有一个为空,将不为空的队列中的全部元素移到空队列中,并使用变量记录每次进新队列元素的数值,最后一次进队的元素就是“栈顶”元素。
- class MyStack {
- Queue<Integer> qu1;
- Queue<Integer> qu2;
-
- public MyStack() {
- qu1 = new LinkedList<>();
- qu2 = new LinkedList<>();
- }
-
- //模拟入栈:把元素放到不为空的队列中
- public void push(int x) {
- if (empty()) {
- //两个队列都为空时 默认放到qu1中
- qu1.offer(x);
- } else if (qu1.isEmpty()) {
- qu2.offer(x);
- }else {
- qu1.offer(x);
- }
- }
-
- //将有元素的队列中的size-1个元素导入进空队列中
- //剩下的1个元素,就是要出栈的元素
- public int pop() {
- if (qu1.isEmpty()) {
- while (qu2.size() != 1) {
- int x = qu2.poll();
- qu1.offer(x);
- }
- return qu2.poll();
- }else {
- while (qu1.size() != 1) {
- int x = qu1.poll();
- qu2.offer(x);
- }
- return qu1.poll();
- }
- }
-
- //将有元素的队列中的全部元素导入进空队列中
- //并用变量记录每一次导进的元素,最后一次导入的元素就是栈顶元素
- public int top() {
- int x = 0;
- if (qu1.isEmpty()) {
- while (!qu2.isEmpty()) {
- x = qu2.poll();
- qu1.offer(x);
- }
- return x;
- }else {
- while (!qu1.isEmpty()) {
- x = qu1.poll();
- qu2.offer(x);
- }
- return x;
- }
- }
-
- //当两个队列都为空时,说明栈为空
- public boolean empty() {
- return qu1.isEmpty() && qu2.isEmpty();
- }
- }
模拟入队操作:“入队”的元素全部放入第一个栈中
模拟出队操作:
需要先判断第2个栈为不为空,
1.如果未空,需要把第一个栈当中的所有元素都放到第二个栈中,弹出第二个栈当中的栈顶元素
2.如果不为空,直接弹出第二个栈当中的栈顶元素
也就是说第二个栈的栈顶元素,其实就是我们所模拟队列的队头元素。
- class MyQueue {
-
- ArrayDeque<Integer> stack1;//"入队"的元素统一放到stack1中
- ArrayDeque<Integer> stack2;//统一在stack2中出队
-
- public MyQueue() {
- stack1 = new ArrayDeque<>();
- stack2 = new ArrayDeque<>();
- }
-
- public void push(int x) {
- stack1.push(x);//"入队"的元素统一放到stack1中
- }
-
- public int pop() {
- if (stack2.isEmpty()) {
- //若stack2为空,则将stack1中的元素导入stack2中,
- // stack2的栈顶元素即为模拟出队的“队头”元素
- while (!stack1.isEmpty()) {
- int x = stack1.pop();
- stack2.push(x);
- }
- return stack2.pop();
- }else {
- //若stack2不为空,其栈顶元素即为模拟出队的“队头”元素
- return stack2.pop();
- }
- }
-
- public int peek() {
- if (stack2.isEmpty()) {
- while (!stack1.isEmpty()) {
- int x = stack1.pop();
- stack2.push(x);
- }
- return stack2.peek();
- }else {
- return stack2.peek();
- }
- }
-
- public boolean empty() {
- //当stack1和stack2均为空时,说明模拟的队列为空
- return stack1.isEmpty() && stack2.isEmpty();
- }
- }
OK~本次博客到这里就结束了,
感谢大家的阅读~欢迎大家在评论区交流问题~
如果博客出现错误可以提在评论区~
创作不易,请大家多多支持~
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。