Java stacks and queues in detail

@

---

preamble

Please respect my original knowledge sharing and keep my blog in mind:South of the South i、

---

Tip: Below is the body of this post, with the following examples for reference

synopsis

Implemented in JavaStack cap (a poem)Queue operations are very common tasks. Stacks and queues are two different data structures with specific operations and behaviors.

a wooden or bamboo pen for sheep or cattle

A stack is a type ofLast In First Out (LIFO, Last In First Out) The data structure of the stack. It only allows operations that add (push) or remove (pop) elements at the top of the stack.Similar to a badminton bucket, the ball that goes in at the beginning needs to be taken out at the end.

Sample code for a Java implementation of a stack:

public static void query() {
        Queue<Integer> queue = new LinkedList<>();
        // Enter the queue
        (1);
        (2);
        (3).

        // Look at the head element of the queue
        ("Head element: " + ()); // Do not remove the head element.

        // exit the queue
        while (! ()) {
            ("Outgoing element: " + ()); }
        }
    }


    public static void stack() {
        //1. Create a stack: Use the Stack class (although Stack is a legacy class, it is more recommended to use an implementation of the Deque interface such as ArrayDeque) or the Deque interface (and its implementation classes such as ArrayDeque) to implement a stack.
        //Stack<Integer> stack = new Stack<Integer>();
        Deque<Integer> stack = new ArrayDeque<>();

        //2. Add elements to the top of the stack by entering the stack
        (1);
        (2);
        (3);

        //3, out of the stack (Pop): remove the element from the top of the stack, and return the removed element. Stack class provides pop () method for out of the stack operation
        int element = (); // return and remove the top element of the stack
        (element); // Output: 3


        // 4. Access to the top of the stack (Peek): Get the top element of the stack, but do not modify the stack. the Stack class provides the peek() method for accessing the top element of the stack
        int outElement = (); // Returns the top element but does not remove it.
        ("Top stack element: " + outElement); // Output: 3

        // 5. Loop out of the stack
        while (! ()) {
            ("Out of stack element: " + ()); }
        }

        /* Output:
        Top stack element: 3
        Outgoing stack elements: 3
        Outgoing stack elements: 2
        Outgoing stack elements: 1*/
    }

The main application scenarios for the stack include:

1. Function call stack:
   In programming languages, function calls are implemented via the stack. When a function is called, information about its local variables, parameters, and return address is pressed into the stack. When the function is finished executing, this information is popped off the stack and control is returned to the caller.

2. Browser forward and backward:
   Browser history is usually managed using a stack. When we browse a web page, each visited page is pressed into the stack; when we click "back", the page is ejected from the stack and returned to the previous page.

3. Parentheses match:
   When parsing or compiling code, checking for matches of parentheses, curly braces, etc. is a common problem. The stack can be used to solve this problem by pressing a left parenthesis into the stack whenever it is encountered, and checking whether the top element of the stack matches a right parenthesis whenever it is encountered, and popping the top element of the stack if it matches, or else reporting an error.

4. Undo the operation:
   In many editors or graphical interfaces, the user can return to a previous state through an undo operation. Undo operations are usually implemented using a stack, where each operation is pressed into the stack, and when the user performs an undo operation, the operation at the top of the stack is popped and applied to the current state.

formation

A queue is aFirst In First Out (FIFO, First In First Out) data structure. It only allows adding elements to the end of the queue (enqueue) and deleting elements at the beginning of the queue (dequeue)A process similar to queuing。

Java implementation of the queue sample code:

public static void queue() {
        // 1. Create a queue: We can use Java's collection class LinkedList to implement queue operations.
        Queue<Integer> queue = new LinkedList<>();
        // 2. Enqueue: adds an element to the end of the queue. the LinkedList class provides the offer() method for queue operation.
        (1);
        (2);
        (3).

        //3, out of the queue (Dequeue): from the head of the queue to remove the element, and return the removed element. LinkedList class provides the poll () method for out of the queue operation.
        int element = (); // Returns and removes the element at the head of the queue.
        (element); // Output: 1

        // 4. Access to the head element (Peek): Get the head element, but do not modify the queue. the LinkedList class provides the peek() method for accessing the head element.
        ("Queue head element: " + ()); // do not remove the queue head element

        // 5. Loop out of the queue
        while (! ()) {
            ("Queue elements out: " + ()); }
        }

        /* Output:
        Team head element: 1
        Outgoing element: 1
        Outgoing team element: 2
        Outgoing team element: 3*/
    }

Difference between add and offer methods in LinkedList

add method. The add method belongs to the Collection interface, which attempts to add the specified element to the list. If the addition succeeds, it returns true; if it fails for some reason (such as a capacity limit), it throws the IllegalStateException. In a LinkedList, using the add method when the queue is empty may result in an error due to a capacity limit violation. In addition, when using a LinkedList as a list, the add method is usually used to press in objects.

Offer method. The offer method belongs to the Deque interface (double-ended queue)which attempts to insert the specified element into the queue. It returns true if the insertion was successful, or false if the element could not be added because of space constraints.Unlike theadd method, the Unlike the add method, the offer method does not throw an exception, but instead returns a value indicating whether the operation was successful. In a capacity-limited queue, theThe offer method is superior to the add method because it handles the lack of space by returning false instead of throwing an exception, which is more efficient。‌

To summarize, the main differences between the add and offer methods are their return values and exception handling. The add method may throw an exception due to a capacity limit violation, while the offer method avoids exception handling overhead by returning a value that indicates whether the operation was successful or not.

Queue Main Application Scenarios:

1. Task Scheduling:
   In a multitasking system, tasks are usually stored in a queue. The system executes the tasks in the order in which they enter the queue, enabling fair scheduling.

2. Messaging:
   In inter-process communication or network programming, messages are usually stored in a queue. A sender sends a message to the end of the queue, and a receiver takes the message from the head of the queue to process it.

3. Page request processing:
   In a Web server, multiple user requests may arrive at the same time. The server can store these requests in a queue and then process them in the order in which they arrive.

4. Breadth-first search (BFS):
   In the graph traversal algorithm, breadth-first search uses a queue to store the nodes to be visited. The algorithm starts by adding the starting node to the queue. Then, the algorithm proceeds in a loop, removing one node at a time from the queue to be visited and adding its unvisited neighboring nodes to the queue.

summarize

realizeStacks and QueuesThe application scenarios help us to choose the right data structure according to the actual needs, so as to solve the problems more efficiently.

---

I am.South of the South iRecord the drops grow a little bit every day, learning is never ending! Reprinted with link to original article!!!