From charlesreid1


Stacks and Queues - why

Why stacks and queues? If you follow the abstract data type interface, all operations to access stacks and queues are O(1). (See Abstract Data Types page for a comparison table.)

Stacks - last-in, first-out data structure where things are added and removed from the top.

Queues - first-in, first-out data structure where things are removed from the front and added to the back.



Goodrich Chapter 6


Stacks are LIFO objects that provide the following methods:

  • push
  • pop

You can implement other convenience methods, but that's the basic concept.

  • top or peek
  • size
  • isEmpty

The stack class in Java Collections framework provides a built-in object that's fully functional and very fast.

Two implementations guided by Goodrich book:

Skiena Chapter 3

Basics of stacks and queues

Stacks and queues provide a container that permits storage and retrieval of data items independent of content.

This contrasts with Dictionaries, a data structure where data retrieval happens based on key values or content.

If a container permits storage and retrieval independent of content, its defining characteristic is the order of retrieval that they support.

Stacks implement LIFO (last in first out) order.

Queues implement FIFO (first in first out) order.


  • push(x,s) - insert item x at top of stack s
  • pop(s) - return and remove the top item of stack s


  • enqueue(x,q) - insert item x at the back of queue q
  • dequeue(q) - return and remove the front item from queue q

Queues are the fundamental data structure for controlling breadth-first searches in graphs.

These can be implemented using arrays or linked lists, with or without an upper bound.

Priority queues

See Priority Queues


See also: