队列（Queue）移除未按FIFO工作问题求助

Hey Paul, let's break down why your queue is misbehaving when removing elements—array-based queues are tricky with pointer management, so this is a super common pitfall!

From what you described (elements add fine, but after inserting 6th/7th items only the 7th can be removed, plus late-stage duplicates), here are the most likely culprits and fixes to check:

1. Broken Front Pointer Update on Dequeue #

The #1 issue with array queues is forgetting to properly advance the front index (or adjust the array for non-circular queues) when removing elements.

Example of Bad Dequeue Logic: #

// This only returns the element but never moves the front pointer
public Point dequeue() {
    return arr[front];
}

Fix for Circular Queues: #

If you're implementing a circular queue (reusing array space once elements are dequeued), you need to update front and track the current size:

public Point dequeue() {
    if (isEmpty()) throw new NoSuchElementException("Queue is empty");
    
    Point removedItem = arr[front];
    // Wrap around to the start of the array if we hit the end
    front = (front + 1) % capacity;
    size--; // Don't forget to decrement the element count!
    
    return removedItem;
}

Fix for Non-Circular Queues: #

If you're shifting elements left when dequeuing, make sure you shift all elements and clean up the old tail:

public Point dequeue() {
    if (isEmpty()) throw new NoSuchElementException("Queue is empty");
    
    Point removedItem = arr[0];
    // Shift all elements left by one
    for (int i = 0; i < size - 1; i++) {
        arr[i] = arr[i + 1];
    }
    // Clear the now-unused last position to avoid duplicate references
    arr[size - 1] = null;
    size--;
    
    return removedItem;
}

2. Incorrect Rear Pointer or Size Tracking on Enqueue #

If your rear index isn't being updated correctly (especially in circular queues), you might be overwriting elements or leaving the queue in an inconsistent state. Also, failing to increment size when enqueuing will break empty/full checks.

Bad Enqueue Logic Example: #

// Doesn't handle circular wrap or track size
public void enqueue(Point p) {
    arr[rear] = p;
    rear++; // Will go out of bounds once it hits the array end
}

Correct Circular Enqueue: #

public void enqueue(Point p) {
    if (isFull()) throw new IllegalStateException("Queue is full");
    
    arr[rear] = p;
    rear = (rear + 1) % capacity;
    size++; // Critical: keep size in sync with actual elements
}

3. Debug with Print Statements #

To pinpoint exactly where things go wrong, add debug output after every enqueue/dequeue. Print the front, rear, size, and the full array state:

// After enqueue:
System.out.printf("Enqueued: %s | Front: %d, Rear: %d, Size: %d%n", p, front, rear, size);
System.out.println(Arrays.toString(arr));

// After dequeue:
System.out.printf("Dequeued: %s | Front: %d, Rear: %d, Size: %d%n", removedItem, front, rear, size);
System.out.println(Arrays.toString(arr));

This will show you if the 6th/7th enqueues are messing up the pointers, or if dequeues aren't advancing front like they should.

4. Check for Unhandled Edge Cases #

• What happens when the queue hits full capacity? If you're not resizing a non-circular queue or checking for full state in a circular queue, you might be overwriting elements without realizing it.
• Are you initializing front to 0 and rear to 0 (circular queue) or 0 (non-circular)? Incorrect initial values can throw off the entire logic.

内容的提问来源于stack exchange，提问作者Paul