Most efficient way to implement stack and queue together?

Question

What would be the most appropriate way to implement a stack and a queue together efficiently, in a single data structure. The number of elements is infinite. The retrieval and insertion should both happen in constant time.

• soegaard: Is amortized constant time also okay?
• tobias_k: Isn't that pretty much what a deque does?

Answer 1

A doubly linked list, has all the computational complexity attributes you desire, but poor cache locality.

A ring buffer (array) that allows for appending and removing at head and tail has the same complexity characteristics. It uses a dynamic array and requires reallocation, once the number of elements grows beyond it's capacity.

But, similar to an array list / vector generally being faster in practice for sequential access versus a linked list. In most cases it will be faster and more memory efficient than using a doubly linked list implementation.

It is one of the possible implementations for the dequeue abstract data structure, see e.g. the ArrayDeque<E> implementation in Java.

Answer 2

A doubly linked list can solve this problem with all operations taking constant time:

• It allows push() or enqueue() by appending the element to the list in constant time.
• It allows pop() by removing the last element in constant time
• It allows dequeue() by removing the first element, also in constant time.

• amit: @MarkPercieval I am pretty sure YOU can code it in java, and let us know if you encounter any problems. This is YOUR assignment, after all

Answer 3

A two-way linked list is going to be best for this. Each node in the list has two references: one to the item before it and one to the item after it. The main list object maintains a reference to the item at the front of the list and one at the back of the list.

Any time it inserts an item, the list:

1. creates a new node, giving it a reference to the previous first or last node in the list (depending on whether you're adding to the front or back).
2. connects the previous first or last node to point at the newly-created node.
3. updates its own reference to the first or last node, to point at the new node.

Removing an item from the front or back of the list effectively reverses this process.

Inserting to the front or back of the structure will always be an O(1) operation.