Start with a model
A data structure is a representation of information plus operations that preserve rules about that representation. First write down the workload: lookup by index, lookup by key, append, remove, iterate, or find the minimum. An abstract queue specifies first-in-first-out behavior; it does not require a particular array or linked-node implementation. Separate this contract from its implementation before comparing costs.
Arrays and dynamic capacity
An array supports indexed access because an index identifies an element location directly. A Java array has fixed length; ArrayList wraps a resizable backing array. Appending usually writes into spare capacity, but a resize copies existing references. Geometric capacity growth spreads these occasional copies across many appends. Middle insertion still shifts later references. A LinkedList must follow links to an index; a known-node splice is cheap only after the relevant node references have been obtained.
End operations and ownership
Stacks remove the newest item; queues remove the oldest. ArrayDeque offers both ends and is commonly preferable to legacy Stack for single-threaded stack work. Its lack of thread safety matters when sharing work between threads. Null elements are not permitted. A producer-consumer system also needs a capacity and overload policy; choosing a collection does not by itself define blocking, rejection, fairness or lifecycle.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
Deque<String> work = new ArrayDeque<>();
work.addLast("validate");
work.addLast("save");
String next = work.removeFirst(); // "validate": FIFO
work.addFirst("retry"); // priority at the front
String urgent = work.removeFirst(); // "retry"Walkthrough
The queue starts empty. The first two additions produce [validate, save]. Removing from the front leaves [save]. Adding retry to the front produces [retry, save]. Removing from the same end returns retry. If both insertion and removal use the front, the behavior is a stack. These are alternative policies over the same deque representation.
Practice it yourself
Implement a bracket validator. Decide what an empty input means, reject a closing bracket without a matching opener, and test mixed bracket types.
Check your reasoning
Push openers. For a closer, reject an empty stack or an incorrect top, otherwise pop. Accept only if the stack is empty after the scan. Cases include empty text, (), ([{}]), ([)] and an unmatched opener.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.