# Stacks, Queues, and Iterators

Source: https://wisconsin.twango.dev/fa24-cs300/u4-linear-data/deques-and-interation

# Stacks, Queues, and Iterators

## Stack
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where elements are added and removed from the top.

> [!example]
> Think of a stack as a stack of plates. You can only add or remove plates from the top of the stack.

Compared to a head-tail linked list, a stack only allows for operations at the top of the stack. The basic operations of a stack include:

- **Push**: Add an element to the top of the stack.
- **Pop**: Remove and return the element at the top of the stack.
- **Peek**: Return the element at the top of the stack without removing it.

### Array-Based Stack
An array-based stack uses an array to store elements and a pointer to keep track of the top of the stack. The top of the stack is the last element added to the stack.

> [!tip]
> When implementing a stack using an array, you can use the `size` of the array to keep track of the top of the stack.

### Linked List Stack
A linked list stack uses a linked list to store elements, where each element points to the next element in the sequence. The top of the stack is the first element in the list.

> [!tip]
> When implementing a stack using a linked list, you can use the `head` pointer to keep track of the top of the stack.

## Queue
A queue is a linear data structure that follows the First In, First Out (FIFO) principle, where elements are added at the rear and removed from the front.

> [!example]
> Think of a queue as a line of people waiting for a bus. The first person to arrive is the first person to board the bus.

Compared to a head-tail linked list, a queue only allows for operations at the front and rear of the queue. The basic operations of a queue include:

- **Enqueue**: Add an element to the rear of the queue.
- **Dequeue**: Remove and return the element at the front of the queue.
- **Peek**: Return the element at the front of the queue without removing it.

### Array-Based Queue
An array-based queue uses an array to store elements and two pointers to keep track of the front and rear of the queue. The front of the queue is the first element added to the queue, and the rear of the queue is the last element added to the queue.

> [!tip]
> When implementing a queue using an array, you can use the `front` and `rear` pointers to keep track of the front and rear of the queue. However, unless you are using a circular array, you may need to shift elements when the front of the queue is removed (not efficient).

### Linked List Queue
A linked list queue uses a linked list to store elements, where each element points to the next element in the sequence. The front of the queue is the first element in the list, and the rear of the queue is the last element in the list.

> [!tip]
> When implementing a queue using a linked list, you can use the `head` and `tail` pointers to keep track of the front and rear of the queue.

### Double-Ended Queue (Deque)
A double-ended queue (deque) is a linear data structure that allows for insertion and deletion at both the front and rear of the queue. This provides more flexibility than a stack or queue, as elements can be added or removed from either end.

With a double ended queue, you can effectively implement both a stack and a queue, as you can add or remove elements from either end of the deque.

> [!note]
> Deques are not taught or within scope for CS 300, but are included here for completeness. Java provides a `Deque` interface and several implementations, which can be useful in certain situations.

## Iterators
An iterator is an object that allows you to traverse a collection of elements, such as a list, stack, or queue. It provides methods to move through the collection and access the elements one by one.

In Java, the `Iterator` interface provides methods to iterate over a collection. The basic methods of an iterator include:

- **`hasNext()`**: Returns `true` if there are more elements in the collection.
- **`next()`**: Returns the next element in the collection.

> [!tip]
> Iterators are commonly used to traverse collections in Java, such as lists, sets, and maps. They provide a way to access elements without exposing the underlying data structure.
>
> To use enhanced for loops in Java, the collection must implement the `Iterable` interface, which provides an `iterator()` method that returns an iterator for the collection.

### Iterable vs. Iterator

- **`Iterable`**: Represents a collection of elements that can be iterated over. It provides an `iterator()` method that returns an iterator for the collection.
- **`Iterator`**: Allows you to traverse a collection of elements. It provides methods to move through the collection and access the elements one by one.

> [!example]
> The following code snippet demonstrates how to use an iterator to traverse a list of integers:
>
> ```java
> List<Integer> numbers = new ArrayList<>();
> numbers.add(1);
> numbers.add(2);
> numbers.add(3);
>
> Iterator<Integer> iterator = numbers.iterator();
> while (iterator.hasNext()) {
>     System.out.println(iterator.next());
> }
> ```
>
> This code snippet creates a list of integers, adds elements to the list, and then uses an iterator to traverse the list and print each element.

> [!success] Key Idea
> `Iterable` defines a method `iterator()` that returns an `Iterator` object, which allows you to traverse the elements of a collection. The `Iterator` is what actually allows you to move through the collection and access the elements one by one.
>
> ```mermaid
> classDiagram
>     class Iterable {
>         <<interface>>
>         +iterator(): Iterator
>     }
>
>     class Iterator {
>         <<interface>>
>         +hasNext(): boolean
>         +next(): Object
>         +remove(): void
>     }
>
>     Iterable <-- Iterator : Uses
> ```

## Source

The existing course note was retained and normalized during the merge.

Related: [[u4-linear-data/index|Topic index]].