IB Computer Science HL Topic 5 Stacks and Queues

In the topic 5 of IB we have already covered 2 dimensional arrays and Recursion. We have left to cover other abstract data structures like stacks, queues, linked lists and Binary trees.

These Abstract Data Structures (ADS) are ways to store data. We have already in SL covered collections and 1 dimensional arrays.

Why does this matter?

This matters because we want to acces the data or modify as fast as possible. In order to understand this we need to review what is Big O Notation that we have already covered.

Remember collections that we have these methods

1. AddItem() that adds an item to the collection
2. hasNext() that returns true if we can still loop through the collection checking where is the cursor of the collection.
3. getNext() that returns the next element and moves the cursor (doesn't delet anything)
4. resetNext() that resets the cursor.

Recomended summary video

https://www.youtube.com/watch?v=wjI1WNcIntg

Stacks

Stacks are sets of elements with a particular order that allow access only to the last item inserted.

They are a linear data structure (elements go one after the other) flexible data structure (we can shrink or increase its size).

A stack is a Last-In First-Out (LIFO) data structure

They are a linear data structure (elements go one after the other) flexible data structure (we can shrink or increase its size).

In IB (And in general) stacks have 3 main methods (They may have different names in different implementations)

1. push() that inserts one element onto a stack
2. pop() that removes the last element entered on the stack and returns it
3. isEmpty() that tests if a stack is empty. Returns a boolean. True if it's empty and fals if it's not. Is used to loop through an stack.

Other methods that are common in stacks

• peek() will return the last element entered on the stack without removing it.

stack of plates

When to use a stack

Mainly when we know that the most visited element is going to be the last inserted. For example, if we are in web browser or any editting tool, we may have a stack of the last steps that we have done. So when we undo them, we can access to them quickly.

Function stacks

Let's say that we have this mathematical operation:

$$3·2+(13/160{)}^2$$

//example with arduino morsecode

Also microprocessors (link to topic 2 and 6) usually have a stack for methods. Remember when we have a recursive method?

Something like fibonacci(3) that calls fibonacci (2) that calls both fibonacci(1) and fibonacci(0).

fibonacci(n)
    if (n<2) then
        return 1
    else
    return fibonacci(n-1)+fibonacci(n-2)
end method

When this happens in memory we have a stack. In this case let's go step by step

First, fibonacci(3) is going to be pushed to the stack when is called fibonacci (2).

Then fibonacci(2) is going to be pushed to the stack when is called fibonacci (1) called.

Then fibonacci(1) is called and it will return (1). At the time of returning Fibonacci(2) is going to be poped from the stack to add the 1 returned from fibonacci(1).
Then fibonacci(2) is going to be pushed (again) back to the stack when is called fibonacci(0).
Then fibonacci(0) is going to be called and it will return (1).
Then fibonacci(2) is going to be poped (again) from the stack to add 1 that was returned from fibonacci(0).
Then fibonacci(2) is going to finish and return 2.
Then fibonacci(3) is going to be poped from the stack to add the 2 value from fibonacci(2).
Then fibonacci(3) is going to be pushed (again) back to the stack when is called fibonacci(1).
Then fibonacci(1) is called and it will return (1).
Then fibonacci(3) is going to be poped (again) from the stack to add 1 that was returned from fibonacci(1).
Finally fibonacci(3) will return 2+1.

Exercise

Create the stack process of fibonacci(6) using the array implementation of a stack in this web.

https://www.cs.usfca.edu/~galles/visualization/StackArray.html

Solution done with excel in the spoiler

In the spoiler we're going to compare also the same logarithm with or without caché. In this case the caché is having in memory previous results of the same function. It's going to take also some memory but it's going to be way faster.

Finding fibonacci (6) without a caché
```
Working elment 6
Call stack

​Working elment	5								

Call stack
6

​Working elment	4								

Call stack
6 5

​Working elment	3								

Call stack
6 5 4

​Working elment	2								

Call stack
6 5 4 3

​Working elment	1								

Call stack
6 5 4 3 2

​Working elment	0								

Call stack
6 5 4 3 2

​Working elment	3								

Call stack
6 5 4

​Working elment	1								

Call stack
6 5 4 3

​Working elment	4								

Call stack
6 5

​Working elment	2								

Call stack
6 5 4

​Working elment	1								

Call stack
6 5 4 2

​Working elment	0								

Call stack
6 5 4 2

​Working elment	5								

Call stack
6

​Working elment	3								

Call stack
6 5

​Working elment	2								

Call stack
6 5 3

​Working elment	1								

Call stack
6 5 3 2

​Working elment	0								

Call stack
6 5 3 2

​Working elment	3								

Call stack
6 5

​Working elment	5								

Call stack
6

​Working elment	6								

Call stack

​Working elment	4								

Call stack
6

​Working elment	4								

Call stack
6
Working elment 4
Call stack
6

​Working elment	3								

Call stack
6 4

​Working elment	2								

Call stack
6 4 3

​Working elment	1								

Call stack
6 4 3 2

​Working elment	0								

Call stack
6 4 3 2

​Working elment	3								

Call stack
6 4

​Working elment	1								

Call stack
6 4 3

​Working elment	4								

Call stack
6

​Working elment	2								

Call stack
6 4

​Working elment	1								

Call stack
6 4 2

​Working elment	0								

Call stack
6 4 2

​Working elment	4								

Call stack
6

​Working elment	6								

Call stack

END

With a cache

Finding fibonacci (6) with a caché

​Working elment	6								

Call stack

​Working elment	5								

Call stack
6

​Working elment	4								

Call stack
6 5

​Working elment	3								

Call stack
6 5 4

​Working elment	2								

Call stack
6 5 4 3

​Working elment	1								

Call stack
6 5 4 3 2

​Working elment	0								

Call stack
6 5 4 3 2

​Working elment	3								

Call stack
6 5 4 3

​Working elment	1								

Call stack
6 5 4 3

​Working elment	3								

Call stack
6 5 4

​Working elment	4								

Call stack
6 5

​Working elment	2								

Call stack
6 5 4

​Working elment	5								

Call stack
6

​Working elment	3								

Call stack
6 5

​Working elment	5								

Call stack
6

​Working elment	6								

Call stack

​Working elment	4								

Call stack
6

​Working elment	6								

Call stack

END

#### Extra 

How to write the fibonacci function with an iteration 

https://masqueprogramar.wordpress.com/2016/12/29/fibonacci-iterativo/

Important: IF THEY ASK THIS DON'T USE RECURSION! 

Stacks in execution threads

Algorithms using stacks

To look for an element into a stack we're going to use a while loop and a flag variable.

In this case we're going to do it in a way that is destructive, the stack is not going to be the same after the search.

S //stack
FOUND = false
loop while (S.isEmpty() == false AND FOUND == false)
    element = S.pop()
    if (element == condition) then
        FOUND = true
        //do whatever, return, output etc
    end if
end loop

What we can do for putting everything back together is to use a stack for storing the elements that we are poping. Once the search has ended we push the elements back in their place.

S //stack
FOUND = false
S2 // new empty stack
loop while (S.isEmpty() == false AND FOUND == false)
    element = S.pop()
    S2.push(element)
    if (element == condition) then
        FOUND = true
        //do whatever, return, output etc
    end if
end loop
loop while NOT S2.isEmpty()
    S.push(S2.pop())
end loop

Simple exercise with stacks (Outputs)

Let's create a stack and say the output of these exercise with vegetables

pak choi

S // stack
S.push("potato")
S.push("lettuce")
S.push("pak choi")
S.push("tomato")
S.pop()
S.push("carrot")
output(S.pop())
C= S.pop()
output(S.pop())
S.push(C)
S.push(C)
output(S.pop())

What would be the output of this algorithm?

Solution on the spoiler

carrot,
lettuce,
pak choi

What would be the contents of the stack by the end of this algorithm?

The last element would be another copy of "pak choi" and the first element would be the potato.

Simple exercise with stacks (find info)

Imagine that we have a stack with information about vegetables called VEGGIES. We need to find how many vegetables in that stack are "carrot" (and output them)

First way to do it is destructive since we're going to mess with the stack.

What do we mean by destructive

In stacks and queues, unlike arrays, looping trough them is going to actually change them and even delete them completely if we're not careful. That's why we may have destructive algorithms that we're going to use when we don't care about how is the stack or queue after the execution and non destructive algorithms that are going to set the elements as they were before their execution of the algorithm.

For that we need a COUNT

VEGGIES // stack
COUNT = 0
loop while not VEGGIES.isEmpty()
    element = VEGGIES.pop()
    if element == "carrot" then
        COUNT = COUNT + 1
    end if
end loop
output COUNT

One student answer with this algorithm. (Thank you, anonymous student)

Can you find what is wrong with this algorithm? (Solution in the details)

This algorithm is never going to stop in the case that we find a "carrot"

We could get more one liners with this implementation:

VEGGIES // stack
COUNT = 0
loop while not VEGGIES.isEmpty()
    if  VEGGIES.pop()== "carrot" then
        COUNT = COUNT + 1
    end if
end loop
output COUNT

But sometimes in other (more complex) programs we actually need to do more than 1 thing to the elements that we pop so for not messing it up I suggest to use the former version.

What would be to do something else with that element? In case of being an object, check a couple of their properties. (Such as ID and age, for example). In other cases maybe we need to store 2 elements because we want to check how we add them together. Other cases are 2 conditions or more (a number bigger than some threshold but lower than other threshold)

Now the non-destructive version:

VEGGIES // stack
S // empty stack
COUNT = 0
loop while not VEGGIES.isEmpty()
    element = VEGGIES.pop()
    S.push(element)
    if element == "carrot" then
        COUNT = COUNT + 1
    end if
end loop
loop while not S.isEmpty()
    VEGGIES.push(S.pop())
end loop
output COUNT

Simple exercise of searching a stack with 2 conditions.

Imagine that we have a stack with the latests grades of IB. We need to count how many of them are between 24 and 30 marks.

The stack is called IBGrades.

The destructive version:

IBGrades // stack
COUNT = 0
loop while not IBGrades.isEmpty()
    GRADE = IBGrades.pop()
    if  GRADE > 23 AND GRADE < 31 then
        COUNT = COUNT + 1
    end if
end loop
output COUNT

This is wrong!

IBGrades // stack
COUNT = 0
loop while not IBGrades.isEmpty()
    if  IBGrades.pop() > 23 AND IBGrades.pop() < 31 then
        COUNT = COUNT + 1
    end if
end loop
output COUNT

Because you're comparing 2 different grades since everytime that you call IBGrades.pop() you're changing the element that you're working with!

The non-destructive version of the algorithm:

credit Y.C.

Count how many elements (in total) we have in an stack

We want to know how many elements we have in a certain stack at a certain moment (without destroing it).

S //stack
COUNT (counter)
S2 //temporary stack
loop while (S.isEmpty() == false)
    S2.push(S.pop())
    COUNT = COUNT +1
end loop
loop while (S2.isEmpty()== false)
    S.push(S2.pop())
end loop
ouput COUNT

Queues

Queues are sets of elements with a particular order that allow access only to the first item inserted.

They are a linear data structure (elements go one after the other) flexible data structure (we can shrink or increase its size).

A stack is a First-In First-Out (FIFO) data structure

In IB (And in general) stacks have 3 main methods (They may have different names in different implementations)

1. enqueue() that inserts one element into the end of the queue
2. dequeue() that removes the first element entered on the stack and returns it
3. isEmpty() that tests if a queue is empty. Returns a boolean. True if it's empty and fals if it's not. Is used to loop through an queue.

Applications of queues

• Simulation of real queues (duh)
• Response queues. When you ask something to a server, it usually will put it into a queue. The first query that it gets is usually the first response that it will create.
• Sending data packets (topic 3 link)
• Printer queues

Algorithms using queues

To look for an element into a queue we're going to use a while loop and a flag variable.

In this case we're going to do it in a way that is destructive, the queue is not going to be the same after the search.

Q //queue
FOUND = false
loop while (Q.isEmpty() == false AND FOUND == false)
    element = Q.dequeue()
    if (element == condition) then
        FOUND = true
        //do whatever, return, output etc
    end if
end loop

Can we write directly if Q.dequeue()== condition?

Yes, but the problem is that in some other context you may have to do more than one thing (or one condition) so if you call Q.dequeue twice you're getting 2 different elements (is the same problem with getNext() in collections) so to avoid it I tend to put the element that I'm going to compare in a variable.

Implenting a queue or a stack using an array

Remember that implementation means that how to find a solution. There can be many. To implement a stack we can use several ways. For example in the video from before:

You can see an implementation of a stack and a queue using OOP in java.

Now since you know how arrays work let's see how we can implement (in pseudocode) a stack o a queue.

Implement a stack using an array

Remember that in an array in many algorithms that you see in IB we're keeping track of how filled is a fixed length array using a varible of "counter" or "index" or "POTATO_COUNT".

So for doing this trick we are going to use an array and implement the methods that we have using variables for those indexes. In the case of Stacks the relevant is TOP

ARRAY[N] //array of fixed N elements
TOP = 0 //we asume that we start that the top is first 0 in this implementation. We can go also that if the stack is empty, TOP = -1. In this case TOP counts how many elements we have in our stack

The methods that we need to implement to make it work are:

push(data), pop() and isEmpty()

isEmpty()

method isEmpty()
    if TOP > 0 then
        return false
    else
        return true
    end if
end method

push(data)

In this case we're supposing that we have enough space in our array

method push(data)
    ARRAY[TOP] = data
    TOP = TOP + 1
end method

pop()

In this case we're supposing that we have elements in our stack

method pop()
    TOP = TOP -1
    return ARRAY[TOP]
end method

Implement a queue using an array

(Resource)

In this case we need 2 variables. HEAD (head of the queue, the element that is going to be first out) and TAIL, the last element that we have enqueued.

In this case there are more nuances, so fasten your seatbelts

ARRAY[N] //array of fixed N elements
HEAD = 0 // the index where is going to be the first element to take out. 
TAIL = 0 //the index where we're going to put the next element

isEmpty()

This is the easiest one

method isEmpty()
    if TAIL == HEAD then 
         return true
    else 
        return false
    end if
end method

enqueue(data)

method enqueue(data)
    ARRAY[TAIL] = DATA
    TAIL = TAIL +1
end method

dequeue

method dequeue
    ANSWER = ARRAY[HEAD]
    HEAD = HEAD + 1
    return ANSWER
end method

Exercise with a Queue

We have a printer job queue called PQ. These jobs have the method "isColor()" that is going to return TRUE in case they are a color job and FALSE otherwise (mainly black and white copies)

Construct in pseudocode an algorithm that finds and outputs how many elements of this queue (PQ) are in color, then reconstruct the queue (we don't want to disturb that queue!). You may use the method "isColor()" described before.

Is very common in IB exams they describe you briefly a new function and what it does and you should be able to grasp it and use it.

PQ //queue
PQ2 // second empty queue
COUNTER = 0
loop while NOT PQ.isEmpty()
    C.PQ.pop()
    if C.isColor() then
        COUNTER = COUNTER + 1
    end if
    PQ2.push(C)
end loop
PQ = PQ2 //restore the original queue 
OUTPUT COUNT //Don't forget to output!

In the case of queues we don't need a second loop because the second queue is going to have the exact same order as the first (due to the FIFO structure)

Exercises with queues and stacks

How to reverse a stack with a queue algorithm

I have seen this question in one of the exams as "description"

For doing this we need to loop through the stack and put everything into a queue. Then dequeue and fill the stack again.

For example

S //Stack to reverse
Q //Auxiliary empty queue
loop while S.isEmpty() == false
    Q.enqueue(S.pop())
end loop
loop while Q.isEmpty() == false
    S.push(Q.dequeue())
end loop

Remember that when we write S.push(Q.dequeue()) we are pushing to the stack S what we retrieve from dequeueing in the queue Q

How to reverse a queue with a stack

[ Exercise for the students, do the description AND the pseudocode ]

Description:

In order to reverse the queue, we first create an empty stack S. Then, we start a loop while the queue Q is not empty, where the elements will be pushed into the stack S while they are dequeued from the queue Q. Finally, we create another loop while the stack S is not empty, and we enqueue the elements from queue Q, meaning that they are popped from stack S. Since they are popped from a stack, their order will change as the last one will become the first one. As a result, the queue will be reversed.

credit Y.C.

Pseudocode

credit Y.C

Remember that when we write Q.enqueue(S.pop()) we are enqueuing in the queue Q what we retrieve from popping the Stack S

References

Implementation of stacks in Java
https://www.geeksforgeeks.org/stack-class-in-java/

Array implementation of a stack

https://www.cs.usfca.edu/~galles/visualization/StackArray.html