java 使用循环数组实现双端队列？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5070363/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implementing a deque using a circular array?
提问by smooth_smoothie
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?
我在使用循环数组实现这个双端队列时遇到了很多麻烦；特别是，无论我尝试什么，remove 方法似乎都在删除错误的元素。任何人都可以帮忙吗？
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
回答by smooth_smoothie
the code size() == capacity will never be true, this is why it's not expanding. Make it size() == capacity - 1.
代码size() == capacity 永远不会是真的，这就是它不扩展的原因。让它size() == capacity - 1。
I'm giving this away is because it's very easy to overlook
我放弃这个是因为它很容易被忽视
回答by Suraj Chandran
According to your given code, the value of front will always retain the value zero.
根据您给定的代码， front 的值将始终保留值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.
- 在removeFirst() 中，您必须执行front++；
- 在insertLast() 中，你做了两次后部++。您可以删除 if/else 之外的后部++。
- 您的removeFirst()始终返回第二个元素，因为该方法中的 for 循环丢失了第一个元素。
NOTE: Any of the above will not make it a circular queue. Advice: read and reimplement:)
注意：以上任何一项都不会使其成为循环队列。建议：阅读并重新实现:)
回答by Sergio Nardi
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.
我有一个关于 C 的实现，是我前段时间做的。我认为应该很容易移植到 Java 或者至少给你一个关于如何在 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;
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;
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_capacity (nx_queue_t *q) { return (q->sz); }
size_t nx_queue_size (nx_queue_t *q) { return (q->nelems); }
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_empty (nx_queue_t *q) { return (!q->nelems); }
int nx_queue_full (nx_queue_t *q) { return (q->nelems == q->sz); }
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;
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 ;
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);
}
}
回答by Ayush Jindal
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;
}
}
};
