java - 如何在 Java 中编写队列

Question

我正在尝试在java中创建一个队列。

问题是我不知道如何从数组中删除（？）一个值，即我出列的索引值。

这是我的代码。front() 方法是出列部分。我使用 iter_ 设置当前索引位置。但是正如您所看到的，尽管该值仍保留在数组中，但它使正确的值出队:(

public class IntQueue {

    private int[] items_;
    private int top_;
    private int capacity_;
    private int iter_;

    public IntQueue(int capacity)
    {
        if(capacity <=0) capacity = 10;

        capacity_ = capacity;
        top_=0;
        count_ = 0;
        iter_=0;

        items_= new int[capacity_];
    }

    public void push_back(int value)
    {
        if(top_>= capacity_)
            overflow();

        items_[top_++]=value;
        count_++;
    }

    public int front()
    {
        if(top_<=0)
            return 0;

        int temp=0;
        temp=items_[iter_];

        count_--;
        iter_++;
        return temp;

    }

    public IntQueue clone()
    {
        IntQueue result = new IntQueue(capacity_);

        for(int i=0 ; i<top_; ++i)
        {
            result.push_back(items_[i]);

        }

        /*for(int i=0 ; i<top_ ; ++i)
        {

            result.items_[i] = items_[i];
        }*/

        return result;

    }

    public void log()
    {

        for(int i=0 ; i <top_; ++i)
        {
            System.out.print(items_[i]);
            if(i<top_ -1)
                System.out.print(", ");
        }
        System.out.println();
        }

    }

    private void overflow()
    {
        int[] newItem = new int[capacity_*2];

        for(int i=0 ; i <top_; ++i)
            newItem[i] = items_[i];
        items_=newItem;
        capacity_ *=2;

    }

    public static void main(String args[])
    {
        IntQueue queue = new IntQueue(2);

        System.out.println("queue push 3: "); queue.push_back(3);
        System.out.println("queue push 2: "); queue.push_back(2);
        System.out.println("queue push 1: "); queue.push_back(1);

        System.out.print("queue log: "); queue.log();

        System.out.println("front " + queue.front());
        System.out.println("front " + queue.front());

        System.out.print("queue log: "); queue.log();

        System.out.println("queue push 12: "); queue.push_back(12);
        System.out.println("queue push 11: "); queue.push_back(11);
        System.out.println("queue push 21: "); queue.push_back(21);
        System.out.println("queue push 31: "); queue.push_back(31);

        System.out.print("queue log: "); queue.log();

        System.out.println("front " + queue.front());
        System.out.println("front " + queue.front());

        System.out.print("clone queue log: "); queue.clone().log();


    }

}

score 4 · Accepted Answer

关于您的实施，我不明白的是：

在您使用的前面方法中iter_，但没有其他地方。到底有什么好处呢？
如果您没有使用某种变量来跟踪已删除的内容而没有实际删除它，从技术上讲，您需要将数组的所有项目向左移动一个位置，这样第一个项目就消失了。然而，这是一个 O(N) 操作。
使用链表而不是数组来实现队列更容易。

score 3 · Accepted Answer

使用数组构建队列时，您可以创建一个指向数组头部的循环“指针”，您可以使用它来检索顶部。

简单地通过增加这个循环指针来从数组中弹出。

维护一个int变量：top，一旦你需要弹出一个元素top = (top + 1) % items_.length

使用检索头部很简单items_[top]。

确保您防止弹出不存在的元素（从空数组中弹出）。
您可能还需要维护size队列大小的变量。

score 1 · Accepted Answer

下面我分享我提出的简单线程安全 FIFO 队列的解决方案：D

public class Queue extends Object {

    private int numElements;

    private Node first;
    private Node last;

    /**
     * Helper linked list class 
     */
    private static class Node {
        private Object item;
        private Node next;
    }

    /**
     * Creates a new Queue object. 
     */
    public Queue() {
        numElements = 0;
        first = last = null;
    }

    /**
     * Puts an object at the end of the queue.
     * 
     * @param object 
     */
    public void putObject(Object object) {

        synchronized (this) {

            Node newNode = new Node();
            newNode.item = object;
            newNode.next = null;

            if ( numElements == 0 ) {
                first = last = newNode;
            } else {
                last.next = newNode;
                last = newNode;
            }

            numElements += 1;
        }
    }

    /**
     * Gets an object from the beginning of the queue. The object is removed
     * from the queue. If there are no objects in the queue, returns null.
     */
    public Object getObject() {

        synchronized (this) {

            Object item = null;

            if ( numElements > 0 ) {

                item = first.item;
                first = first.next;

                numElements -= 1;

                if (numElements == 0) {
                    last = null;
                }
            } 

            return item;
        }
    }
}

score 0 · Accepted Answer

当您设计一个队列时，您需要确定优先级，例如您将如何添加和删除元素。您可以通过此链接并以类似的方式实现它。先进先出

一个典型的例子是：

 import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {

    public static void main(String[] args) {

        Queue<String> qe=new LinkedList<String>();

        qe.add("b");
        qe.add("a");
        qe.add("c");
        qe.add("e");
        qe.add("d");

        Iterator it=qe.iterator();

        System.out.println("Initial Size of Queue :"+qe.size());

        while(it.hasNext())
        {
            String iteratorValue=(String)it.next();
            System.out.println("Queue Next Value :"+iteratorValue);
        }

        // get value and does not remove element from queue
        System.out.println("Queue peek :"+qe.peek());

        // get first value and remove that object from queue
        System.out.println("Queue poll :"+qe.poll());

        System.out.println("Final Size of Queue :"+qe.size());
    }
}

score 0 · Accepted Answer

您不能从像列表这样的数组中删除元素。您需要将值向上移动并将数组的最后一个索引设置为空。看一下实现Queue.remove()方法的java类的源码。例如以下是来自removeAt(int index)方法的代码ArrayBlockingQueue。

void removeAt(int i) {
        final E[] items = this.items;
        // if removing front item, just advance
        if (i == takeIndex) {
            items[takeIndex] = null;
            takeIndex = inc(takeIndex);
        } else {
            // slide over all others up through putIndex.
            for (;;) {
                int nexti = inc(i);
                if (nexti != putIndex) {
                    items[i] = items[nexti];
                    i = nexti;
                } else {
                    items[i] = null;
                    putIndex = i;
                    break;
                }
            }
        }
        --count;
        notFull.signal();
    }

score 0 · Accepted Answer

首先，你不能从数组中删除一个项目，你可以覆盖它。您可以使用 aList代替。

正如阿米特的回答所指出的那样，另一种选择是使用循环队列。

使用数组的简单解决方案是：

int queue[SIZE];
int first = 0;
int last = 0;

void enque(int i) {
    if(last == SIZE)
        throw new RuntimeExeption("Queue is full");
    queue[last++] = i;
}

int deque() {
    if(first == last)
        throw new RuntimeExeption("Queue is empty");
    return queue[first++];
}

score 0 · Accepted Answer

检查这个：它有enqueue和dequeue方法：

 import java.io.*;  
 import java.lang.*;  
 class clrqueue  
 {  
  DataInputStream get=new DataInputStream(System.in);  
  int a[];  
  int i,front=0,rear=0,n,item,count=0;  
  void getdata()  
  {  
  try  
   {  
   System.out.println("Enter the limit");  
   n=Integer.parseInt(get.readLine());  
   a=new int[n];  
   }   
  catch(Exception e)  
   {  
   System.out.println(e.getMessage());  
   }  
  }  
  void enqueue()  
  {  
   try  
   {  
   if(count<n)  
    {  
    System.out.println("Enter the element to be added:");  
    item=Integer.parseInt(get.readLine());  
    a[rear]=item;  
     rear++;  
    count++;  
    }  
   else  
    System.out.println("QUEUE IS FULL");  
   }  
  catch(Exception e)  
   {  
   System.out.println(e.getMessage());  
   }  
  }  
  void dequeue()  
  {  
   if(count!=0)  
    {  
    System.out.println("The item deleted is:"+a[front]);  
    front++;  
    count--;  
    }  
   else  
    System.out.println("QUEUE IS EMPTY");  
  if(rear==n)  
   rear=0;  
  }  
  void display()  
  {  
   int m=0;  
   if(count==0)  
   System.out.println("QUEUE IS EMPTY");  
   else  
   {  
   for(i=front;m<count;i++,m++)  
   System.out.println(" "+a[i]);  
   }  
  }  
 }  
 class Myqueue  
 {  
  public static void main(String arg[])  
  {  
  DataInputStream get=new DataInputStream(System.in);  
  int ch;  
  clrqueue obj=new clrqueue();  
  obj.getdata();  
  try  
  {  
   do  
   {  
   System.out.println(" 1.Enqueue  2.Dequeue  3.Display  4.Exit");  
   System.out.println("Enter the choice");  
   ch=Integer.parseInt(get.readLine());  
   switch (ch)  
   {  
   case 1:  
       obj.enqueue();  
      break;  
   case 2:  
      obj.dequeue();  
      break;  
   case 3:  
      obj.display();  
      break;  
   }  
   }  
   while(ch!=4);  
  }  
  catch(Exception e)  
  {  
  System.out.println(e.getMessage());  
  }  
  }  
 }

score 0 · Accepted Answer

这是我实现的代码，在我的系统中运行良好。

import java.util.Arrays;

public class Queue {

public int[] queue = new int[3];

int head = -1, tail =-1;

public void enqueue(int N){
    if(tail == (queue.length-1))
        queue = Arrays.copyOf(queue,2*queue.length);
    if(head == -1){
        head++;
        tail++;
        queue[head] = N;
    }
    else {
        tail++;
        queue[tail] = N;
    }

}

public int dequeue(){
    if(head == -1)
        throw new IllegalStateException("Cannot dequeue if queue is empty");
    int firstItem = queue[head];
    if (head == tail) {
        head = -1;
        tail = -1;
    }
    else
        head++;
    return firstItem;
}

public void display(){
    for (int i = head; i<= tail ; i++){
        System.out.println("Display: " + queue[i]);
    }
 }
}
public class Main {

public static void main(String[] args) {

    Queue queue = new Queue();
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    queue.enqueue(40);
    queue.display();
    int dequeue = queue.dequeue();
    System.out.println(dequeue);
    queue.display();
    int dequeue1 = queue.dequeue();
    System.out.println(dequeue1);
    queue.display();
 }
}

java - 如何在 Java 中编写队列

8 回答 8

Related

Reference