2

我在使用循环数组实现这个双端队列时遇到了很多麻烦；特别是，无论我尝试什么，删除方法似乎都在删除错误的元素。任何人都可以帮忙吗？

public class ArrayDeque
{
   public static final int INIT_CAPACITY = 8;   // initial array capacity
   protected int capacity;  // current capacity of the array
   protected int front;     // index of the front element
   protected int rear;      // index of the rear element
   protected int[] A;       // array deque

   public ArrayDeque( )      // constructor method
   {
      A = new int[ INIT_CAPACITY ];
      capacity = INIT_CAPACITY;
      front = rear = 0;
    }

   /**
     * Returns the number of items in this collection.
     * @return the number of items in this collection.
     */
    public int size( )
    {
        return rear - front;
    }

    /**
     * Returns true if this collection is empty.
     * @return true if this collection is empty.
     */ 
    public boolean isEmpty( )
    {
        return front == rear;
    }
    /**
     * Returns the first element of the deque
     */
    public int getFirst() throws EmptyDequeException
    {     
        if(isEmpty()){
            throw new EmptyDequeException("Deque is empty.");
        }
        return A[front % capacity];       
    }
    /**
     * Returns the last element of the deque
     */
    public int getLast( ) throws EmptyDequeException
    {  
        if(isEmpty()){
            throw new EmptyDequeException("Deque is empty.");
        }
        return A[(front + rear - 1) % capacity];   // replace this line with your code         
    }
    /**
     * Inserts e at the beginning (as the first element) of the deque
     */
    public void insertFirst( int e )
    {
        rear++;
        if(size() == capacity){
            capacity *= 2;
        }
        int[] B = new int[capacity];
        for(int i = 0; i < size(); i++){
            B[i] = A[i];
        }
        A = B;
        for(int i = size(); i >= front; i--){
            A[i+1] = A[i];
        }
        A[front] = e;
        front = front % capacity;
    }
    /**
     * Inserts e at the end (as the last element) of the deque
     */
    public void insertLast( int e )
    {
        if(size() == capacity){
            capacity *= 2;
            A[rear++] = e;
        }
        else{
            A[rear++] = e;
        }
        rear++;
    }
    /**
     * Removes and returns the first element of the deque
     * Shrink array by half of current size N when number of elements in the deque falls below N/4
     * minimum capacity should always be 8
     */
    public int removeFirst( ) throws EmptyDequeException
    {
        if(size() == 0){
            throw new EmptyDequeException("Deque is empty.");
        }
        if(capacity >= 8){
            if(size() < capacity/4){
                capacity /= 2;
            }
        }
        int[] B = new int[capacity];
        for(int i = 1; i < size(); i++){
            B[i-1] = A[i];
        }
        A = B;
        return A[front];
    }
    /**
     * Removes and returns the last element of the deque
     * Shrink array by half of current size N when number of elements in the deque falls below N/4
     * minimum capacity should always be 8
     */
    public int removeLast( ) throws EmptyDequeException
    {
        if(size() == 0){
            throw new EmptyDequeException("Deque is empty.");
        }
        if(capacity >= 8){
            if(size() < capacity/4){
                capacity /= 2;
            }
        }
        int[] B = new int[capacity];
        for(int i = front; i<size()-1; i++){
            B[i] = A[i];
        }
        A = B;
        rear--;
        return A[rear];
    }
}  // end class
4

4 回答 4

4

代码size() == capacity 永远不会是真的，这就是它没有扩展的原因。让它size() == capacity - 1。

我放弃这个是因为它很容易被忽视

于 2011-03-04T12:33:12.467 回答
1

根据您给定的代码， front 的值将始终保留值zero。

  1. 在removeFirst()中，你必须做front++；
  2. 在insertLast()中，您执行了两次后部++。您可以删除 if/else 之外的后部++。
  3. 您的removeFirst()始终返回第二个元素，因为该方法中的 for 循环会丢失第一个元素。

注意：以上任何一项都不会使其成为循环队列。建议：阅读并重新实现:)

于 2011-02-21T19:42:42.130 回答
-1

我有一个前段时间在 C 语言上的实现。我认为应该很容易移植到 Java，或者至少给你一个关于如何在 Java 中实现它的提示。

谢谢，塞尔吉奥。

typedef struct { void * elems; /数据。*/ size_t sz; /* 队列容量。*/ size_t nelems; /* 队列中的元素数。*/ size_t 优先；/* 指向队列中的第一个元素。*/ } nx_queue_t;

nx_queue_t *nx_queue_create (size_t size) { nx_queue_t *q;

if ( (q = malloc (sizeof(nx_queue_t))) == NULL )
    return (NULL);

q->sz = size;
q->nelems = 0;
q->first=0;

if ( (q->elems = malloc (sizeof(void*)*size)) == NULL ) {
    free (q);
    return (NULL);
}

return (q);

}

size_t nx_queue_capacity (nx_queue_t *q) { return (q->sz); }

size_t nx_queue_size (nx_queue_t *q) { return (q->nelems); }

int nx_queue_empty (nx_queue_t *q) { return (!q->nelems); }

int nx_queue_full (nx_queue_t *q) { return (q->nelems == q->sz); }

int nx_queue_enqueue (nx_queue_t *q, void *elem) { size_t i;

if (nx_queue_full (q))
    return (-1);

i = (q->first + q->nelems) % q->sz;
q->elems[i] = elem;
q->nelems++;

}

无效 *nx_queue_dequeue (nx_queue_t *q) { 无效 *elem ;

if (nx_queue_empty (q))
    return (NULL);

elem = q->elems[q->first];
q->first = (q->first + 1) % q->sz;
q->nelems--;

return (elem);

}

于 2011-02-21T19:50:25.130 回答
-1 
class Deque{
    int capacity=0,back=-2,front=0;
    int*array=NULL;
    bool isEmpty(){
        return back==-2;
    }
    bool isFull(){
        return ((front-1+capacity)%capacity==back)||((back+1)%capacity==front);
    }
    public:
    Deque(int n){
        capacity=n;
        array= new int[n];
        cout<<"deque allocated with capacity "<<n<<endl;
    }
    ~Deque(){
        delete[] array;
        cout<<"deque deleted\n";
    }
    bool push_back(int x){
        if(isFull())
            return false;
        if(back==-2)
            back=-1;
        back=(back+1)%capacity;
        array[back]=x;
        return true;
    }
    bool push_front(int x){
        if(isFull())
            return false;
        if(back==-2){
            back=0;
            front=1;
        }
        front=(front-1+capacity)%capacity;
        array[front]=x;
        return true;
    }
    int pop_back(){
        if(isEmpty())
            return -1000;
        int a=array[back];
        if(back==front){
            front=0;
            back=-2;
        }
        else
            back=(back-1+capacity)%capacity;
        return a;
    }
    int pop_front(){
        if(isEmpty())
            return -1000;
        int a=array[front];
        if(back==front){
            front=0;
            back=-2;
        }
        else
            front=(front+1)%capacity;
        return a;
    }
    void print(){
        if(isEmpty())
            cout<<"deque is empty\n";
        else{
            int temp=front;
                while(temp!=back){
                    cout<<array[temp]<<" ";
                    temp=(temp+1)%capacity;
                }
            cout<<array[temp]<<endl;
        }
    }
};
于 2018-09-07T07:38:48.860 回答