# LinkedList, Stack and Queue

> LinkedList draws a ListTrace as boxes with a value and a link cell, node by height pixels and gap apart.

Page: https://fframes-kit.pages.dev/docs/computer-science/linked-list-stack-and-queue/
Cargo feature: `cs` (`fframes-kit = { version = "..", features = ["cs"] }`)

`LinkedList` draws a `ListTrace` as boxes with a value and a link cell, `node` by `height`
pixels and `gap` apart. Links are arrows from the link cell to the next node; a link back to
a node on the left dips under the nodes, and a node without a link shows a slash. New nodes
drop in, removed ones drop out, and nodes that pass each other (when a reversed list takes
its new order) swing apart. The pointers, with `head` on the first node, sit above the nodes.
Gallery scene: `LinkedList` (an insert, a find, a remove and a reversal).

Gallery clip of `LinkedList`: https://fframes-kit.pages.dev/media/scenes/LinkedList-0ecfdc0c.mp4

`Stack` piles the items up in a container `capacity` boxes tall, the last item on top with a
`top` marker; pushed boxes drop in, popped ones rise out. `Queue` lines the items up in a
channel `capacity` boxes long, the front at the left, with `front` and `back` markers;
enqueued boxes slide in from the right and dequeued ones leave to the left. A `Stack` with
`indices` writes each box's index left of the container, 0 at the bottom, and `label` names it
under the container. Gallery scenes: `Stack` and `Queue`. The `VariableBox` scene also shows a stack with indices
and a label.

Gallery clip of `Stack`: https://fframes-kit.pages.dev/media/scenes/Stack-96baf98c.mp4

Gallery clip of `Queue`: https://fframes-kit.pages.dev/media/scenes/Queue-d3bc9807.mp4

Build the trace once and pass it to either view:

```rust
use fframes_kit::prelude::*;

fn list<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a ListTrace) -> Svgr<'a> {
    ui.show(LinkedList { trace: Some(trace), step_time: 0.75, ..ui.defaults() })
}

fn stack<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a ListTrace) -> Svgr<'a> {
    ui.show(Stack { trace: Some(trace), step_time: 0.75, ..ui.defaults() })
}
```

```rust
use fframes_kit::prelude::*;

fn queue<'a>(ui: &mut Ui<'a, '_, '_>, trace: &'a ListTrace) -> Svgr<'a> {
    // trace = ListTrace::record(&[4]).enqueue(7).dequeue().finish(), built once
    ui.show(Queue {
        trace: Some(trace),
        delay: 0.5,
        step_time: 0.7,
        capacity: 5,
        ..ui.defaults()
    })
}
```

## API

Components are plain structs. Set the fields you need and fill the rest with `..ui.defaults()`: the defaults below come from the current theme (`theme.` values are fields of `Theme`).

### LinkedList

A linked list: each node a box with its value and a link cell, `node` by `height` pixels and `gap` apart, centred on `center` (units of `ui.space`). Links are arrows from the link cell to the next node; a link that points back to a node on the left dips under the nodes, and a node without a link shows a slash. It plays a [`ListTrace`](https://fframes-kit.pages.dev/docs/computer-science/list-trace.md), one step every `step_time` seconds from `delay`: nodes slide to their places, new ones drop in, removed ones drop out, links fade as they change, and the pointers (`cur`, and `head` with `head`) sit above the nodes. The whole figure fades with `enter` and `exit`.

| Field | Type | Default | Description |
| --- | --- | --- | --- |
| `trace` | [`Option<&ListTrace>`](https://fframes-kit.pages.dev/docs/computer-science/list-trace.md) | `None` | The recorded steps to play (`ListTrace`); `None` draws nothing. |
| `delay` | `f32` | `0.0` | Seconds after the container's start before the first step. |
| `step_time` | `f32` | `0.8` | Seconds each step of the trace takes. |
| `center` | `(f64, f64)` | `(0.0, 0.0)` | The middle of the list, in units of `ui.space`. |
| `node` | `f32` | `120.0` | Width of a node in pixels. |
| `height` | `f32` | `64.0` | Height of a node in pixels. |
| `gap` | `f32` | `60.0` | Space between neighbouring nodes in pixels, where the link arrows run. |
| `head` | `bool` | `true` | Whether the `head` pointer is shown above the first node. |
| `notes` | `bool` | `true` | Whether the step's note is written under the list. |
| `colors` | `CellColors` | `CellColors::themed(theme)` | Colours of the nodes in each state (visited, moved, found). |
| `link_color` | `Color` | `theme.colors.text` | Colour of the link arrows and the slash of a node without a link. |
| `pointer_color` | `Color` | `theme.colors.highlight` | Colour of the pointer names (`cur`, `head`) above the nodes. |
| `value_style` | `TextStyle` | `value_style` | The font of the values in the nodes. |
| `small_style` | `TextStyle` | `theme.typography.caption` | The font of the pointer names and notes. |
| `enter` | `Option<FadeIn>` | `None` | Fade in at the start; `None` for none. |
| `exit` | `Option<FadeOut>` | `None` | Fade out before the end; `None` for none. |

Feature `cs` · [Source](https://github.com/khanhthanhdev/fframes-kit/blob/main/fframes-kit/src/kits/cs/list.rs#L464)

### Stack

A stack: boxes `width` by `height` pixels piled up from the bottom of a container that holds `capacity` of them, centred on `center` (units of `ui.space`), with a `top` marker beside the top box. It plays a [`ListTrace`](https://fframes-kit.pages.dev/docs/computer-science/list-trace.md) (the last item is the top), one step every `step_time` seconds from `delay`: pushed boxes drop in from above, popped ones rise out. With `indices` (manim-dsa's `add_indexes`) each box has its index left of the container, 0 at the bottom, and `label` (`add_label`, empty for none) is written under it. The whole figure fades with `enter` and `exit`.

| Field | Type | Default | Description |
| --- | --- | --- | --- |
| `trace` | [`Option<&ListTrace>`](https://fframes-kit.pages.dev/docs/computer-science/list-trace.md) | `None` | The recorded steps to play (`ListTrace`, the last item is the top); `None` draws nothing. |
| `delay` | `f32` | `0.0` | Seconds after the container's start before the first step. |
| `step_time` | `f32` | `0.7` | Seconds each step of the trace takes. |
| `center` | `(f64, f64)` | `(0.0, 0.0)` | The middle of the container, in units of `ui.space`. |
| `width` | `f32` | `220.0` | Width of a box in pixels. |
| `height` | `f32` | `60.0` | Height of a box in pixels. |
| `gap` | `f32` | `10.0` | Space between neighbouring boxes in pixels. |
| `capacity` | `usize` | `5` | How many boxes the container holds; sets its height. |
| `indices` | `bool` | `false` | Whether each box has its index left of the container, 0 at the bottom. |
| `label` | `&str` | `""` | Text written under the container; empty for none. |
| `notes` | `bool` | `true` | Whether the step's note is written under the stack. |
| `colors` | `CellColors` | `CellColors::themed(theme)` | Colours of the boxes in each state (visited, moved, found). |
| `frame_color` | `Color` | `theme.colors.muted` | Colour of the container's outline. |
| `marker_color` | `Color` | `theme.colors.highlight` | Colour of the `top` marker. |
| `index_color` | `Color` | `theme.colors.muted` | Colour of the indices. |
| `label_color` | `Color` | `theme.colors.text` | Colour of the label under the container. |
| `value_style` | `TextStyle` | `value_style` | The font of the values in the boxes. |
| `small_style` | `TextStyle` | `theme.typography.caption` | The font of the marker, indices and notes. |
| `enter` | `Option<FadeIn>` | `None` | Fade in at the start; `None` for none. |
| `exit` | `Option<FadeOut>` | `None` | Fade out before the end; `None` for none. |

Feature `cs` · [Source](https://github.com/khanhthanhdev/fframes-kit/blob/main/fframes-kit/src/kits/cs/list.rs#L718)

### Queue

A queue: boxes `width` by `height` pixels in a channel `capacity` boxes long, centred on `center` (units of `ui.space`), the front at the left, with `front` and `back` markers under the boxes. It plays a [`ListTrace`](https://fframes-kit.pages.dev/docs/computer-science/list-trace.md) (the first item is the front), one step every `step_time` seconds from `delay`: enqueued boxes slide in from the right, dequeued ones leave to the left and the rest move up. The whole figure fades with `enter` and `exit`.

| Field | Type | Default | Description |
| --- | --- | --- | --- |
| `trace` | [`Option<&ListTrace>`](https://fframes-kit.pages.dev/docs/computer-science/list-trace.md) | `None` | The recorded steps to play (`ListTrace`, the first item is the front); `None` draws nothing. |
| `delay` | `f32` | `0.0` | Seconds after the container's start before the first step. |
| `step_time` | `f32` | `0.7` | Seconds each step of the trace takes. |
| `center` | `(f64, f64)` | `(0.0, 0.0)` | The middle of the channel, in units of `ui.space`. |
| `width` | `f32` | `110.0` | Width of a box in pixels. |
| `height` | `f32` | `80.0` | Height of a box in pixels. |
| `gap` | `f32` | `12.0` | Space between neighbouring boxes in pixels. |
| `capacity` | `usize` | `6` | How many boxes the channel holds; sets its length. |
| `notes` | `bool` | `true` | Whether the step's note is written under the queue. |
| `colors` | `CellColors` | `CellColors::themed(theme)` | Colours of the boxes in each state (visited, moved, found). |
| `frame_color` | `Color` | `theme.colors.muted` | Colour of the channel's outline. |
| `marker_color` | `Color` | `theme.colors.highlight` | Colour of the `front` and `back` markers. |
| `value_style` | `TextStyle` | `value_style` | The font of the values in the boxes. |
| `small_style` | `TextStyle` | `theme.typography.caption` | The font of the markers and notes. |
| `enter` | `Option<FadeIn>` | `None` | Fade in at the start; `None` for none. |
| `exit` | `Option<FadeOut>` | `None` | Fade out before the end; `None` for none. |

Feature `cs` · [Source](https://github.com/khanhthanhdev/fframes-kit/blob/main/fframes-kit/src/kits/cs/list.rs#L955)