Stacks

Stacks

What is a stack?

• Stacks are 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

Operation	Description
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

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

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