A-level Computing/AQA/Paper 1/Fundamentals of data structures/Stacks
A stack is an ADT that might involve a dynamic or static implementation. A stack is a last-in-first-out (LIFO) or first-in-last-out (FILO) ADT. Implementations should include two operations, pushing and popping, and a pointer to the top of the stack.
A real life example is a stack of books you might have on your desk:
Let's take a look at a computer implementation of a stack:
- Pushing: Adds a new specified item to the top of the stack
- Popping: Removes the item from the top of the stack.
| State 1 | State 2 | State 3 | State 4 | State 5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Push 'elephant' | Push 'hippo' | Push 'zebra' | Pop | Push 'flamingo' | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
Note the data isn't 'deleted' |
|
Stacks have several uses:
- Reversing queues (as seen above with the Alphabetised names)
- Performing Reverse Polish Calculations (see ....)
- Holding return addresses and system states for recursive function calls
|
Exercise: Stacks Draw the stack after each of the following commands, starting with an empty stack. What does the stack achieve:
Answer:
This set of instructions used the stack to input data in order and then output it in reverse order Give the set of instructions required to get from State 1 to State 2 as shown below:
Answer:
If we have an empty Stack what do we set the pointer TopOfStack to? Answer: 0 or null Describe the Stack data type: Answer: A stack is a First In Last Out or Last In First Out data type Give two uses for a Stack in a computer: Answer:
|
Dim myStack(10) as string
Dim ToS as integer = 0 'this is our pointer
Dim item as string
While item <> “#”
Console.writeline(“please insert item ” & ToS & “ into the stack: ”)
item = Console.readline()
myStack(ToS) = item
ToS = ToS + 1
End While
For x = ToS to 0 step -1
Console.writeline(“Stack item: ” & x & “ = ” & myStack(x) )
Next
console.readline()