Data Structures - Stacks and Queues (1.4.2)

This post covers the following topics:

• Stacks

• Queues

Stacks (LIFO)

A stack handles linear lists of data, stacks follow Last-In First-Out (LIFO). This means that the most recent piece of data to be placed onto the stack is the first piece to be taken off of it.

Example of Last-In First-Out (Stack)

To add data to a stack it's pushing to the stack and to take data off the stack it's popping. Stacks can be implemented easily using an array or linked list and a variable to point to the top of the stack. A stack is implemented within memory using pointers.

Example of usig stacks, with pushing and popping and showing the pointers.

Here's an example of a stack implemented within Python:

myStack = ['Edward', 'Emily', 'Peter', 'Sam', 'Empty', 'Empty'] # creates a stack
pointerTop = 3 #points to the element at the top of the stack
def pop( ) : #removes the value from the top of the stack and returns it
	value = myStack[pointerTop]
	myStack[pointerTop] = 'Empty'
	pointerTop = pointerTop – 1
	return value
def push(data) : #adds a new piece of data to the top of the stack
	pointerTop = pointerTop + 1
myStack[pointerTop] = data

If a stack is full then more items shouldn't be appended to the stack otherwise it will cause a StackOverflow error. If the stack has no items and a pop is attempted then it will cause a StackUnderflow error.

The top pointer will address the index which is one higher than the current highest index. So if there is a maximum of 20 elements and there are 10 elements then top points at 10 (as it starts at 0, would be 11 if started from 0 like lua).

Queues (FIFO)

A queue is a First-In First-Out (FIFO) data structure. So the most recent piece of data to be placed in the queue is the last to be taken out. When buying tickets the first person in the queue would be the first person to be able to purchase tickets (for example on AXS when buying tickets for Niall Horan's Dinner Party Live On Tour especially on the 2nd and 3rd of October there is a queue that everyone is in and slowly released into the ticket buying pages).

Data within a queue doesn't move forward physically, instead two pointers are used to denote the beginning and the end of the queue to track data items within the structure.

Just like with stacks there is pushing and popping.

Sources

• https://docs.google.com/presentation/d/1UAtVenHVlJSSRE1Ck7xkpYIt93xq769cgY_ZCsTUDFc/edit?slide=id.p1#slide=id.p1 (Slides 21-29)