2.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, and isEmpty.

• Queues are simple data structures that maintain a FIFO, first-in first-out, ordering.

• The fundamental operations for a queue are enqueue, dequeue, and isEmpty.

• 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 addFront, addRear, removeFront, removeRear, and isEmpty.

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