Objectives¶

To understand the abstract data types stack, queue, deque, and list.
To be able to implement the ADTs stack, queue, and deque using Python lists.
To understand the performance of the implementations of basic linear data structures.
To understand prefix, infix, and postfix expression formats.
To use stacks to evaluate postfix expressions.
To use stacks to convert expressions from infix to postfix.
To use queues for basic timing simulations.
To be able to recognize problem properties where stacks, queues, and deques are appropriate data structures.
To be able to implement the abstract data type list as a linked list using the node and reference pattern.
To be able to compare the performance of our linked list implementation with Python’s list implementation.