---Stack & queue---

Catalog

Stack （Stack）

One 、 Concept

Two 、 The core operation of stack ：

3、 ... and 、 The realization of the stack ：

1. Use sequence table to realize stack

2. Use linked list to realize stack

queue （Queue）

One 、 Concept

Two 、 Examples of complex queues ：

3、 ... and 、 Implementation of queues

1. Using linked lists to implement queues

2. Use an array to implement a ring queue

---

Stack （Stack）

One 、 Concept

Stack The elements in follow “ Last in, first out ”, The end that allows insertion and deletion is called the top of the stack ; fixed , The other end that does not allow insertion and deletion is called the bottom of the stack , You can think of it as a clip on a gun for easy understanding . meanwhile Stack Is a class , It can be used directly .

Two 、 The core operation of stack ：

① Push ： Put the elements on the stack ,push()

② Out of the stack ： Delete the last element ,pop()

③ Take the top element of the stack ： Get the result of the last incoming element ,peek()

3、 ... and 、 The realization of the stack ：

1. Use The order sheet Implementation stack

private int[] data=new int[100];
    private int size=0;

a) Tail insertion → Push

public void push(int val){
        if (size>=data.length){
            return;
        }
        data[size]=val;
        size++;
    }

b) Deletion at the end → Out of the stack

public Integer pop(){
        if (size==0){
            return null;
        }
        // The top element of the stack is the last element 
        int ret=data[size-1];
        size--;
        return ret;
    }

c) Take the element according to the subscript → Take the top element of the stack

public Integer peek(){
        if (size==0){
            return null;
        }
        return data[size-1];
    }

2. Use Linked list Implementation stack

Define the node

class Node{
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
    }
}

（ A linked list without dummy nodes is used here to represent ）

a) Head insertion → Push

public void push(int val){
            Node newNode=new Node(val);
            // Insert the new node into the header 
            // Because the current linked list does not have puppet nodes , So first judge whether it is empty 
            if (head==null){
                head=newNode;
                return;
            }
            newNode.next=head;
            head=newNode;
        }

b) Head deletion → Out of the stack

public Integer pop(){
            // Delete the header 
            if (head==null){
                return null;
            }
            if (head.next==null){
                int ret= head.val;
                head=null;
                return ret;
            }
            int ret=head.val;
            head =head.next;
            return ret;
        }

c) Take the header node → Take the top element of the stack

public Integer peek(){
                if (head==null){
                    return null;
                }
                return head.val;
            }

queue （Queue）

One 、 Concept

queue The elements in follow “ fifo ”, The end that allows deletion is called the head of the team , The end allowed to be inserted is called the end of the queue

Different from stack , Queue is an interface , Cannot instantiate directly , You need to create corresponding subclasses .

Two 、 Examples of complex queues ：

1. Priority queue

2. Message queue （ The element in the queue has type , When you get out of the queue, you can get elements by type ）

3. Blocking queues （ If the queue is full , Continue inserting data at this time , It will form “ Blocking ”, If the queue is empty , At this point, continuing to take elements will also form “ Blocking ”【 Blocking ： Generally speaking, the code will not continue to go down 】）

4. Lockless queue （ More efficient thread safe queues , A common way to ensure thread safety is to lock , But the locking efficiency is relatively low ）

3、 ... and 、 Implementation of queues

1. Use Linked list Implementation queue

Defining nodes

static class Node{
        int val;
        Node next;
        public Node(int val){
            this.val=val;
        }
    }

Create the head node and tail node of the linked list

private Node head=null;
    private Node tail=null;

a) Queue entry offer(int val)

public boolean offer(int val){
        Node newNode=new Node(val);
        // Insert at the end of the list , You need to consider whether the current list is empty 
        if (head==null){
            // Directly to head and tail Point to the new node 
            head=newNode;
            tail=newNode;
            return true;
        }
        tail.next=newNode;
        tail=tail.next;
        return true;
    }

b) Outgoing queue poll()

public Integer poll() {
        if (head==null){
            return null;
        }
        int ret=head.val;
        if (head.next==null){
            head=null;
            return ret;
        }
        head=head.next;
        return ret;
        }

c) Take the team lead   peek(int val)

public Integer peek(){
        if (size==0){
            return null;
        }
        return data[size-1];
    }

2. Use Array Implement ring queue

Create two subscripts , Represent the head and tail of the queue respectively , Set up a special one size Variable record ,size==0 It's empty ,size== The array length is full .

private int[] data=new int[100];
    // Queue validity interval [head,tail)
    private int head=0;
    private int tail=0;
    private int size=0;

a) Queue entry

public boolean offer(int val){
        if (size==data.length){
            // The queue is full , Expansion logic can also be realized here 
            return false;
        }
        // Put the new element in tail The corresponding subscript 
        data[tail]=val;
        tail++;
        //tail End of array reached , Need to let tail Start from scratch 
        if (tail==data.length){
            tail=0;
        }
        size++;
        return true;
    }

b) Outgoing queue

public Integer poll(){
        if (size==0){
            return null;
        }
        int ret=data[head];
        head++;
        if (head==data.length){
            head=0;
        }
        size--;
        return ret;
    }

c) Take the team lead

public Integer peek(){
        if (size==0){
            return null;
        }
        return data[head];
    }