Dsa Using Java 简明教程

DSA using Java - Queue

Overview

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

Queue is kind of data structure similar to stack with primary difference that the first item inserted is the first item to be removed (FIFO - First In First Out) where stack is based on LIFO, Last In First Out principal.

Queue Representation

Basic Operations

insert / enqueue − add an item to the rear of the queue.
remove / dequeue − remove an item from the front of the queue.

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

We’re going to implement Queue using array in this article. There is few more operations supported by queue which are following.

Peek − get the element at front of the queue.
isFull − check if queue is full.
isEmpty − check if queue is empty.

Insert / Enqueue Operation

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

Whenever an element is inserted into queue, queue increments the rear index for later use and stores that element at the rear end of the storage. If rear end reaches to the last index and it is wrapped to the bottom location. Such an arrangement is called wrap around and such queue is circular queue. This method is also termed as enqueue operation.

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

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

Remove / Dequeue Operation

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

Whenever an element is to be removed from queue, queue get the element using front index and increments the front index. As a wrap around arrangement, if front index is more than array’s max index, it is set to 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 +" ");
      }
   }
}

如果我们编译并运行上述程序，它将生成以下结果 -

If we compile and run the above program then it would produce following result −

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