An article to introduce you to Java stacks and queues

This article brings you relevant knowledge about java, which mainly organizes issues related to stacks and queues, including the definition, application, implementation and operation of stacks and queues, etc. , let’s take a look at it, I hope it will be helpful to everyone.

Recommended study: "java Video Tutorial"

Before learning stacks and queues, first understand what a linear table is: Save a single element of the same type at a time, and multiple elements are logically continuous, such as arrays, linked lists, strings, stacks and queues
Stacks and queues are actually linear lists with limited operations, whether they are arrays or linked lists, they can be Inserting and deleting at the head can also be done at the tail, but stacks and queues can only be inserted at one end and deleted at one end

1. Stack

1. Definition

You can only insert elements at one end, and you can only delete elements at this end (top of the stack). You can think of the stack as a "water cup". You can only add elements from one end, and you can only delete elements from one section. Moreover, first The water that enters the water cup is at the bottom of the cup, and the water that enters the water cup later is at the top of the cup. When you pour water out, the water from the top of the cup is also poured out. The same is true for stacks. The elements that are pushed into the stack first are at the bottom of the stack, and the elements that are pushed into the stack later are It is at the top of the stack, so the elements that are pushed into the stack first are taken out last, and the elements that are pushed into the stack last are taken out first. This is also the characteristic of the stack: "First in, last out, last in, first out". Last In First Out (LIFO), elements can be taken out and added only in Top of the stack.
Put 1 2 3 4 5 into the stack at once

2. Stack application

1. Ubiquitous undo (undo) operation

After typing something wrong in any editor, use Ctrl z to return to the entered content;
Click the back operation in any browser

All are Application of this structure of the stack
1. Use the editor to use the undo operation. Once you input, the content is pushed into the stack. If you input again, it will be pushed into the stack again. If you find an input error, use the undo operation to save the current content. If the error content on the top of the stack pops up, the current content on the top of the stack will be the last input content.
2. Browsing the web is actually based on the same principle, just like opening Baidu -> opening csdn -> opening the creation center, which also uses the stack structure. First, the Baidu web page is pushed into the stack, and then the csdn web page is pushed into the stack. , and then push the creation center web page into the stack. If you want to return to the csdn home page, press the back arrow to pop up the creation center web page currently on the top of the stack and take out the csdn home page.

2. Operating system stack

During the re-execution of the program, function B is called from function A, and function C is called from function B. When the call ends and returns to execution, how do you know where to start? Continue to execute, behind it is the stack structure

3. Stack implementation

Stack implemented based on linked list – chained stack
Stack implemented based on array – sequential stack (use a relatively More)
Define a stack based on dynamic array

//基于动态数组实现的顺序栈public class MyStack<e> {
    //记录当前栈的元素个数
    private int size;
    //实际存储数据的动态数组，此时在栈中只能在数组的尾部添加和删除元素
    private List<e> data = new ArrayList();
    }</e></e>

4. Stack operations

1. Add an element to the stack
You can only add it to the top of the stack

 /**
     * 向当前栈中添加元素 -- >压栈操作
     * @param val
     */
    public void push(E val){
        data.add(val);
        size++;
    }

2. Currently popping an element from the top of the stack

/**
     * 弹出当前栈顶元素,返回栈顶元素的值
     * @return
     */
    public E pop(){
        if (isEmpty()){
            //栈为空无法弹出
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //在数组末尾删除元素
        E val = data.get(size - 1);
        data.remove(size - 1);
        size --;
        return val;
    }

3. View the current element on the top of the stack, but not popping it

/**
     * 查看当前栈顶元素值，不弹出该元素
     * @return
     */
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek!");
        }
        return data.get(size - 1);
    }

2. Queue

1. Definition

Queue: first-in-first-out (FIFO) data structure i. Elements can only be added to the queue from the end of the queue, and can only be dequeued from the head of the queue. The dequeuing order and enqueuing order of elements are maintained. Consistent
Put 1 2 3 4 5 into the queue in sequence

2. Queue application

In real life, various "queuing" operations

3. Queue implementation

Queue implemented based on array – sequential queue
Queue implemented based on linked list – chained queue
Dequeue operation can only be performed at the head of the queue , if a queue implemented by an array is used, every time an element is dequeued, all the remaining elements have to be moved forward one unit. At this time, the queue implemented by a linked list is more suitable for the queue structure. To delete an element, you only need to delete the head node. Add elements to the end of the linked list

public interface Queue<e> {
    //入队操作
    void offer(E val);
    //出队操作
    E poll();
    //查看队首元素
    E peek();
    boolean isEmpty();}</e>

For stacks, there are many subclasses of queue implementations, such as
FIFO queue
Double-ended queue
Circular queue
Priority Queue
No matter which queue must be implemented

4.FIFO queue

1.Define a FIFO queue

// An highlighted blockvar foo = 'bar';

2.Add an element to the queue

public void offer(E val) {
        Node<e> node = new Node(val);
        if (head == null){
            head = tail = node;
        }else{
            //链表的尾插
            tail.next = node;
            tail = node;
        }
        size++;
    }</e>

3. Dequeue an element from the head of the current queue

 public E poll() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll!");
        }
        //头删
        E val = head.val;
        Node<e> node = head;
        head = head.next;
        node.next = node = null;
        size--;
        return val;
    }</e>

4. View the head element of the current queue

public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }

5.循环队列

1.定义：基本上都是使用固定长度的数组来实现，数组在实现队时，若从数组头部删除元素需要频繁的移动后面的元素，效率比较低；出队和入队操作，使用两个引用，一个head，一个tail,添加元素在数组的尾部添加，删除元素只需要移动head引用指向的地址即可（逻辑删除）
2.应用：操作系统的生产消费者模型，MySQL数据库的InnoDB存储引擎的redo日志
3.循环队列就是使用长度固定的数组来实现，数组头部就是队首（head），数组的尾部就是队尾（tail），数组[head…tail)时循环队列的有效元素
head永远指向循环队列的第一个元素
tai永远指向循环队列有效元素的后一个位置

此时循环队列的有效元素就为7 9 1两个元素
循环队列出队一个元素，就只用让head引用向后移动一个位置

此时循环队列的有效元素就只有9 和 1 两个元素了
再出队一个元素，但此时head引用已经走到末尾了，所谓循环队列就是当head或者tail引用走到数组末尾时，再向后移动就是返回数组头部的操作，循环队列最大好处就是进行元素的删除的时候不需要进行数据的搬移操作，当有新的元素添加到队列中就会覆盖掉原来的元素，就只需要将tail索引位置覆盖上新的元素，再让tail再向后移动

当队列为空时,head == tail

当队列已“满”时，head == tail

循环队列需要注意的关键点
1.因此当head 和 tail相等时，没法区分此时循环队列已满，还是为空，因此在循环队列中，若(tail + 1) % n == head就认为循环队列已满

此时循环队列就已经满了，在循环队列中就会浪费一个空间，判断队列是否已满
2.head和tail的移动不能简单的 + 1，使用取模操作，取数组长度
tail = (tail + 1) % n
head = (head + 1) % n
对数组长度取模的本质：
当head和tai走到数组最后一个索引位置时，下一次要返回数组头部，就必须用 + 1对数组长度取模
3.head == tail时，认为队列为空

6.循环队列的操作

1.定义一个循环队列

//基于整形的循环队列public class LoopQueue implements Queue<integer> {
    //定长数组
    private Integer[] data;
    //指向队首元素
    int head;
    //指向队尾元素的下一个元素
    int tail;
    public LoopQueue(int size){
        data = new Integer[size + 1];
    }}</integer>

2.向循环队列中添加一个元素

@Override    public void offer(Integer val) {
       if (isFull()){
           throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
       }
       data[tail] = val;
       tail = (tail + 1) % data.length;
    }

3.从循环队列中出队一个元素

 @Override    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot poll!");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        return val;
    }

4.查看当前循环队列队首元素

 @Override    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot peek!");
        }
        return data[head];
    }

5.判断当前循环队列是否为空

 @Override    public boolean isEmpty() {
        return head == tail;
    }

6.判断当前循环队列是否已满

 public boolean isFull(){
        return (tail + 1) % data.length == head;
    }

7.toString方法

public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        //最后一个有效元素的索引
        int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data[i]);
            if (i != lsatIndex){
                sb.append(", ");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }

---

7.双端队列

双端队列：Deque是Queue的子接口，这个队列既可以尾插，头出；也可以头插，尾出

双端队列的一个常用子类就是LinkedList，不管使用栈还是队列，都可以统一使用双端队列接口
1.现在需要一个栈

2.现在需要一个队列

推荐学习：《java视频教程》

The above is the detailed content of An article to introduce you to Java stacks and queues. For more information, please follow other related articles on the PHP Chinese website!