Stacks and Queues: Properties, Operations, and Applications

DATA STRUCTURES
4.1 STACKS AND QUEUES

WHAT ARE STACKS AND QUEUES

Stacks and queues are similar in nature to lists or arrays in programming, the both hold data in a linear way and both can have data added and removed. Stacks and queues are two methods of handling data flow. The main difference between stacks and queues is how the data is taken (popped) from each.
Stacks have a Last In First Out structure - LIFO
Queues have a First In First Out structure - FIFO

STACKS LIFO STRUCTURE

With a LIFO stack the last item of data in to the stack is always the first item of data out. To illustrate this, imagine piling books on top of each other, the last book you placed(at the top of the pile) is the first book you will pick up, even if you want to read the book from the bottom of the pile you would need to remove (pop) each book above it first. This is known as Last In First Out (LIFO)

You can only put in or take out one item at a time in the stack. If you want to access the third item in the stack you would have to remove the first item, then remove the second item before you could access the third item.

Stack are used in many computational processes such as the Polish and Reverse Polish notation discussed later on this page, they are are used for everyday processing such as an undo function in a program, the last thing you did will be at the top of the stack therefore when you click undo that is the first item to be removed, hence actuating the undo feature.

There are many features of stacks however 3 methods that are popular and common to A-Level and IB Computer Science are:
✓ push(item) add item to the top of the stack
✓ pop() remove and return the item from the top of the stack
✓ isEmpty() return true or false depending on the items in the stack

We can easily simulate a stack in Python or Java using Lists and Arrays. For example in Python to to insert an item to the top (end) of a list you can use the append method, to remove an item from the top(end) of a list you can use the pop method. Below shows some examples in both Python and Java simulating these three methods, push(), pop() and isEmpty().

STACK METHODS IN PYTHON

PUSH METHOD IN PYTHON
Copy and try the code below, the append method is simulating a stack push by adding an item to the last(top) of the list one at a time.

myStack = []

myStack.append("Bob")
myStack.append("Jill")
myStack.append("Jane")
print (myStack)

POP METHOD IN PYTHON
Copy and try code below. the pop() method pops(removes) the last(top) item in the list.

myStack = ["Bob","Jane","Jill"]
myStack.pop()
print(myStack)

ISEMPTY METHOD IN PYTHON
Copy and try the code below, this is one way to simulate a stack isEmpty method in python.

myStack = []
if not myStack:
   print ("The Stack is Empty")

QUEUES FIFO STRUCTURE

With a FIFO queue the first item of data in to the queue is always the first item of data out. To illustrate this, imagine a queue at a coffee shop, the person at the front of the queue if the first to get processed, new people join the back of the queue and work their way to the front at other customers are processed, they cannot jump the queue at any point. This is known as First In First Out (FIFO)

There are many features of queue however 3 methods that are popular and common to A-Level and IB Computer Science are:
✓ enqueue() add item to the end of the queue
✓ dequeue(queue location 0) remove and return the item from the front of the queue
✓ isEmpty() return true or false depending on the items in the queue

QUEUE METHODS IN PYTHON

ENQUEUE METHOD IN PYTHON
We can you the same method as the stack to place an item at the end of the queue, Copy and try the code below, the append method is simulating a queue enqueue by adding an item to the last position of the list one at a time.

myQueue = []

myQueue.append("Bob")
myQueue.append("Jill")
myQueue.append("Jane")
print (myQueue)

DEQUEUE METHOD IN PYTHON
Like used in the stack, we can also use the pop() method to remove the item at the front of the queue, the difference being we now need to stipulate the position of the item, the item at the front of the queue will always be position zero. Copy and try code below.

myStack = ["Bob","Jane","Jill"]
myStack.pop(0)
print(myStack)

ISEMPTY METHOD IN PYTHON
Copy and try the code below, this is one way to simulate a Queue isEmpty method in python.

myQueue = []
if not myQueue:
   print ("The Queue is Empty")

What is a stack data structure and how does it differ from a queue data structure?
What is the principle behind the Last-In-First-Out (LIFO) method of a stack?
How does the push and pop operations work in a stack?
What are the applications of stack data structures in computer science?
What is the difference between a static stack and a dynamic stack?
What is the First-In-First-Out (FIFO) method of a queue data structure?
How does enqueue and dequeue operations work in a queue data structure?
What are the advantages of using a queue data structure over a stack data structure?
How can a queue data structure be implemented in real-life situations, such as printing jobs or process management in an operating system?
What is the difference between a linear queue and a circular queue, and in what cases would one be preferred over the other?

NEXT: LINKED LISTS

POLISH NOTATION (A-LEVEL ONLY)

This section shows how data can be processed by the computer and give a brief explanation of why the order that we notate traditional mathematic equations is not very efficient for the computer processor.

Whilst Polish notation is discussed in the processor fundamentals section, the principle is also relevant in the understanding of Stacks and Queues and how data can be processed effectively.

What is Polish Notation? Polish notation is a method of passing in to the processor mathematical equations in an order and format that can be processed effectively. If we think of each element of an equation being held in a stack ready to be processed we start to see how the order that the processor receives each part of the equation and the removal of parentheses speeds up processing.

In normal mathematic expressions the operator has an infix position for example in addition the plus sign + is noted in between the two numbers. For example: 5 + 4

However it is often inefficient for the processor to process a calculation in this way there Polish notation is used. Polish notation simply places the operator before the numbers to process. For Example + 5 4.

With reverse polish notation the operator will be placed a after the numbers to process, for example 5 4 +

All three expressions above yield the same result:
5 + 4 = 9
+ 5 4 = 9 (Polish Notation)
5 4 + = 9 (Reverse Polish Notation)

Using parentheses (or parentheses binary notation) is not efficient for the processor. In the expression below the parentheses are moved and reverse polish notation is used to give the same result. The processor needs to process calculations in a simple left to right order, when we as humans calculate infix expressions we will look for the parentheses, work these parts out first then go back and work out the rest and put the calculation together, the process of going back to part of a calculation is not very effective for the process and how the data is fed to the processor in the form of a stack mean that the ability to calculate in one single left to right flow of data is the most effective way for the processor to work.

(5 + 4) * 7 = 63

In Reverse Polish Notation: 5 4 + 7 *
For further information on RPN Click Here to watch ( AQA A’Level Reverse Polish Notation - Part 1, by, craigndave Published on Feb 7, 2018.)

Examples of Reverse Polish Notation

Further information can be found here ( Assembly language and machine code - Gary explains!)

NEXT: LINKED LISTS