# IB Computer Science HL Topic 5 Stacks and Queues

In the topic 5 of IB we have already covered [2 dimensional arrays](/W401zMAJToK7PBiLN1QKnw) 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](/ePOy45OFT0yOOnIMyxtaTw) that we have already covered.

:::warning
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

{%youtube 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).

:::success
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.

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

### 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
:::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.

:::info
**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

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

:::danger
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).

:::success
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

:::info
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:

{%youtube wjI1WNcIntg%}

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](https://www.geeksforgeeks.org/array-implementation-of-queue-simple/))

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

## Exercises with queues and stacks

### How to reverse a stack with a queue algorithm

:::success
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

:::info
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_

:::info
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