使用 Java 的 DSA - 队列

概述

队列是一种类似于堆栈的数据结构，主要区别在于插入的第一个项目是第一个被移除的项目(FIFO - 先进先出)，而堆栈基于 LIFO，后进先出原则。

队列表示

基本操作

• 插入/入队 − 将一个项目添加到队列的后面。

• 移除/出队 − 从队列的前面移除一个项目。

在本文中，我们将使用数组实现队列。队列支持以下几个操作。

• Peek − 获取队列前面的元素。

• isFull − 检查队列是否已满。

• isEmpty − 检查队列是否为空。

插入/入队操作

每当将元素插入队列时，队列都会增加后索引以供以后使用，并将该元素存储在存储的后端。如果后端到达最后一个索引，它将被包装到底部位置。这种安排称为环绕，这种队列是循环队列。此方法也称为入队操作。

public void insert(int data){
   if(!isFull()){
      if(rear == MAX-1){
         rear = -1;            
      }       
      
      intArray[++rear] = data;
      itemCount++;
   }
}

移除/出队操作

每当要从队列中移除元素时，队列都会使用前索引获取元素并增加前索引。作为环绕式安排，如果前索引大于数组的最大索引，则将其设置为 0。

 	 	
public int remove(){
   int data = intArray[front++];
   if(front == MAX){
      front = 0;
   }
   itemCount--;
   return data;  
}

队列实现

Queue.java

package com.tutorialspoint.datastructure;

public class Queue {
    
   private final int MAX;
   private int[] intArray;
   private int front;
   private int rear;
   private int itemCount;

   public Queue(int size){
      MAX = size;
      intArray = new int[MAX];
      front = 0;
      rear = -1;
      itemCount = 0;
   }

   public void insert(int data){
      if(!isFull()){
         if(rear == MAX-1){
            rear = -1;            
         }       

         intArray[++rear] = data;
         itemCount++;
      }
   }

   public int remove(){
      int data = intArray[front++];
      if(front == MAX){
         front = 0;
      }
      itemCount--;
      return data;  
   }

   public int peek(){
      return intArray[front];
   }

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

   public boolean isFull(){
      return itemCount == MAX;
   }

   public int size(){
      return itemCount;
   }    
}

演示程序

QueueDemo.java

package com.tutorialspoint.datastructure;

public class QueueDemo {
   public static void main(String[] args){
        Queue queue = new Queue(6);
        
        //插入5个项目
        queue.insert(3);
        queue.insert(5);
        queue.insert(9);
        queue.insert(1);
        queue.insert(12);
        
        // 前面 : 0
        // 后面 : 4
        // ------------------
        // 索引 : 0 1 2 3 4
        // ------------------
        // 队列 : 3 5 9 1 12
        
        queue.insert(15);
        
        // 前面 : 0
        // 后面 : 5
        // ---------------------
        // 索引 : 0 1 2 3 4 5
        // ---------------------
        // 队列 : 3 5 9 1 12 15
        
        if(queue.isFull()){
        System.out.println("队列已满!");
        }
        
        //删除一个项目
        int num =queue.remove();
        System.out.println("元素已移除:"+num);
        // front : 1
        // rear : 5
        // -------------------
        // index : 1 2 3 4 5
        // -------------------
        // 队列 : 5 9 1 12 15
        
        //插入更多项目
        queue.insert(16);
        
        // front : 1
        // rear : -1
        // ----------------------
        // index : 0 1 2 3 4 5
        // ----------------------
        // 队列 : 16 5 9 1 12 15
        
        //由于队列已满，元素将无法插入。
        queue.insert(17);
        queue.insert(18);
        
        // ----------------------
        // index : 0 1 2 3 4 5
        // ----------------------
        // 队列 : 16 5 9 1 12 15
        System.out.println("Element at front: "+queue.peek());
        
        System.out.println("----------------------");
        System.out.println("index : 5 4 3 2  1  0");
        System.out.println("----------------------");
        System.out.print("Queue:  ");
        while(!queue.isEmpty()){
         int n = queue.remove();            
         System.out.print(n +" ");
        }
   }
}

如果我们编译并运行上述程序，则会产生以下结果 −

Queue is full!
Element removed: 3
Element at front: 5
----------------------
index : 5 4 3 2  1  0
----------------------
Queue:  5 9 1 12 15 16