A stack is an .
It has interesting behaviour - LAST IN FIRST OUT - LIFO
We can PUSH items onto the TOP of the stack.
We can POP items from the stack and then update the TOP of the stack.
Check out this simulation in which a stack is implemented on a static 1-dimensional array of length 5.
Stack
| 4 | ||
| 3 | ||
| 2 | ||
| 1 | ||
| 0 |
TOP
-1
Note: these observations are for the above simulation. There are subtle variations on how to process a stack, but the LIFO behaviour is always the same.
A stack is an Abstract Data Structure.
It stores a set of related data and...
... it has methods available to manipulate the data structure.
In this course, those methods are:
In this unit we will consider stacks from a conceptual, pseudocode perspective. We will also consider how to implement a stack using a static array, using Java to help out.
Before we do any of that, let's look at the nature of a stack:
As you can see, we can push data onto a stack.
We can also pop the last item off the stack.
This is known as LAST IN, FIRST OUT behaviour (LIFO).
What happens if you try to pop from an empty stack?
A stack, STACK, exists. It stores only integers.
The following algorithm will push 5 random numbers onto the stack:
loop i from 0 to 4
input randNum
STACK.push(randNum)
end loop
A stack, STACK, exists. It stores only integers.
The following algorithm will pop each item in STACK into a static array, nums:
//precondition: nums has enough elements to hold each item in STACK
i = 0
loop while not STACK.isEmpty()
item = STACK.pop()
nums[i] = item
i = i + 1
end loop
A stack, STACK, exists. It stores Strings.
Another data structure, an array of 10 Strings exists.
An algorithm processes the array. If any of the Strings have a length greater than 5, they are pushed onto the stack.
Write this algorithm in pseudocode.
A stack, STACK, exists. It stores Strings.
In order to interact with each String, they must be popped off the stack.
This really means that we are destroying the stack in order to process it.
Can we discard elements of the stack which have a length greater than 5, and rebuild the stack in the original order with the remaining elements?
Using your own knowledge of arrays and stacks, design an algorithm in pseudocode to solve this problem.
We can implement a stack by using a 1D-array, as simulated above.
Let's take a look at a version of a Stack class in Java and consider its 3 behaviours.
We could imagine the design of the isEmpty() method in the Stack class in a Java program:
public boolean isEmpty(){
if(topOfStack == -1){
return true;
}else{
return false;
}
}
We can also imagine the design of the pop() method in the Stack class in a Java program:
public int pop(){
int item = stack[topOfStack];
topOfStack = topOfStack - 1;
return item;
}
Note: this adaptation returns the item at the top of the stack.
What about implementing the push() method?
Note, we cannot push if topOfStack has reached the end of the array!
THINK before you push the button! What's your idea?
public void push(int item){
}
This might be an opportunity to test and review your coding skills.
Design the Stack class in your IDE.
In another class, construct an instance of a Stack and write a program to push and pop items from it.
One use of Stacks is to implement a recursive algorithm.
The latest recursive call is pushed on the stack.
Each call is popped off the stack when the base case is reached and the recursion unwinds.
public static int mystery(int n) {
if (n <= 1) {
return 1;
} else {
return n * mystery(n - 2);
}
}
mystery(7)? Show your working.Here is another stack simulation. With this one, the top of the stack is always the next available element, not the latest element.
stack array push pop lifo full empty