Dsa Using Java 简明教程

DSA using Java - Queue

Overview

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

Queue Representation

Basic Operations

insert / enqueue − 向队列后部添加项目。
remove / dequeue − 从队列前部删除项目。

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

Peek − 获取队列前部的元素。
isFull − 检查队列是否已满。
isEmpty − 检查队列是否为空。

Insert / Enqueue Operation

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

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

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

Remove / Dequeue Operation

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

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

Queue Implementation

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;
   }
}

Demo Program

QueueDemo.java

package com.tutorialspoint.datastructure;

public class QueueDemo {
   public static void main(String[] args){
      Queue queue = new Queue(6);

      //insert 5 items
      queue.insert(3);
      queue.insert(5);
      queue.insert(9);
      queue.insert(1);
      queue.insert(12);

      // front : 0
      // rear  : 4
      // ------------------
      // index : 0 1 2 3 4
      // ------------------
      // queue : 3 5 9 1 12

      queue.insert(15);

      // front : 0
      // rear  : 5
      // ---------------------
      // index : 0 1 2 3 4  5
      // ---------------------
      // queue : 3 5 9 1 12 15

      if(queue.isFull()){
         System.out.println("Queue is full!");
      }


      //remove one item
      int num = queue.remove();
      System.out.println("Element removed: "+num);
      // front : 1
      // rear  : 5
      // -------------------
      // index : 1 2 3 4  5
      // -------------------
      // queue : 5 9 1 12 15

      //insert more items
      queue.insert(16);

      // front : 1
      // rear  : -1
      // ----------------------
      // index : 0  1 2 3 4  5
      // ----------------------
      // queue : 16 5 9 1 12 15

      //As queue is full, elements will not be inserted.
      queue.insert(17);
      queue.insert(18);

      // ----------------------
      // index : 0  1 2 3 4  5
      // ----------------------
      // queue : 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