I'm having a lot of trouble implementing this deque using a circular array; in particular, the remove methods seem to be removing the wrong elements no matter what I try. Can anyone help?
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]; 开发者_如何学Go
}
/**
* 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
the code size() == capacit
y will never be true, this is why it's not expanding. Make it size() == capacity - 1
.
I'm giving this away is because it's very easy to overlook
According to your given code, the value of front will always retain the value zero.
- In removeFirst(), you have to do front++;
- In insertLast() you are doing rear++ twice. You can remove the rear++ outside the if/else.
- Your removeFirst() always returns the second element, because the for-loop in that method looses the first element.
NOTE: Any of the above will not make it a circular queue. Advice: read and reimplement:)
I have an implementation on C that I have made some time ago. I think should be easy to port to Java or at least gives you a hint on how to implement it in Java.
Thanks, Sergio.
typedef struct { void *elems; / The data. */ size_t sz; /* Capacity of queue. */ size_t nelems; /* Number of elements in the queue. */ size_t first; /* Points to the first element in the queue. */ } 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++;
}
void *nx_queue_dequeue (nx_queue_t *q) { void *elem ;
if (nx_queue_empty (q))
return (NULL);
elem = q->elems[q->first];
q->first = (q->first + 1) % q->sz;
q->nelems--;
return (elem);
}
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;
}
}
};
精彩评论