使用圆形数组实现双端队列？
我在使用圆形阵列实现此双端队列时遇到了很多麻烦;特别是，无论我尝试什么，删除方法似乎都在删除错误的元素。有人可以帮忙吗？
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 个回复
呢率篓舍烫
y将永远不会成立，这就是为什么它不会扩展。做它。 我放弃它是因为它很容易被忽视雇砰
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);if (nx_queue_full (q)) return (-1); i = (q->first + q->nelems) % q->sz; q->elems[i] = elem; q->nelems++;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 deletedn"; } 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 emptyn"; else{ int temp=front; while(temp!=back){ cout<<array[temp]<<" "; temp=(temp+1)%capacity; } cout<<array[temp]<<endl; } } };