Data Structure | Queue

如同 Stack 一样，Queue 也是一种线性的数据结构。不同点在于 Stack 是后进先出 (Last In First Out)，而 Queue 是先进先出 (First In First Out) FIFO

每次添加 (enqueue) 元素添加在队尾 (back), 每次取出 (dequeue) 元素取出对头 (front)
可以将生活中的排队抽象为 Queue 这种数据结构

enqueue 和 dequeue 操作思路如下
为使一个元素 x enqueue，我们让 currentSize 和 back 增加1，使 currentSize[size] = x
为使元素 dequeue，我们置返回值为 theArray[front], 且 currentSize - 1，然后使 front 加1

Implementing Queue using Array

使用 Array 来实现 Queue 时，要注意的一点是，当 front 为 array.length - 1 时，即 front 指向最后一个元素时，再想要 enqueue 就无法完成了。为解决该问题，我们用到了循环数组实现 (circular array)，即 只要 front 或 back 到达数组的尾端，它就又绕回到开头

Java 实现如下

import java.util.Arrays;

public class Queue<T>{
    private int front;
    private int rear;
    private int size;
    private int capacity;
    private T[] array;

    public Queue(int capacity){
	this.capacity = capacity;
	array = (T[]) new Object[capacity];
	front = 0;
	rear = capacity -1;
	size = 0;
    }

    public boolean isEmpty(Queue q){
 	return (q.size == 0);
    }

    public boolean isFull(Queue q){
	return (q.size == q.capacity);
    }

    public void enqueue(T value){
	if (isFull(this)) return;
	this.rear = (this.rear + 1) % this.capacity;
	this.array[this.rear] = value;
	this.size++;
	System.out.println(value + " enqueued to queue");
    }

    public void dequeue(){
	if (isEmpty(this)) return;
	T value = this.array[this.front];
	array[front] = null;
	this.front = (this.front + 1) % this.capacity;
	this.size --;
	System.out.println(value + " dequeued from queue");
    }

    public T front(){
	if (isEmpty(this)) return null;
	return this.array[this.front];
    }

    public T rear(){
	if (isEmpty(this)) return null;
	return this.array[this.rear];
    }

    @Override
    public String toString(){
	return "Queue front = " + array[front]  +", rear = " + 
	array[rear] + ", size = " + size + ", queue = " + Arrays.toString(array);
    }

    public static void main(String[] args){
	Queue q = new Queue(10);
	q.enqueue(1);   // 1 enqueued to queue
	q.enqueue(2);   // 2 enqueued to queue
	q.enqueue(9);   // 9 enqueued to queue
	q.enqueue(4);   // 4 enqueued to queue

	q.dequeue();    // 1 dequeued from queue
	System.out.println(q.toString());
	// Queue front = 2, rear = 4, size = 3, queue = 
	// [null, 2, 9, 4, null, null, null, null, null, null]
    }
}

所有操作的时间复杂度为 O(1)

Implementing Queue using LinkedList

enqueue 即在 LinkedList 后增加一个 node
dequeue 即 remove head node，move front to next node

class Node{
    int key;
    Node next;

    public Node(int key){
	this.key = key;
	this.next = null;
    }
}

class Queue{
    Node front, rear;

    public Queue(){
	this.front = null;
	this.rear = null;
    }

    void enqueue(int key){
	Node temp = new Node(key);

	if (rear == null){
	    front = temp;
	    rear = temp;
	    return;
	}
	rear.next = temp; // Add the new node at the end of queue
	rear = rear.next;  // Change rear
    }

    Node dequeue(){
	if (front == null) return null;

	Node temp = this.front;
	this.front = this.front.next;

	// If front becomes NULL, then change rear also as NULL
	if (this.front == null) this.rear = null;
	return temp;
    } 

    public static void main(String[] args){
	Queue q = new Queue();
	q.enqueue(1);   
	q.enqueue(2);  
	q.enqueue(9);   
	q.enqueue(4);      
	System.out.println("Dequeued item is: " + q.dequeue().key); // 1
    }
}

Implementing Queue using Stack

使用两个 stack 来实现 Queue
push() 把元素添加到最底端
pop() 把最顶端的元素取出
peek() 返回最顶端的元素
isEmpty() 看 Queue 是否为空

除了 push() 在 Stack 和 Queue 中表示不同的含义以外，其余的方法都是一样的
push() 在 Stack 中是把元素添加到最顶端，而在 Queue 中，秉承着 FIFO 的原则，push() 表示把元素添加到最底端

如何实现呢，这里提供一种思路
使用两个 stack，当需要把元素添加到 stack1 中时，先把 stack1 中的现有元素转移到 stack2 中
再 push()，然后把 stack2 中元素再转移到 stack1 中

Java 代码实现如下

import java.util.Stack;

public class Queue{
    Stack<Integer> temp = new Stack<>();
    Stack<Integer> stack = new Stack<>();

    public void push(int i){
	if (stack.isEmpty()) stack.push(i);
	else {
	    while (!stack.isEmpty()){
		temp.push(stack.pop());
	    }
	    stack.push(i);
	    while (!temp.isEmpty()){
		stack.push(temp.pop());
	    }
	}
    }

    public int pop(){
	return stack.pop();
    }

    public int peek(){
	return stack.peek();
    }

    public boolean isEmpty(){
	return stack.isEmpty();
    }

    public static void main(String[] args){}
}

关于 Queue，有个有趣的应用 ———> 在这里
即给定一个数 n，返回从 1 到 n 的所有二进制数

GeeksforGeeks 上提供的算法是这样的

1) Create an empty queue of strings
2) Enqueue the first binary number “1” to queue.
3) Now run a loop for generating and printing n binary numbers.
……a) Dequeue and Print the front of queue.
……b) Append “0” at the end of front item and enqueue it.
……c) Append “1” at the end of front item and enqueue it.

Source: http://www.geeksforgeeks.org/interesting-method-generate-binary-numbers-1-n/

Java 实现如下：

import java.util.Queue;
import java.util.LinkedList;

public class QueueApp{
    public static void printBinary(int n){
	Queue<String> q = new LinkedList<String>();
	q.add("1");
	for (int i = 0; i < n; i++){
	    String temp = q.remove();
	    System.out.println(temp);
	    q.add(temp + "0");
	    q.add(temp + "1");
	}
    }

    public static void main(String[] args){
	printBinary(7);
    }
}

运行结果如下：

1
10
11
100
101
110
111

Queue 由于其 FIFO 的特点，在我们不知道 input size 而又要将 input 存入到 array 中去时，queue 就可以派上用场了
先将元素 enqueue 到 queue 中，再求 q.size()，再将元素 dequeue 到 array 中

import java.io.*;
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class QueueArray{
    public static void main(String[] args){
	try{
	    File f = new File(args[0]);
	    Scanner scan = new Scanner(f);

	    Queue<Integer> q = new LinkedList<Integer>();
	    while (scan.hasNextInt()){
		q.add(scan.nextInt());
	    }

	    int[] array = new int[q.size()];

	    for(int i = 0; i < q.size(); i++){
		array[i] = q.remove();
	    }
	} catch (FileNotFoundException e){
	    System.out.println("File not found.");
	} catch (ArrayIndexOutOfBoundsException e){
	    System.out.println("Please enter a file name.");
	}
    }
}

---

关于 Queue 的讨论就到这里
以上内容如有疏漏或不足之处，欢迎与我讨论
邮箱：entropy714@gmail.com
微信：cobain0714