This is the 13th day of my participation in the First Wenwen Challenge 2022.First challenge in 2022.

The stack and queue

Mastering the fundamentals of data structures makes stack and queue problems much easier to deal with. Of course, some problems can be quite intractable. Some of the problems are little more than tweaks to the basic data structure; others are much harder.

Implementing a stack

A stack is a data structure that is exactly what it sounds like: a place where data is stored. In some specific problems, stacks are more appropriate than arrays.

The stack is in LIFO order. In other words, like a stack of dishes, the last item on the stack goes out first.

The stack has the following basic operations.

  • pop(): Removes the top element of the stack.
  • push(item): Adds an element to the top of the stack.
  • peek(): returns the top element of the stack.
  • isEmpty(): returns if and only if the stack is emptytrue.

Unlike arrays, the stack cannot access the first in constant time complexityAn element. However, because the stack does not need to move elements during add and remove operations, such operations can be done in constant time complexity.

A simple stack implementation code is shown below. Note that a stack can also be implemented using a linked list if elements are added and removed from only one end of the list.

1.   public class MyStack<T> {
2.     private static class StackNode<T> {
3.       private T data;
4.       private StackNode<T> next;
5.
6.       public StackNode(T data) {
7.         this.data = data;
8.       }
9.     }
10.
11.    private StackNode<T> top;
12.
13.    public T pop(a) {
14.      if (top == null) throw new EmptyStackException();
15.      T item = top.data;
16.      top = top.next;
17.      return item;
18.    }
19.
20.    public void push(T item) {
21.      StackNode<T> t = new StackNode<T>(item);
22.      t.next = top;
23.      top = t;
24.    }
25.
26.    public T peek(a) {
27.      if (top == null) throw new EmptyStackException();
28.      return top.data;
29.    }
30.
31.    public boolean isEmpty(a) {
32.      return top == null;
33.    }
34.  }
Copy the code

For some recursive algorithms, stacks are often useful. Sometimes, you need to add temporary data to the stack during recursion, and then delete the data after backtracking (for example, if the recursive judgment fails). Stack is an intuitive way to implement this kind of algorithm.

Stacks also come in handy when implementing recursive algorithms using iterative methods. This is a good exercise. Choose a simple recursive algorithm and implement it iteratively.

Implementing a queue

The queue uses a first-in, first-out (FIFO) order. Like a ticket queue, the first elements are the first ones out.

Queues have the following basic operations.

  • add(): Adds an element to the end of the queue.
  • remove(): Removes the first element in the queue.
  • peek(): Returns the top element of the queue.
  • isEmpty(): returns if and only if the queue is emptytrue.

Queues can also be implemented using linked lists. In fact, lists and queues are essentially the same as long as elements are added and removed from opposite ends of the list.

Update the first and last nodes in the queue, so be sure to double-check.

Queues are often used in breadth-first search or caching implementations.

For example, in breadth-first search, we use queues to store nodes that need to be processed. Each time a node is processed, its neighbors are added to the end of the queue. This allows us to process each node in the order in which it was found.