Data Structures: Stack and Queue

About this unit

A data structure is a way of organising data so that it can be used efficiently. This unit studies two linear data structures that limit where items are added and removed: the stack (last in, first out) and the queue (first in, first out), along with the deque, which allows both ends. It also uses a stack to convert and evaluate arithmetic expressions written in infix, prefix and postfix notation.

Key ideas

• Stack: LIFO, with PUSH, POP and peek (top) operations.
• Overflow (no space to add) and underflow (removing from an empty structure).
• Infix, prefix and postfix notation; operator precedence.
• Evaluating postfix expressions and converting infix to postfix using a stack.
• Queue: FIFO, with enqueue at the rear and dequeue at the front.
• Deque: insertion and deletion at both front and rear.

How to prepare

Trace sequences of operations on paper, writing the contents after each step. Practise five or six infix-to-postfix conversions and postfix evaluations. Learn which Python list methods implement each operation: append(), pop() and pop(0), insert(0, x).