队列的介绍

队列（Queue），是一种线性存储结构。它有以下几个特点：
(01) 队列中数据是按照"先进先出（FIFO, First-In-First-Out）"方式进出队列的。
(02) 队列只允许在"队首"进行删除操作，而在"队尾"进行插入操作。
队列通常包括的两种操作：入队列 和 出队列。

add，将val值添加到队列的末尾。

pop，返回队列首部，并且删除队列首部。

1，队列的示意图

队列中有10，20，30共3个数据。

2，出队列

出队列前：队首是10，队尾是30。
出队列后：出队列(队首)之后。队首是20，队尾是30。

3，入队列

入队列前：队首是20，队尾是30。
入队列后：40入队列(队尾)之后。队首是20，队尾是40。

 

队列的java实现

JDK包Queue中的也提供了"队列"的实现。JDK中的Queue接口就是"队列"，它的实现类也都是队列，用的最多的是LinkedList。

1. Java实现一：数组实现的队列，能存储任意类型的数据。
2. Java实现二：Java的 Collection集合 中自带的"队列"(LinkedList)的示例。

1. Java实现一：数组实现的队列，能存储任意类型的数据

实现代码(ArrayQueue.java)

/**
 * Java : 数组实现“队列”，只能存储int数据。
 *
 * @author skywang
 * @date 2013/11/07
 */
public class ArrayQueue {

    private int[] mArray;
    private int mCount;

    public ArrayQueue(int sz) {
        mArray = new int[sz];
        mCount = 0;
    }

    // 将val添加到队列的末尾
    public void add(int val) {
        mArray[mCount++] = val;
    }

    // 返回“队列开头元素”
    public int front() {
        return mArray[0];
    }

    // 返回“栈顶元素值”，并删除“栈顶元素”
    public int pop() {
        int ret = mArray[0];
        mCount--;
        for (int i=1; i<=mCount; i++)
            mArray[i-1] = mArray[i];
        return ret;
    }

    // 返回“栈”的大小
    public int size() {
        return mCount;
    }

    // 返回“栈”是否为空
    public boolean isEmpty() {
        return size()==0;
    }

    public static void main(String[] args) {
        int tmp=0;
        ArrayQueue astack = new ArrayQueue(12);

        // 将10, 20, 30 依次推入栈中
        astack.add(10);
        astack.add(20);
        astack.add(30);

        // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
        tmp = astack.pop();
        System.out.printf("tmp=%d\n", tmp);

        // 只将“栈顶”赋值给tmp，不删除该元素.
        tmp = astack.front();
        System.out.printf("tmp=%d\n", tmp);

        astack.add(40);

        System.out.printf("isEmpty()=%b\n", astack.isEmpty());
        System.out.printf("size()=%d\n", astack.size());
        while (!astack.isEmpty()) {
            System.out.printf("size()=%d\n", astack.pop());
        }
    }
}

运行结果：

tmp=10
tmp=20
isEmpty()=false
size()=3
size()=20
size()=30
size()=40

结果说明：ArrayQueue是通过数组实现的队列，而且ArrayQueue中使用到了泛型，因此它支持任意类型的数据。

2. Java实现二：Java的 Collection集合 中自带的"队列"(LinkedList)的示例

实现代码(MyQueue.java)

import java.util.LinkedList;
public class MyQueue
{
  private LinkedList list = new LinkedList();
  public void clear()//销毁队列
  {
	  list.clear();
  }
  public boolean QueueEmpty()//判断队列是否为空
  {
	  return list.isEmpty();
  }
  public void enQueue(Object o)//进队
  {
	  list.addLast(o);
  }
  public Object deQueue()//出队
  {
	  if(!list.isEmpty())
	  {
		  return list.removeFirst();
	  }
	  return "队列为空";
  }
  public int QueueLength()//获取队列长度
  {
	  return list.size();
  }
  public Object QueuePeek()//查看队首元素
  {
	  return list.getFirst();
  }
  public static void main(String[] args)//测试队列
  {
	  MyQueue queue = new MyQueue();
	  System.out.println(queue.QueueEmpty());
	  queue.enQueue("a");
	  queue.enQueue("b");
	  queue.enQueue("c");
	  queue.enQueue("d");
	  queue.enQueue("e");
	  queue.enQueue("f");
	  System.out.println(queue.QueueLength());
	  System.out.println(queue.deQueue());
	  System.out.println(queue.deQueue());
	  System.out.println(queue.QueuePeek());
	  System.out.println(queue.deQueue());
	  queue.clear();
	  queue.enQueue("s");
	  queue.enQueue("t");
	  queue.enQueue("r");
	  System.out.println(queue.deQueue());
	  System.out.println(queue.QueueLength());
	  System.out.println(queue.QueuePeek());
	  System.out.println(queue.deQueue());
  }
}

运行结果：

true
6
a
b
c
c
s
2
t
t