Appendix

There are also other foundational data structures.

Stack

Fig. 31 A stack of plates. We must take plates on the top to reach plates below.
CC BY 3.0. By Foto: Jonn Leffmann. Source: Wikimedia Commons

Previously we talked about 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.

stack (abstract data type)

a collection of elements with two main operations:

1. push

2. pop

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

Fig. 32 Filling and emptying a stack using push and pop operations, respectively.
CC0. By Vectorization: Alhadis. Source: Wikimedia Commons

Queue

Fig. 33 Filling and emptying a queue using enqueue and dequeue operations, respectively. CC BY-SA 3.0. Created by WPUser:Vegpuff. Source Wikimedia Commons

Opposite of a stack.

Queue (abstract data type)

a collection of elements with two main operations:

1. enqueue

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

        flowchart LR
System1 --> Queue -->|data waits until System2 is done| System2
    

Tree

Fig. 34 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.
CC BY-SA 4.0. By Paddy3118. Source: Wikimedia Commons

Tree (abstract data type)

a data type that represents a hierarchical tree structure with a set of connected notes.