# Appendix

There are also other foundational data structures.

(stack)=
## Stack

:::{commons-figure} https://commons.wikimedia.org/wiki/File:Tallrik_-_Ystad-2018.jpg
:figwidth: 30%
:align: right
A stack of plates. We must take plates on the top to reach plates below.
:::


Previously we talked about {ref}`static-and-stack-based-memory`. C uses it to execute a chain of functions. In contrast, we will talk about how we can use a stack-based data structure to solve data processing problems.

:::{wpd} stack (abstract data type)
a collection of elements with two main operations:
1. push
1. pop
:::

The elements are managed in a *last-in-first-out (LIFO)* manner.

:::{commons-figure} https://commons.wikimedia.org/wiki/File:Lifo_stack.svg
:figwidth: 70%
Filling and emptying a stack using *push* and *pop* operations, respectively.
:::


## Queue

:::{figure} https://upload.wikimedia.org/wikipedia/commons/5/52/Data_Queue.svg
:figwidth: 40%
:align: right
Filling and emptying a queue using *enqueue* and *dequeue* operations, respectively.
CC BY-SA 3.0. Created by WPUser:Vegpuff. Source [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Data_Queue.svg)
:::


Opposite of a [stack](stack).

:::{wpd} Queue (abstract data type)
a collection of elements with two main operations:
1. enqueue
1. dequeue
:::

The elements are managed in a *first-in-first-out (FIFO)* manner.


Queues or FIFOs play a crucial role not only in the supermarket but also in information processing systems. They can be used to isolate two *chained* systems, where one system's output is other system's output. This isolation allows two systems to operate on different speeds:

<br>

```{mermaid}
flowchart LR
System1 --> Queue -->|data waits until System2 is done| System2
```

<!--
:::{commons-figure} https://commons.wikimedia.org/wiki/File:Queue_System.svg
:align: right
:figwidth: 40%
A queue helps to restrict input to a system.
:::
-->


## Tree

:::{commons-figure} https://commons.wikimedia.org/wiki/File:Tree_(computer_science).svg
:align: right
:figwidth: 40%
In contrast to trees in nature, a tree is drawn upside down. `2` is the root, because it has no parents. `1`, `10`, `5`, `11` and `4` are leaves.
:::

:::{wpd} Tree (abstract data type)
a data type that represents a hierarchical tree structure with a set of connected notes.
:::