队列基本概念
1 数据集合
队列的数据集合可以表示为a0,a1,…,an-1,每个数据元素的数据类型可以是任意的类型。
2 操作集合
(1)入队列append(obj):把数据元素obj插入队尾。
(2)出队列delete():把队头数据元素删除并由函数返回。
(3)取队头数据元素getFront():取队头数据元素并由函数返回。
(4)非空否isEmpty():非空否。若队列非空,则函数返回false,否则函数返回true。
队列抽象数据类型的Java接口定义如下:
public interface Queue{
public voidappend(Object obj) throws Exception;
public Object delete()throws Exception;
public ObjectgetFront() throws Exception;
public booleanisEmpty();
}
顺序队列
当rear和front达到maxSize-1后,再加1就自动到0。这样,就不会出现顺序队列数组的头部已空出许多存储空间,但队尾却因数组下标越界而引起溢出的假溢出问题。
(1)设计一个布尔变量以判断队列的空和满;
(2)少用一个存储空间。
(3)设计一个计数器,统计队列中得元素个数。
1)设计一个布尔变量以判断队列的空和满;
添加一个标志位。设标志位为tag,初始时置tag=0;每当入队列操作成功就置tag=1;每当出队列操作成功就置tag=0。则队列空的判断条件为:
rear == front&& tag==0
队列满的判断条件为:
rear = = front&& tag= =1
当少用一个存储空间时,以队尾rear加1等于队头 front为队列满的判断条件,即队列满的判断条件此时为:
(rear + 1) % maxSize== front
队列空的判断条件仍然为:
rear = = front
3)设计一个计数器,统计队列中得元素个数。
添加一个计数器。设计数器为count,初始时置count=0;每当入队列操作成功就使count加1;每当出队列操作成功就使count减1。这样,该计数器不仅具有计数功能,而且还具有像标志位一样的标志作用,则此时队列空的判断条件为:
count == 0
队列满的判断条件为:
count > 0&& rear == front
顺序循环队列的实现
//队列接口 public interface Queue { //入队 public void append(Object obj) throws Exception; //出队 public Object delete() throws Exception; //获得队头元素 public Object getFront() throws Exception; //判断对列是否为空 public boolean isEmpty(); }
//循环顺序队列 public class CircleSequenceQueue implements Queue{ static final int defaultSize = 10; //默认队列的长度 int front; //队头 int rear; //队尾 int count; //统计元素个数的计数器 int maxSize; //队的最大长度 Object[] queue; //队列 public CircleSequenceQueue() { init(defaultSize); } public CircleSequenceQueue(int size) { init(size); } public void init(int size) { maxSize = size; front=rear=0; count=0; queue = new Object[size]; } @Override public void append(Object obj) throws Exception { // TODO Auto-generated method stub if(count>0&&front==rear) { throw new Exception("队列已满!"); } queue[rear]=obj; rear=(rear+1)%maxSize; count++; } @Override public Object delete() throws Exception { // TODO Auto-generated method stub if(isEmpty()) { throw new Exception("队列为空!"); } Object obj = queue[front]; front = (front+1)%maxSize; count--; return obj; } @Override public Object getFront() throws Exception { // TODO Auto-generated method stub if(!isEmpty()) { return queue[front]; } else { return null; } } @Override public boolean isEmpty() { // TODO Auto-generated method stub return count==0; } }
循环队列应用
//卖票者 public class Consumer implements Runnable { WindowQueue queue ; public Consumer(WindowQueue queue) { this.queue = queue; } @Override public void run() { // TODO Auto-generated method stub while(queue.isAlive) { try { queue.consumer(); } catch(Exception ex) { ex.printStackTrace(); } } } }
//买票者 public class Producer implements Runnable { WindowQueue queue ; public Producer(WindowQueue queue) { this.queue = queue; } @Override public void run() { // TODO Auto-generated method stub while(queue.num<100) { try { queue.producer(); } catch(Exception ex) { ex.printStackTrace(); } } } }
//卖票窗口 public class WindowQueue { //卖票的队列 int maxSize =10; CircleSequenceQueue queue = new CircleSequenceQueue(maxSize); int num=0; //统计卖票的数量,一天最多卖100张票。 boolean isAlive = true; //判断是否继续卖票。 //排队买票 public synchronized void producer() throws Exception { if(queue.count < maxSize) { queue.append(num++); //等待买票的数量加1 System.out.println("第"+num+"个客户排队等待买票!"); this.notifyAll();//唤醒卖票的线程 } else { try { System.out.println("队列已满...请等待!"); this.wait();//队列满时,排队买票线程等待。 } catch(Exception ex) { ex.printStackTrace(); } } } //卖票 public synchronized void consumer() throws Exception { if(queue.count > 0) { Object obj = queue.delete(); int temp = Integer.parseInt(obj.toString()); System.out.println("第"+(temp+1)+"个客户买到票离开队列!"); //如果当前队列为空,并且卖出票的数量大于等于100,说明卖票结束 if(queue.isEmpty()&&this.num>=100) { this.isAlive = false; } this.notifyAll(); //唤醒排队买票的线程。 } else { try { System.out.println("队列已空...请等待!"); this.wait();//队列空时,卖票线程等待。 } catch(Exception ex) { ex.printStackTrace(); } } } }
public class Test { /** * @param args */ public static void main(String[] args)throws Exception { WindowQueue queue = new WindowQueue(); Producer p = new Producer(queue);//注意一定要传同一个窗口对象 Consumer c = new Consumer(queue); //排队买票线程 Thread pThread = new Thread(p); //卖票线程 Thread cThread = new Thread(c); pThread.start(); //开始排队买票 cThread.start(); //开始卖票 } }