Lecture Notes: Data Structures - Stacks and Queues
Overview
Part three of a five-part series on data structures.
Focus on Stacks and Queues.
Stacks
Definition: A stack is a data structure that operates on a Last In, First Out (LIFO) principle.
Operations:
Push: Add an item to the top of the stack.
Pop: Remove the item from the top of the stack.
Peek: View the top item without removing it.
Characteristics:
Only the top item is accessible.
Involves a stack pointer pointing to the top node.
Stack Overflow: Occurs when pushing to a full stack.
Stack Underflow: Occurs when popping from an empty stack.
Implementation:
Commonly implemented using arrays or object-oriented techniques.
Applications:
Processors use stacks for subroutine call management.
Local variables and interrupts handling.
Used in depth-first search algorithms, user inputs tracking, backtracking algorithms, and evaluating mathematical expressions (e.g., using the shunting yard algorithm).
Queues
Definition: A queue is a linear data structure that operates on a First In, First Out (FIFO) principle.
Operations:
Enqueue: Add an item to the back of the queue.
Dequeue: Remove the item from the front of the queue.
Peek: View the front item without removing it.
Characteristics:
Involves a back pointer (tail) and a front pointer (head).
Queue Overflow: Occurs when enqueuing into a full queue.
Queue Underflow: Occurs when dequeuing from an empty queue.
Priority Queue: Allows new items to join at the front.
Implementation:
Typically implemented using arrays or object-oriented techniques.
Circular Queue: Back pointer cycles to the front when at the array's end, useful for known memory footprint situations like game design.
Applications:
Process scheduling, data transferring between processors, printer spooling.
Breadth-first search algorithms.
Key Concepts to Understand
How stacks and queues work and their uses.
Additional Resources
Book: "Essential Algorithms for A Level Computer Science" available on Amazon.
Covers necessary data structures and algorithms.
Provides structured English, diagrams, pseudocode, and coded algorithms in Python and VB.
Includes QR code links to additional resources.
Conclusion
Understanding data structures is crucial and challenging.