开发者社区> IT辰柒_Java> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【数据结构与算法】深入理解队列(下)

简介: 【数据结构与算法】深入理解队列(下)
+关注继续查看

✨hello,进来的小伙伴们,你们好耶!✨

🍅🍅系列专栏:【数据结构与算法】

✈️✈️本篇内容:  循环队列,双端队列以及面试OJ题!

⛵⛵作者简介:一名双非本科大三在读的科班Java编程小白,道阻且长,你我同行!

  一、循环队列

环形队列通常使用数组实现。

60c1b513faf64a5ea6702b7f823d49c7.jpeg

 那么在使用我们的循环队列时,我们可以发现很明显的一个问题就是如何区分空与满,因为刚开始没有存元素的时候我们的head和tail都是在同一位置,随着我们相继向队列中存元素,那么我们的head不动,tail往后走,当tail再次和head相遇的时候,那么问题来了,这个时候队列是满还是空的呢?如何解决?

如何区分空与满

1. 通过添加 size 属性记录

2. 保留一个位置

3. 使用标记

那么今天博主给大家演示就是通过保留一个位置(计数器)来实现循环队列!

一、实现类

   class MyCircularQueue {

       private int front;

       private int rear;

       private int capacity;

       private int[] elements;//通过计数器的方式实现

     

       public MyCircularQueue(int k) {

           capacity = k + 1;

           elements = new int[capacity];

           rear = front = 0;

       }

   }

2、插入一个元素

    public boolean enQueue(int value) {//插入一个元素

           if (isFull()) {

               return false;

           }

           elements[rear] = value;

           rear = (rear + 1) % capacity;

           return true;

       }

3、删除一个元素

       public boolean deQueue() {//删除一个元素

           if (isEmpty()) {

               return false;

           }

           front = (front + 1) % capacity;

           return true;

       }

4、获取队首元素

       public int Front() {//获取队首元素

           if (isEmpty()) {

               return -1;

           }

           return elements[front];

       }

5、获取队尾元素

    public int Rear() {//获取队尾元素

           if (isEmpty()) {

               return -1;

           }

           return elements[(rear - 1 + capacity) % capacity];

       }

6、判断是否为空

       public boolean isEmpty() {

           return rear == front;

       }

7、判断是否满

       public boolean isFull() {

           return ((rear + 1) % capacity) == front;

       }

二、双端队列

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。

7345974a7efe418090c767ca0e912d1c.pngDeque是一个接口,使用时必须创建LinkedList的对象。由于在实际开发中Deque使用的并不是非常多,所以大家只需了解一下即可!

三、面试题

1. 用队列实现栈。

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

实现 MyStack 类:

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

示例:

输入:

["MyStack", "push", "push", "top", "pop", "empty"]

[[], [1], [2], [], [], []]

输出:

[null, null, null, 2, 2, false]

解释:

MyStack myStack = new MyStack();

myStack.push(1);

myStack.push(2);

myStack.top(); // 返回 2

myStack.pop(); // 返回 2

myStack.empty(); // 返回 False

解题思路:

因为栈是后进先出结构,而我们的队列是先进先出结构,我们可以用两个队列来模拟实现栈的结构,qu1用来进栈,当我们需要出栈时,将qu1里面的元素出栈size-1个元素,就能得到我们的栈顶元素,注意,进栈的时候先判断两个队列谁不为空往哪个队列进,只有两个队列都为空的时候我们的栈也为空。

代码实现:

   class MyStack {

     

       private Queue<Integer> qu1;

       private Queue<Integer> 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.offer(x);

           }

       }

     

       

       //出栈

       public int pop() {

           if(empty()) {

               return -1;//

           }

           if(!qu1.isEmpty()) {

               int size = qu1.size();

               for (int i = 0; i < size-1; i++) {

     

                   qu2.offer(qu1.poll());

               }

               return qu1.poll();

           }else {

               int size = qu2.size();

               for (int i = 0; i < size-1; i++) {

     

                   qu1.offer(qu2.poll());

               }

               return qu2.poll();

           }

       }

     

     

       //peek操作

       public int top() {

           if(empty()) {

               return -1;//

           }

           if(!qu1.isEmpty()) {

               int size = qu1.size();

               int ret = -1;

               for (int i = 0; i < size; i++) {

                   ret = qu1.poll();

                   qu2.offer(ret);

               }

               return ret;

           }else {

               int size = qu2.size();

               int ret = -1;

               for (int i = 0; i < size; i++) {

                   ret =  qu2.poll();

                   qu1.offer(ret);

               }

               return ret;

           }

       }

     

     

       //两个队列都为空 那么就是栈为空

       public boolean empty() {

           return qu1.isEmpty() && qu2.isEmpty();

       }

   }

2. 用栈实现队列。

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

实现 MyQueue 类:

void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明:

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

示例 1:

输入:

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

输出:

[null, null, null, 1, 1, false]

解题思路:

1、用两个栈实现队列,先将元素全部入栈到第一个栈s1当中。

2、pop()操作,先判断s1是否为空,如果为空则返回-1,接着判断条件为s2为空,s1不为空,将s1中的元素全部进栈到s2当中,然后return s2.pop()便是出队操作。

3、跟操作2类似,最后返回s2.peek()便可!

代码实现:

   import java.util.*;

     

   class MyQueue {

       private Stack<Integer> s1;

       private Stack<Integer> 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();

       }

   }

🍻好了,那么关于队列的知识点就先讲到这里啦,我们下期见,拜拜!🥞


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构——队列
数据结构——队列
7 0
数据结构——队列
学完栈之后自然是学队列
33 0
数据结构与算法之优先队列
数据结构与算法之优先队列
28 0
数据结构与算法(下)
输入两个整数序列。第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。
76 0
算法模版:模拟数据结构之队列
算法模版:模拟数据结构之队列
39 0
数据结构——队列
1、什么是队列 2、队列的基本结构 3、顺式队列的实现和基本操作 4、循环队列的实现和基本操作 5、链式队列的实现和基本操作
144 0
数据结构——队列
1 队列是一种只允许在表的一端插入元素,在另一端删除元素的特殊的线性表。允许插入的一端成为队尾(rear),允许删除的一端成为队头(front)。当队列中没有任何元素时成为空队列。队列是一种先进先出的线性表,简称FIFO表。 2 与栈类似,队列也是一种操作受限的特殊的线性表,同样可以采用顺序存储结构和链式存储结构来表示队列。 3 队列的顺序存储表示——循环队列 队列的顺序存储表示同样
1024 0
+关注
IT辰柒_Java
攀登者!
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载