Data Structures: Stacks

A stack is a data structure that stores items in last-in, first-out (LIFO) order. Elements are added at the top and removed from the top, like a real-world stack of books. Stacks are used for the history in a web browser and the undo action in word processor.

See more like this Stacks Trees Graphs Queues

Theory

A stack is typically implemented using an array of a fixed size and a pointer that indicates the top item in the stack. When an item is added to the stack, the pointer is incremented, and when an item is removed the pointer is decremented

In the following stack implementation, the top pointer indicates the current item in the stack. When the stack is empty, the pointer is -1. When the stack is full, the pointer is one less than the maximum number of items

Interactive Example and Pseudocode

PUSH POP

						procedure push(item)
						if top == 4
						print("full")
						else
						top = top + 1
						stack[top] = item
						end-procedure
					

						function pop()
						if top == -1
						print("empty")
						return -1
						else
						top = top - 1
						return stack[top + 1]
						end-function
					

In this alternative implementation, the top pointer indicates the next free space in the stack. When the stack is empty, the pointer is 0. When the stack is full the pointer is equal to the maximum number of items. See the differences highlighted below

PUSH POP

						procedure push(item)
						if top == 5 
						print("full")
						else
						stack[top] = item
						top = top + 1
						end-procedure
					

						function pop()
						if top == 0 
						print("empty")
						return -1
						else
						top = top - 1
						return stack[top]
						end-function
					

Check your understanding

Download a worksheet to test your understanding and strengthen your skills!

Browse Worksheets