队列在计算机术语中使用queue,和list(排)其实是一个意思。队列也是一种数据结构,类似于栈,只是与栈相反,在队列中最先插入的数据也最先被移除,即先进先出(FIFO,First In First Out)。队列可以理解成排队,比如,食堂窗口排的队,越在前面的,越早得到服务而先离开。在银行大厅的排号的机器也许就用了队列这个数据结构。在打印的时候,有“添加到队列”的选项,队列应用是很广泛的。
队列的操作有:插入到队尾数据项,移除队头数据项,查看数据项等功能。
下面用Java实现队列的基本功能(数组版)。
package cn.zhf.list; public class MyQueue { private int maxSize;//定义最大容量 private int[] qarray;//存放元素的数组 private int front;//前一个元素索引 private int rear;//后一个元素索引 private int nItems;//队列中元素的个数 //构造对象并初始化 public MyQueue(int s){ maxSize = s; qarray = new int[maxSize]; front = 0; rear = -1; nItems = 0; } //在队列尾端插入元素 public void enqueue(int i){ if(rear == maxSize - 1){ rear = -1; } qarray[++rear] = i; nItems++; } //删除队首元素 public int dequeue(){ int temp = qarray[front++]; if(front == maxSize){ front = 0; } nItems--; return temp; } public int peekFront(){//取第一个元素 return qarray[front]; } public boolean isEmpty(){ return (nItems == 0); } public static void main(String[] args) { MyQueue queue = new MyQueue(5); queue.enqueue(1); queue.enqueue(2); queue.enqueue(3); queue.enqueue(4); queue.enqueue(5); while(!queue.isEmpty()){ int i = queue.dequeue(); System.out.println(i); } } } |