x

Stacks

Main info

·         Can be implemented within an array

·         Dynamic data structure

·         Data cannot be directly accessed.

Properties of a stack

·         If a stack is empty, TOP = 0

·         The TOP variable defines how many elements there are in a stack

·         Items are pushed (added) to a stack

·         Items are popped (removed) from a stack

·         If the stack becomes full, no more data can be added to it without first removing some data (overflow error)

·         E.G. If you try and store the value 384 in a byte, which is impossible because a byte can only hold a maximum value of 255

How stacks are used in computers

·         If an interrupt happens in a CPU, then the CPU needs to drop all the tasks it is doing and complete the interrupt handling routine

·         The tasks it is doing beforehand need to be continued after the interrupt, and therefore it needs to store these instructions before they are dropped by the CPU

·         In this case, a stack is used to store the important instructions (in registers)

·         When the interrupt handling routine is finished, it pops all the instructions back into the registers and the CPU carries on what it was doing beforehand

Reversing a stack

·         In a queue, elements are added to the back and removed from the front like a supermarket queue

·         To reverse a queue, push all the elements in the queue onto the stack

·         Then, pop all the elements out of the stack and onto the queue, one by one

·         The queue is now reversed

Left-click: follow link, Right-click: select node, Scroll: zoom
x