This is the 11th day of my participation in the August More Text Challenge. For details, see:August is more challenging

1 Stack (Stack)

A stack is a data structure that is either FILO, First in last out or LIFO.

  • Unidirectional linked list: a single linked list can be used to implement the stack data structure. Also, because we only operate on the top elements of the stack, borrowing the head of the single linked list allows all stack operations to be done in O(1) time.
  • Stack: a subclass of Vector that has several more methods than Vector
 public class Stack<E> extends Vector<E> {
         // Push the element to the top of the stack
         public E push(E item) {
             addElement(item);
             return item;
         }
     
         // Pop the top element of the stack
         public synchronized E pop(a) {
             E obj;
             int len = size();
             obj = peek();
             removeElementAt(len - 1);
             return obj;
         }
     
         // Access the top element of the current stack, but do not remove the top element
         public synchronized E peek(a) {
             int len = size();
             if (len == 0)
                 throw new EmptyStackException();
             return elementAt(len - 1);
         }
     
     // Test whether the stack is empty
         public boolean empty(a) {
             return size() == 0;
         }
         
         // Returns the position of the object in the stack, base 1
         public synchronized int search(Object o) {
             int i = lastIndexOf(o);
             if (i >= 0) {
                 return size() - i;
             }
             return -1; }}Copy the code

Basic operations (on failure: add/remove/ Element for throw exception, offer/poll/peek for return false or null)

  • E push(E): Pushes an element onto the stack
  • E pop(): Pops the top element on the stack
  • E peek(): Takes the top element of the stack but does not pop it
  • boolean empty(): tests whether the stack is empty
  • int search(o): Returns the position of the object in the stack, base 1

Application scenarios

When solving a problem, you only need to care about the most recent operation, and when the operation is complete, you need to look forward to the previous operation.

Case 1: Determining whether a string is valid

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, determine whether the string is valid. A valid string must meet the following requirements:

  • The opening parenthesis must be closed with a closing parenthesis of the same type
  • The opening brackets must be closed in the correct order
  • An empty string is considered a valid string

Use a stack, keep pressing in the open bracket, once a close bracket, we will pop the open bracket at the top of the stack, indicating that this is a legal combination, and so on, until the final judgment stack left open bracket.

Case 2: Daily temperature

From the daily temperature list, create a new list with the input of how much longer you have to wait for the temperature to rise beyond that day. If it does not rise after that, replace it with a zero.

Their thinking

  • Idea 1: The most intuitive way is to search backward for each temperature value and find a value higher than the current temperature. The computational complexity is O(n2).

  • Idea 2: You can use a stack to quickly know how many days it will take for the temperature to rise. Scan through a given array T and get the result if the temperature on that day is higher than the temperature recorded at the top of the stack.

2 the Queue (Queue)

A Queue is different from a stack. The most important feature of a Queue is first-in, first-out (FIFO), which is like queuing in order. For queue data, we only allow viewing and adding data at the end of the queue and viewing and deleting data at the head of the queue.

  • The stack: in this paper,Last in, first out(LIFO)
  • The queue: in this paper,First in first outFirst in First Out, i. eFIFO)

implementation

Queues can be implemented with the help of double linked lists. The header pointer of a double-linked list allows data to be viewed and deleted at the head of the queue, while the tail pointer of a double-linked list allows data to be viewed and added at the end of the queue.

Basic operations (on failure: add/remove/ Element for throw exception, offer/poll/peek for return false or null)

  • int size(): Gets the queue length
  • boolean add(E)/boolean offer(E): Adds an element to the end of the queue
  • E remove()/E poll(): Gets the first element in the queue and deletes it from the queue
  • E element()/E peek(): Gets the first element of the queue but does not remove it from the queue

Application scenarios

Queues are used when data needs to be processed in a certain order and the amount of data is constantly changing.

3 Dual-end Queue (Deque)

The biggest difference between a dual-end queue and a normal queue is that it allows you to view, add, and delete data at both ends of the queue in O(1) time.

implementation

A Deque is similar to a queue and can be implemented using a double linked list.

Application scenarios

The most common place for a double-ended queue is to implement a window or continuous interval with a dynamic change in length, and dynamic window data structure is used in many problems.

Case 1: Maximum sliding window

Given an array nums, a sliding window of size k moves from the leftmost part of the array to the rightmost part of the array. You can only see the number in the slide window k, and the slide window moves one bit to the right at a time to return the maximum value in the current slide window.

Their thinking

  • Idea 1: Move the window and scan to get the maximum value. Let’s say we have n elements in the array, and the algorithm complexity is O(n). That’s the most intuitive thing to do.

  • Idea 2: Use a double-ended queue to hold the array index of the largest number in the current window. The new head of the double-ended queue is the largest number in the current window. With this index, you can quickly tell whether the new window still contains the original largest number. If it is no longer contained, the old number is removed from the head of the double-endian queue.

Because the dual-endian queue allows both operations to be performed in O(1) time, the complexity of the algorithm can be controlled at O(n).