# Data Structures

Before we begin, recall that defining a function with `type` instead of `var` and `const` simply ensures that the `typename` of the returned object is the same as that of the function. (Calling `info()` on the object will expose its typename, so we can do some basic runtime type checking if we need to)

It's good practice to define all constructor functions (functions that define and return an object) with the keyword `type`.

### Stack

We'll begin with the most basic structure, the Stack.

{% code title="stack.vtx" overflow="wrap" %}

```rust
type Stack = (max = None) => ({
    data: [],
    max: max,
    push: (x) => {
        if (!this.max or (this.data.length() < this.max)) {
            this.data.append(x)
        }
    },
    pop: () => {
        var value = this.data[this.data.length()-1]
        this.data.remove(this.data.length()-1)
        return value
    },
    clear: () => {
        this.data = []
    },
    size: () => this.data.length(),
    front: () => this.data[this.data.length()-1],
    back: () => this.data[0]
})
```

{% endcode %}

Now that we've defined our Stack constructor, we can go ahead and use it to generate a new Struct object.

{% code title="stack.vtx" overflow="wrap" %}

```rust
const s = Stack()

s.push(0)
s.push(1)
s.push(2)

println(s.data) // [0, 1, 2]

s.pop()
s.pop()

println(s.data) // [0]
```

{% endcode %}

Great, we were able to successfully push and pop off our new stack.

Note that we also provided a parameter (max) to our constructor, and defaulted it to `None`.

Since we constructed the stack without providing a value to `max`, our stack can get infinitely large (within the limits of of the physical realm, of course). Let's try creating a stack with a specified max size.

{% code title="" overflow="wrap" %}

```rust
const limited_s = Stack(3)

limited_s.push(0)
limited_s.push(1)
limited_s.push(2)
limited_s.push(3)
limited_s.push(5)

println(limited_s.data) // [0, 1, 2]
```

{% endcode %}

We've successfully capped our stack!

### Queue

Let's move on to a slightly different data structure: Queue

Queues are different to Stacks in that they are First In, First Out rather than First In, Last Out.

{% code title="queue.vtx" overflow="wrap" %}

```rust
type Queue = (max = None) => ({
    data: [],
    max: max,
    enqueue: (x) => {
        if (!this.max or this.data.length() < this.max) {
            this.data.append(x)
        }
    },
    dequeue: () => {
        var value = this.data[0]
        this.data.remove(0)
        return value
    },
    clear: () => {
        this.data = []
    },
    size: () => this.data.length(),
    front: () => this.data[0],
    back: () => this.data[this.data.length()-1]
})
```

{% endcode %}

The only real difference is that instead of pushing and popping, we are enqueuing and dequeuing.

{% code title="queue.vtx" overflow="wrap" %}

```rust
const q = Queue()

q.enqueue(0)
q.enqueue(1)
q.enqueue(2)

println(q.data) // [0, 1, 2]

q.dequeue()
q.dequeue()

println(q.data) // [2]
```

{% endcode %}

As with the Stack, we can also set a max size by passing in a number to the `max` parameter on construction.

### Priority Queue

Now for something a little more complicated, a Priority Queue.

A priority queue maintains a sorted list from high priority to low priority.

{% code title="pqueue.vtx" overflow="wrap" %}

```rust
import [] : functional

type PriorityQueue = (max = None) => ({
    data: [],
    max: max,
    enqueue: (value, priority = 0) => {
        if (!this.max or (this.data.length() < this.max)) {
            var _value = [value, priority]
            this.data.append(_value)
            this.data = this.data.sort((a, b) => a[1] < b[1])
        }
    },
    dequeue: () => {
        var value = this.data[0][0]
        this.data.remove(0)
        return value
    },
    clear: () => {
        this.data = []
    },
    get: () => this.data.map((e) => e[0]),
    size: () => this.data.length(),
    front: () => (this.data[0])[0],
    back: () => (this.data[this.data.length()-1])[0]
})
```

{% endcode %}

This time, every time we enqueue a value, we need to pass alongside it a priority value. The queue then sorts the value into its correct spot.

Bear in mind, this is a naive implementation of a priority queue, and there exist more complex and efficient algorithms than simply sorting on enqueue.

Notice we also provide a `get` function that returns our values without their priorities. We needed to import `functional` to make use of `map` here.

{% code title="pqueue.vtx" overflow="wrap" %}

```rust
const q = PriorityQueue()

q.enqueue("A", 1)
q.enqueue("B", 2)
q.enqueue("C", 1)
q.enqueue("D", 0)

println(q.get()) // [D, A, C, B]
```

{% endcode %}

Let's walk through the flow.

We add "A" with a priority of 1 ->  \["A"]

We add "B" with a priority of 2 -> \["A", "B"]

We add "C" with a priority of 1 -> \["A", "C", "B"]

We add "D" with a priority of 0 -> \["D", "A", "C", "B"]

And just like that, we've built out three useful structures that you can re-use in your own codebase!

Copy the code and modify it to experiment with how things work.

If you wanted to type check a value before adding it to the Stack or Queue, how would you do it? (Hint: check out the list of [built-in functions](/vortex-docs/language-reference/built-in-functions.md) for the answer)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dibs.gitbook.io/vortex-docs/examples/data-structures.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.