queue

When we talk about queues, we often think of stacks, because stacks are LIFO and queues are FIFO
As for stack, it has been written before: [data structure and algorithm] 05 judge whether the string of stack classic interview questions is legal (Java version)
The main focus of this article is on queues

Queue, do you have a first reaction? Whether it's buying food in the canteen, handling business in the bank, or entering the high-speed railway station, you will always queue up
There is an obvious characteristic of queuing: those who come early will finish their work early
This is the queue: first in, first out

Queues can be implemented by arrays, called sequential queues, or by linked lists, called chained queues
Here, we use array and linked list to realize it

Array implementation queue

Using arrays to implement queues is relatively simple, because arrays and queues are linear table structures
No more nonsense, let's look at the code directly

/**
 * Using array to realize queue
 * @author Zheng Lu Lu
 * @date 2020-1-29 15:51:32
 */
public class ArrayQueue {
    /**
       Array: items, array size: n
     */
    private String[] items;
    private int n = 0;
    /**
       head Indicates team head and tail
     */
    private int head = 0;
    private int tail = 0;

    /**
       Request an array of size capacity
     */
    public ArrayQueue(int capacity) {
        items = new String[capacity];
        n = capacity;
    }

    /**
       Join the team
     */
    public boolean enqueue(String item) {
        // If tail == n, the queue is full
        if (tail == n) return false;
        items[tail] = item;
        tail++;
        return true;
    }

    /**
       Team out
     */
    public String dequeue() {
        // If head == tail, the queue is empty
        if (head == tail) return null;
        String ret = items[head];
        head++;
        return ret;
    }

    public void printAll() {
        for (int i = head; i < tail; i++) {
            System.out.print(items[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArrayQueue queue=new ArrayQueue(5);
        queue.enqueue("1");
        queue.enqueue("2");
        queue.enqueue("3");
        queue.enqueue("4");
        queue.enqueue("5");
        queue.dequeue();
        queue.enqueue("6");

        queue.printAll();
    }
}

There is a problem in using arrays to implement queues, that is, deleting is not really deleting, it only points the value of i to the head when printing, but the data to be deleted is still in the array

Linked list implementation queue

Using linked lists to implement queues is also relatively simple:

/**
 * Realization of queue with linked list
 * @author Zheng Lu Lu
 * @date 2020-1-30 09:20:41
 */
public class LinkListQueue {
    /**
        The head and tail of the queue
     */
    private Node head = null;
    private Node tail = null;

    /**
         Join the team
     */
    public void enqueue(String value) {
        if (tail == null) {
            Node newNode = new Node(value, null);
            head = newNode;
            tail = newNode;
        } else {
            tail.next = new Node(value, null);
            tail = tail.next;
        }
    }

    /**
        Team out
     */
    public String dequeue() {
        if (head == null) return null;

        String value = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return value;
    }

    public void printAll() {
        Node p = head;
        while (p != null) {
            System.out.print(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    private static class Node {
        private String data;
        private Node next;

        public Node(String data, Node next) {
            this.data = data;
            this.next = next;
        }

        public String getData() {
            return data;
        }
    }

    public static void main(String[] args) {
        LinkListQueue queue=new LinkListQueue();
        queue.enqueue("3");
        queue.enqueue("2");
        queue.dequeue();
        queue.printAll();
    }
}

Stack implementation queue

In addition to using arrays and linked lists, another way is to use stacks to implement queues
To use stack to implement queue, just as the name implies, only stack operations can be used: pop, push, peek, etc. other operations are not allowed, otherwise, stack is not used to implement queue
Using arrays and linked lists to implement stacks is relatively simple, because when reading data, you only need to read in order
But for the stack, sequential reading is not feasible. Why? If my queue data is 1,2,3,4 and then read in sequence, it is 4,3,2,1 because the stack is last in first out
If we use stacks to implement queues, we need to use two stacks. The output order of one stack is 4,3,2,1. Before reading, we store the read data in another stack, and then read from the later stack. Then the output order is 1,2,3,4, which is consistent with the original queue data
Note here: when there is data in the back stack and there is data in the front stack, first read the data in the back stack, and then put the front data in the back data
Next, let's look at the code implementation:

/**
 * Using stack to implement queue
 * @author Zheng Lu Lu
 * @date 2020-1-30 17:21:19
 */
public class StackQueue {
    private  static Stack<Integer> stackTemp = new Stack<Integer>();
    private static Stack<Integer> stackQueue = new Stack<Integer>();

    /**
       Join the team
     */
    public void push(int x){
        stackTemp.push(x);
    }

    /**
        Team out
     */
    public int pop(){
        // When the whole queue is not empty
        if (empty()!=0){
            // If stackQueue is empty, put the data in stackTemp into stackQueue
            // If stackQueue is not empty, output directly
            if (stackQueue.isEmpty()){
                backFill();
            }
            return stackQueue.pop();
        }else {
            // If the whole queue is empty, - 1 is returned, indicating that there is no value in the queue
            System.out.println("Queue is empty");
            return -1;
        }
    }
    public int empty(){
        // Judge whether the queue is empty. If the return value is 0, it means the queue is empty
        // Note that when both stacks are empty, the queue is empty
        return stackQueue.size() + stackTemp.size();
    }
    /**
        Put the data in stackTemp into stackQueue
     */
    public void backFill(){
        while (!stackTemp.isEmpty()){
            stackQueue.push(stackTemp.pop());
        }
    }
    public static void main(String[] args){
        StackQueue stack = new StackQueue();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        stack.push(4);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

That's what I want to share
Thank you for reading~