3.24. Summary¶
Linear data structures maintain their data in an ordered fashion.
Stacks are simple data structures that maintain a LIFO (last in, first out) ordering.
The fundamental operations for a stack are
push
,pop
, andis_empty
.Queues are simple data structures that maintain a FIFO (first in, first out) ordering.
The fundamental operations for a queue are
enqueue
,dequeue
, andis_empty
.Prefix, infix, and postfix are all ways to write expressions.
Stacks are very useful for designing algorithms to evaluate and translate expressions.
Stacks can provide a reversal characteristic.
Queues can assist in the construction of timing simulations.
Simulations use random number generators to create a real-life situation and allow us to answer “what if” types of questions.
Deques are data structures that allow hybrid behavior like that of stacks and queues.
The fundamental operations for a deque are
add_front
,add_rear
,remove_front
,remove_rear
, andis_empty
.Lists are collections of items where each item holds a relative position.
A linked list implementation maintains logical order without requiring physical storage requirements.
Modification to the head of the linked list is a special case.