StacksQueues

Notes

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.

StacksQueues/Python

StacksQueues/Java

Skiena Chapter 3

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.

Stacks:

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

Queues:

• 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.

Flags

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag