Stacks
Computer Science: OCR A Level, topic 4.2.6
Stacks
A stack is a data structure where data items are always added and removed from the top. It is often referred to as a ‘last in, first out’ data structure.
Stacks
- A stack is a data structure where data items are always added and removed from the top. It is often referred to as a ‘last in, first out’ data structure.
- Stacks can be implemented using other data structures, such as arrays or linked lists. In either case, an extra variable is required to identify the top of the stack.
Stack operations
- Several operations can be carried out on stacks:
- push() - adds an item to the top of a stack.
- pop() - removes and displays the item at the top of a stack
- peek() - displays the item at the top of a stack without removing it
- isEmpty() - checks to see if the stack is empty
- isFull() - checks to see if the stack is full
Uses
- The most common use of stacks is to reverse the order of a set of data items, as they are ‘popped’ in the opposite order that they were ‘pushed’ to a stack.
- They are also used by processors to handle interrupts.
- Stacks can be ‘static’ (fixed in size) or ‘dynamic’ (able to grow in size as necessary)
Errors
- Stack overflow errors can occur in static stacks when attempting to push an item onto a stack that is full.
- Similarly, when trying to pop from an empty stack a stack underflow error occurs.
Test yourself on Stacks
What type of data structure are stacks?