queue Queue

Queued Concept and characteristic fifo

Concept queue ： Data insertion is only allowed at one end , A special linear table that deletes data at the other end , Queue has first in first out FIFO(First
In First Out) Queue entry ： The end of the insertion is called the end of the queue （Tail/Rear） Outgoing queue ： The end of the delete operation is called the queue head

Queue Two interfaces implemented

Deque and Queue

Look at LinkedList( The bottom layer is a two-way linked list ) Realized Two interfaces One is

Deque and Queue

Queue The common method of

1. Additive elements offer And add

public class Main {
    
    public static void main(String[] args) {
    
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.offer(2);
        System.out.println(queue.peek());
        System.out.println(queue.element());

    }
}

2. Get team leader elements peek and element

public class Main {
    
    public static void main(String[] args) {
    
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.offer(2);
        System.out.println(queue.peek()); 1
        System.out.println(queue.element()); 1

    }
}

3 Outgoing queue poll and remove

public static void main(String[] args) {
    
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        queue.offer(2);
        System.out.println(queue.peek());
        System.out.println(queue.element());
        System.out.println(queue.poll());
        System.out.println(queue.remove());
        System.out.println(queue);
        
    }

4. add to Delete see Team head Elements Differences in methods

here Additive elements commonly It's used a lot Yes. offer

deque Deque

Some methods of double ended queue

public class Main {
    
    public static void main(String[] args) {
    
        Deque<Integer> deque = new LinkedList<>();
        deque.offerLast(1); // Last  The tail   The team 
        deque.offerFirst(2);// First  Head into the team 
        deque.offer(3);//  By default, the end of the queue is joined 
        System.out.println(deque.peekFirst());
        System.out.println(deque.peekLast());
        System.out.println(deque);
    }
}

It's over deque , got it LinkedList, The bottom layer is a two-way linked list In retrospect, it is We learned ArrayList The order sheet
here We Here is a brief summary ,

ArrayList And LinkedList Of difference

Add, delete, check and modify Of angle Look at ,ArrayList Bottom Is an array , Every time Delete an element , By moving elements complete , and LinkedList yes Chain table structure , To delete an element, you just need Let the previous node point to

The next node of this node , Add... At the specified location Empathy ,ArrayList still adopt Move elements To complete the addition , and LinkedList Just change the direction of the node .

in addition ArrayList stay Memory is continuous , and LinekdList stay In the memory Not continuous （ It seems to be continuous , But each node represents a space , Connected by reference , So he is not continuous ）
After knowing so much that We Come on branch Three ways To implement our byte Queues

Implement your own queue

1. Single linked list implementation

class Node {
    
    public int val;
    public  Node next;
    public Node(int val) {
    
        this.val = val;
    }
}
//  Use single linked list to realize queue 
public class MyQueue {
    
    //  Marker head 
    public Node head;
    //  Mark   tail 
    public  Node last;

    public void offer(int val) {
    
        Node node = new Node(val);
        if(head == null) {
    
         head = node;
         last = node;
        }else {
    
            last.next = node;
            last = last.next;
        }
    }
    public int poll() {
    
        if(isempty()) {
    
            throw new RuntimeException(" The queue is empty ");
        }
        int oldVal = head.val;
        this.head = head.next;
        return oldVal;
    }
    public int peek() {
    
        if(isempty()) {
    
            throw new RuntimeException(" The queue is empty ");
        }
        int oldVal = head.val;
        return oldVal;
    }
    public boolean isempty() {
    
        return this.head == null;
    }

    @Override
    public String toString() {
    
        return "MyQueue{" +
                "head=" + head +
                ", last=" + last +
                '}';
    }
}

The test case

public class Test {
    
    public static void main(String[] args) {
    
        MyQueue queue = new MyQueue();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.peek());//1
        System.out.println(queue.poll());//1
        System.out.println(queue.poll());//2
        System.out.println(queue.poll());//3
        System.out.println(queue.poll());// abnormal 

    }
}

2. Two way linked list

class Node {
    
    public int val;
    public Node next;
    public Node prev;
    public Node(int val) {
    
        this.val = val;
    }
}
//  Use the bidirectional linked list to realize the stack 
public class MyQueue2 {
    
    //  Marker head 
    public Node head;
    public Node cur;
    public void offer(int val) {
    
        Node node = new Node(val);
        if(cur == null) {
    
            head = node;
            cur = node;
        }else {
    

            cur.next = node;
            node.prev = cur;
            cur = cur.next;

        }
    }
    //  Delete team leader element 
    public int poll() {
    
        if(isEmpty()) {
    
            throw new RuntimeException(" The queue is empty and cannot be deleted ");
        }
        int oldVal = head.val;

        head.prev = null;

        this.head = head.next;

        return oldVal;
    }
    public int peek() {
    
        if(isEmpty()) {
    
            throw new RuntimeException(" The queue is empty and cannot be deleted ");
        }
        int oldVal = head.val;
        return oldVal;
    }
    public boolean isEmpty() {
    
        return this.head == null;
    }

}

The test case

public class Test {
    
    public static void main(String[] args) {
    
        MyQueue2 queue = new MyQueue2();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        System.out.println(queue.peek());//1
        System.out.println(queue.poll());//1
        System.out.println(queue.poll());//2
        System.out.println(queue.poll());//3
        System.out.println(queue.poll());//4
        System.out.println(queue.poll());// abnormal 

    }
}

Through the linked list queue , Have you ever thought about it Use Array to achieve The queue ？？
stay Implement arrays Realization queue When We We should learn one first Circular queue , or It's hard for us to achieve queue

extraction Circular queue

Let's take a look first The circular queue

Let's look at Let's talk about our little tricks

Array subscript loop tips

1. The subscript finally goes back (offset Less than array.length):

   index = (index + offset) % array.length

7 go To 2 The offset offset by 4 adopt The formula （index+ offset）% arraylength = （7 + 4） % 9 = 11 % 9 = 2

There are three methods to judge the full number of circular queues

The first solution Use usedSize

The second kind Solution Use flag bits

Create a boolean Variable flag First assignment by false rear Every time go a step flag The assignment is true know front And rear Meet if flag by true The array is full ,

front Every time Take a step flag The assignment is false When front And rear meet And flag by false The array is empty

The third kind of Waste a grid to judge whether it is empty or full

understand 了 such many Of the circular queue knowledge that We directly On oj topic


that Start Well

Design loop queue

The team and Determine if the queue is full

Out of the team and Judge Array Is it empty , obtain Team head and End of team subscript

It's done Method We Put it in oj come up run

Results found error here No machine We Come on Observe Output and expect result

Next we To observe oj On Given error message

Method 2 Use suedSize Come on Problem solving

//  Use  usedSize
public class MyCircularQueue {
    
    public int[] elem;
    public int front;
    public int rear;
    int usedSize;
    public MyCircularQueue(int k) {
    
        this.elem = new int[k];
    }

    public boolean enQueue(int value) {
    
        if(isFull()) return false;

        this.elem[rear] = value;
        rear = (rear+1) % elem.length;
        usedSize++;
        return true;
    }
     Each time you add  rear  all   Meeting   backward   a step   Enter into   First  0  Subscript   After adding  1  perform rear = (rear+1) % elem.length;  Can point to 2  that   Find the tail node , Can   return 
        elem[rear - 1] ,  however   There is a terry   Namely   When  rear  by  0  when   Need   The return subscript is  elem.length  Value   Here's another one if  Statement ok

    public boolean deQueue() {
    
        if(isEmpty()) return false;
        front = (front + 1) % elem.length;
        usedSize--;
        return true;
    }

    public int Front() {
    
        if(isEmpty()) return -1;
        return elem[front];
    }

    //  Get the tail element 
    public int Rear() {
    
        if(isEmpty()) return -1;


        int index = -1;
        if(rear == 0) {
    
            index = elem.length - 1;
        }else {
    
            index = rear - 1;
        }
        return elem[index];
    }

    public boolean isEmpty() {
    
        return usedSize == 0;
    }

    public boolean isFull() {
    
        return usedSize == elem.length;

    }


}

Last There is another kind. adopt Sign a To judge full Of Sure Try it This is Do not give Give the answer , Because I didn't write

Completed the circular queue , almost Using arrays To achieve queue That's it. Then Strike while the iron is hot blunt oj topic

Using queue to implement stack

class MyStack {
    
    //  Stack through queue 
    // Not empty  , Empty for 
    Queue<Integer> que1 ;
    Queue<Integer> que2 ;
    public MyStack() {
    
        que1 = new LinkedList<>();
        que2 = new LinkedList<>();
    }

    public void push(int x) {
    
        if(!que1.isEmpty()) {
    
            que1.offer(x);
        }else if(!que2.isEmpty()) {
    
            que2.offer(x);
        }else {
    
            que1.offer(x);
        }
    }

    public int pop() {
    
        if(empty()) return -1;
       if(!que1.isEmpty()) {
    
         int  size = que1.size() - 1;
           for(int i = 0;i<size;i++) {
    
               int ret = que1.poll();
               que2.offer(ret);
           }
           return que1.poll();
       }else {
    
           int  size = que2.size() - 1;
           for(int i = 0;i<size;i++) {
    
               int ret = que2.poll();
               que1.offer(ret);
           }
           return que2.poll();
       }
    }

    public int top() {
    
        if(empty()) return -1;
        int ret = 0;
        if(!que1.isEmpty()) {
    
            int  size = que1.size();
            for(int i = 0;i<size;i++) {
    
               ret = que1.poll();
                que2.offer(ret);
            }
            return ret;
        }
        if(!que2.isEmpty()) {
    
            int  size = que2.size();
            for(int i = 0;i<size;i++) {
    
                ret = que2.poll();
                que1.offer(ret);
            }
            return ret;
        }
        return -1;
    }

    public boolean empty() {
    
        return que1.isEmpty()&&que2.isEmpty();
    }
}

The queue implements Stack that Use stack to realize queue It is not a truth Do you Also use

Two Stack To achieve queue

Let's take a look at logic first

I understand Logic Then go straight to oj Just do it

Using stack to realize queue

class MyQueue {
    

      public Stack<Integer> stack1;
    // Stack queued 
    public Stack<Integer> stack2;
    // Out of the queue stack 

    public MyQueue() {
    
    stack1 = new Stack<>();
    stack2 = new Stack<>();
    }

    public void push(int x) {
    
    stack1.push(x);
    }

    public int pop() {
    
        if(empty()) return -1;
        if(!stack2.empty()) {
    
           int ret =  stack2.pop();
            return ret;
        }else {
    
            int size = stack1.size();
            for(int i = 0;i<size;i++) {
    
                int ret = stack1.pop();
                stack2.push(ret);
            }
            return stack2.pop();
        }
    }

    
    public int peek() {
    
        if(empty()) return -1;
        if(!stack2.empty()) {
    
            int ret =  stack2.peek();
            return ret;
        }else {
    
            int size = stack1.size();
            for(int i = 0;i<size;i++) {
    
                int ret = stack1.pop();
                stack2.push(ret);
            }
            return stack2.peek();
        }
    }

    public boolean empty() {
    
        return stack1.empty() && stack2.empty();
    }
}

Actually queue And Stack Of To learn thing Not much Much of the things how Use him , towards Stack also Monotonic stack , Namely To the top of the stack To Stack low Become a A monotonic increasing or decreasing trend , We Need to know Stack and queue characteristic , Stack : advanced Later queue ： fifo , stay Go to Use stacks and queue solve some Exercises You can get to know them well .