Stacks (OCR A Level Computer Science)
Revision Note
Author
James WoodhouseExpertise
Computer Science
Stacks
What is a Stack?
A stack is a last in first out (LIFO) data structure
Items can only be added to or removed from the top of the stack
Stacks are key structures in the computing world as they are used to reserve an action, such as go back a page or undo
A real-life example of a stack would be a pile (or stack) of plates at a buffet; you can only take a plate from the top, and if you need to reach the bottom one you have to remove all the others first
It is often implemented using an array
Where the maximum size required is known in advance, static stacks are preferred as they are easier to implement and make more efficient use of memory
A stack has 6 main operations, which can be seen below
|
|
|---|---|
isEmpty() | This checks is the stack is empty by checking the value of the top pointer |
push(value) | This adds a new value to the end of the list, it will need to check the stack is not full before pushing to the stack. |
peek() | This returns the top value of the stack. First check the stack is not empty by looking at the value of the top pointer. |
pop() | This removes and returns the top value of the stack. This first checks if the stack is not empty by looking at the value of the top pointer. |
size() | Returns the size of the stack |
isFull() | Checks if the stack is full and returns the boolean value, this compares the stack size to the top pointer. |
Stacks use a pointer which points to the top of the stack, where the next piece of data will be added (pushed) or the current piece of data can be removed (popped)
Adding & Removing Data From a Stack
Pushing Data to a Stack
When pushing (adding) data to a stack, the data is pushed to the position of the pointer
Once pushed, the pointer will increment by 1, signifying the top of the stack
Since the stack is a static data structure, an attempt to push an item on to a full stack is called a stack overflow
Visual Example
This would push Bunny onto the empty stack
This would push Dog to the top of the stack
This would push Ant to the top of the stack
Popping Data From a Stack
When popping (removing) data from a stack, the data is popped from the position of the pointer
Once popped, the pointer will decrement by 1, to point at the new top of the stack
Since the stack is a static data structure, an attempt to pop an item from an empty stack is called a stack underflow
Visual Example
This would pop Ant From the top of the stack. The new top of the stack would become Dog
Note that the data that is ‘popped’ isn’t necessarily erased; the pointer 'top' moves to show that Ant is no longer in the stack and depending on the implementation, Ant can be deleted or replaced with a null value, or left to be overwritten
Worked Example
Stacks and queues are both data structures.
A stack is shown below before a set of operations are carried out on it.
Draw what the stack shown below would look like after the following operations:
pop(), push(“A”), push(“B”), pop(), push(“E”), push(“F”)
Pointer | Data |
→ | Z |
| Y |
| X |
2 marks
Answer:
Start by using the operation pop() to remove Z from the top of the stack
Pointer | Data |
→ | Y |
| X |
Use the operation push(“A”) to add A to the top of the stack
Pointer | Data |
→ | A |
|---|---|
| Y |
| X |
Then use the operation push(“B”) to add B to the top of the stack
Pointer | Data |
→ | B |
|---|---|
| A |
| Y |
| X |
Then use pop() to remove the top item in the stack
Pointer | Data |
→ | A |
|---|---|
| Y |
| X |
Then use push(“E”) to add E to the top of the stack
Pointer | Data |
→ | E |
|---|---|
| A |
| Y |
| X |
Finally use push(“F") to add F to the top of the stack
Pointer | Data |
→ | F |
|---|---|
| E |
| A |
| Y |
| X |
F at the top of the stack with E directly below it [1]
A,Y,X. directly below E (with no other entries) [1]
F |
E |
A |
Y |
X |
You've read 0 of your 0 free revision notes
Get unlimited access
to absolutely everything:
- Downloadable PDFs
- Unlimited Revision Notes
- Topic Questions
- Past Papers
- Model Answers
- Videos (Maths and Science)
Did this page help you?