0

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();


    }

}
4

8 に答える 8

4

あなたの実装について私が得られないのは次のとおりです。

  • あなたが使用しているフロントメソッドではiter_、しかし他のどこにもありません。それは何のために良いですか？
  • 実際に削除せずに削除されたものを追跡するためにある種の変数を使用していない場合、技術的には、最初の項目がなくなるように、配列のすべての項目を 1 つの位置だけ左にシフトする必要があります。ただし、これは O(N) 操作です。
  • 配列の代わりにリンク リストを使用してキューを実装する方が簡単です。
于 2012-09-23T06:51:23.740 に答える
3

配列を使用してキューを構築する場合、配列の先頭への循環「ポインタ」を作成できます。これを使用して先頭を取得できます。

配列からのポップは、この循環ポインターを増やすことによって簡単に実行できます。

変数を維持しintます: top、要素をポップする必要がある場合は、top = (top + 1) % items_.length

を使用すると、頭を簡単に取得できitems_[top]ます。

そこにない要素をポップしないように注意してください (空の配列からのポップ)。 おそらく、キューのサイズの変数
も維持する必要があります。size

于 2012-09-23T06:46:18.450 に答える
1

以下に、単純なスレッドセーフな 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;
        }
    }
}
于 2014-03-02T00:46:00.670 に答える
0

これを確認してください：それにはメソッドが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());  
  }  
  }  
 }
于 2012-09-23T06:46:22.480 に答える
0

キューを設計するときは、要素を追加および削除する方法などの優先順位を決定する必要があります。このリンクを参照して、これと同様に実装できます。 FIFO

典型的な例は次のとおりです。

 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());
    }
}
于 2012-09-23T06:49:36.100 に答える
0

リストのような配列から要素を削除することはできません。値を上に移動し、配列の最後のインデックスを null に設定する必要があります。メソッドを実装する Java クラスのソースを見てみましょうQueue.remove()。たとえば、次は の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();
    }
于 2012-09-23T06:49:41.277 に答える
0

まず、配列から項目を削除することはできません。上書きすることはできます。代わりにa を使用できますList。

amit's answer が指摘したように、別のオプションは循環キューを使用することです。

配列を使用した簡単なソリューションは次のとおりです。

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++];
}
于 2012-09-23T06:51:10.957 に答える
0

これは私が実装したコードで、システムで正常に動作しています。

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();
 }
}
于 2016-08-25T07:57:43.893 に答える