快速掌握队列的基础知识

桃扇骨 2024-02-19 10:11 51阅读 0赞

#### 目录 ####

*   *  队列的特点
     *  基于链表实现队列
     *  用栈实现队列
     *  用队列实现栈

队列是一种线性数据结构，它只允许在一边进行插入操作（队尾），另一边进行删除操作（队头）。插入操作称为入队，删除操作称为出队。队列遵循先进先出（FIFO）的原则，即队头的元素最先被删除，队尾的元素最后被删除。

![在这里插入图片描述][8e80c8cacff54725a3bf0f34f52ec693.png]

### 队列的特点 ###

1.  先进先出：队列中的元素按照其进入队列的顺序被取出，即先进入队列的元素将先被取出。
2.  有限容量：队列通常具有一定的最大容量，当队列达到最大容量时，新的元素将无法进入队列。
3.  基本操作：队列支持插入（入队）和删除（出队）两种基本操作，其中插入操作在队列的尾部进行，删除操作在队列的头部进行。

### 基于链表实现队列 ###

这种实现方式比较简单，具体如下：

public class LinkQueue {
        
        // 头节点
        private  Node front;
        //尾节点
        private Node rear;
        //队列大小
        private int size;
        public LinkQueue(){
        
            //初始化头节点和尾节点
            this.front = new Node(0);
            this.rear = new Node(0);
        }
        /**
         *入队
         */
        public  void push(int value){
        
         //创建新节点
         Node newNode = new Node(value);
          //临时节点指向头节点
          Node temp = front;
          //循环遍历，直到临时节点指向尾节点
          while (temp.next!=null){
        
              temp = temp.next;
          }
          //将新节点指向头节点
          temp.next = newNode;
          //将尾节点指向新节点
          rear = newNode;
          //队列大小加1
          size++;
        }
        /**
         * 出队
         */
        public int pull(){
        
           //如果队列为空，则提示
           if(front.next==null){
        
               System.out.println("队列已经为空！");
           }
           //获取头节点指向的节点
           Node fristNode = front.next;
           //将头节点指向头节点指向的节点的下一个节点
           front.next = fristNode.next;
           //队列大小减1
           size--;
           //返回头节点指向的节点
           return fristNode.data;
        }
        /**
         * 遍历队列
         */
        public  void  traverse(){
        
           //临时节点指向头节点指向的节点
           Node temp = front.next;
           //循环遍历，直到临时节点指向尾节点
           while (temp!=null){
        
               //输出临时节点指向的节点
               System.out.printf(temp.data+"\t");
               //将临时节点指向临时节点指向的节点的下一个节点
               temp = temp.next;
           }
        }
       //测试方法
        public static void main(String[] args) {
        
         //创建一个队列
         LinkQueue linkQueue = new LinkQueue();
         //将1，2，3入队
         linkQueue.push(1);
         linkQueue.push(2);
         linkQueue.push(3);
            //输出第一个出队的元素
            System.out.println("第一个出队的元素为"+linkQueue.pull());
            //输出队列中的元素
            System.out.println("队列中的元素为");
            linkQueue.traverse();
    
        }
    
    }
    class Node{
        
        //节点数据
        public  int data;
        //指向下一个节点
        public Node next;
        //构造函数
        public Node(int data){
        
            this.data = data;
        }
    }

首先，定义了一个Node类来表示队列中的节点。每个节点包含一个数据项和一个指向下一个节点的指针。  
在LinkQueue类中，定义了三个私有属性：front表示队列的头节点，rear表示队列的尾节点，size表示队列的大小。  
构造函数LinkQueue()用来初始化队列，它创建一个头节点和一个尾节点，并使它们的值都为0。  
push()方法用于入队操作，即向队列中添加元素。它首先创建一个新的节点，然后通过一个临时节点遍历队列，直到找到队尾节点，将新节点链接至队尾，并更新rear指针指向新的队尾节点。最后，将队列大小加1。  
pull()方法用于出队操作，即从队列中取出元素。首先检查队列是否为空，如果为空则提示队列已经为空。然后从队列头部取出节点，更新front指向下一个节点，并将队列大小减1。最后返回被取出节点的值。  
traverse()方法用于遍历队列，打印出队列中的所有元素。

### 用栈实现队列 ###

用队列实现栈在许多题中会遇到，例如力扣232题：

> 实现 MyQueue 类：
> 
>  *  void push(int x) 将元素 x 推到队列的末尾
>  *  int pop() 从队列的开头移除并返回元素
>  *  int peek() 返回队列开头的元素
>  *  boolean empty() 如果队列为空，返回 true ；否则，返回 false

这道题我们的实现思路就是用两个栈，一个输入栈，一个输出栈，数据输入都会压入输入栈中，当数据输出时，会从输出栈中出栈，当输出栈中为空时我们需要把输入栈中的数据全部出栈，然后压入输出栈中。具体代码示例如下：

class MyQueue {
        
      Deque<Integer> inStack = null;
      Deque<Integer> outStack = null;
        public MyQueue() {
        
         inStack = new LinkedList<>();
         outStack = new LinkedList<>();
        }
        
        public void push(int x) {
        
          inStack.push(x);
        }
        
        public int pop() {
        
         if(outStack.isEmpty()){
        
             in2out();
         }
         return outStack.pop();
        }
        
        public int peek() {
        
        if(outStack.isEmpty()){
        
            in2out();
        }
        return outStack.peek();
        }
        
        public boolean empty() {
        
        return inStack.isEmpty()&&outStack.isEmpty();
        }
        public void in2out(){
        
            while (!inStack.isEmpty()){
        
                outStack.push(inStack.pop());
            }
        }
    }

### 用队列实现栈 ###

我们来看力扣225题：  
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

> 实现 MyStack 类：
> 
>  *  void push(int x) 将元素 x 压入栈顶。
>  *  int pop() 移除并返回栈顶元素。
>  *  int top() 返回栈顶元素。
>  *  boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

这道题我们的实现思路就是用两个队列，我们需要把刚压入的元素放入队列前端以方便出栈的顺序刚好是后进先出，所以我们用队列2辅助队列1进行操作，我们把入栈操作的元素先放到队列2中，然后把队列1中的元素全部出队放入队列2中，然后再把队列1与队列2相互交换，则队列1中的元素即为栈中的元素。

class MyStack {
        
       Queue<Integer> queue1 = null;
       Queue<Integer> queue2 = null;
        public MyStack() {
        
      queue1 = new LinkedList<>();
      queue2 = new LinkedList<>();
        }
        
        public void push(int x) {
        
         //将元素x压入队列2
         queue2.offer(x);
         //将队列1中的元素压入队列2，并将其弹出
         while (!queue1.isEmpty()){
        
             queue2.offer(queue1.poll());
         }
         //交换队列1和队列2
         Queue<Integer> temp = queue1;
         queue1 = queue2;
         queue2 = temp;
        }
        
        public int pop() {
        
          //从队列1中弹出元素
          return   queue1.poll();
        }
        
        public int top() {
        
          //返回队列1的第一个元素
          return queue1.peek();
        }
        
        public boolean empty() {
        
       //判断队列1是否为空
       return queue1.isEmpty();
        }
    }

队列是一种重要的数据结构，它具有“先进先出”的特点，常用于按顺序存储和访问数据。理解队列的基本概念、特点和常见操作对于计算机科学领域的学习和工作都非常重要。在实际应用中，队列有着广泛的用途，包括网络传输、操作系统、任务队列和打印队列等方面。

[8e80c8cacff54725a3bf0f34f52ec693.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/9f1d94c8e11143e19b5af221f38f7af6.png