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:

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.

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.

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: Topic index.