Design an object-oriented queue and compare implementations

You are asked to design an object-oriented Queue abstraction and discuss how it can be implemented internally in different ways.

Describe:

1. Queue interface

• Define a clean, language-agnostic interface (or abstract class) for a generic FIFO queue.
• Include the core operations and their expected behavior (e.g., enqueue, dequeue, peek, isEmpty, size, and possibly capacity-related methods).

1. Internal implementations For the same Queue interface, describe at least two or three different internal data-structure implementations, such as:

• Linked-list-based queue
• Array-based queue (including circular array/buffer)
• Queue implemented using two stacks

1. Trade-offs analysis For each implementation, analyze and compare:

• Time complexity of core operations (enqueue, dequeue, peek)
• Space usage and overhead
• Memory behavior (e.g., cache friendliness, allocations)
• Practical pros/cons and when you would choose each approach

Optionally, also discuss how you might extend the design for:

• A bounded vs unbounded queue
• Thread-safe vs non-thread-safe versions
• How you would expose these variants via interfaces/classes (e.g., using different implementations behind the same Queue interface).

Clarifying Questions to Ask

• Clarify language/runtime assumptions and the level of depth expected.
• Use examples to connect definitions to practical engineering decisions.
• Call out pitfalls, trade-offs, and common misconceptions.