你好,游客 登录 注册 搜索
背景:
阅读新闻

数据结构之队列

[日期:2014-12-09] 来源:CSDN博客  作者:冰河winner [字体: ]

栈是“后进先出”(LIFO,Last InFirst Out)的数据结构,与之相反,队列是“先进先出”(FIFO,First InFirst Out)的数据结构。

队列的作用就像售票口前的人们站成的一排一样:第一个进入队列的人将最先买到票,最后排队的人最后才能买到票。

在计算机操作系统或网路中,有各种队列在安静地工作着。打印作业在打印队列中等待打印。当敲击键盘时,也有一个存储键盘键入内容的队列,如果我们敲 击了一个键,而计算机又暂时在做其他事情,敲击的内容不会丢失,它会排在队列中等待,直到计算机有时间来读取它,利用队列保证了键入内容在处理时其顺序不 会改变。

栈的插入和删除数据项的命名方法很标准,成为push和pop,队列的方法至今也没有一个标准化的方法,插入可以称作put、add或enque等,删除可以叫作delete、get、remove或deque等。

队列

下面我们依然使用数组作为底层容器来实现一个队列的操作封装,与栈不同的是,队列的数据项并不都是从数组的第一个下标开始,因为数据项在数组的下标越小代表其在队列中的排列越靠前,移除数据项只能从队头移除,然后队头指针后移,这样数组的前几个位置就会空出来如下图所示:

这与我们的直观感觉相反,因为我们排队买票时,队列总是向前移动,当前面的人买完票离开后,其他人都向前移动,而在我们的设计中,队列并没有向前移动,因为那样做会使效率大打折扣,我们只需要使用指针来标记队头和队尾,队列发生变化时,移动指针就可以,而数据项的位置不变。

但是,这样的设计还存在着一个问题,随着队头元素不断地移除,数组前面空出的位置会越来越多,当队尾指针移到最后的位置时,即使队列没有满,我们也不能再插入新的数据项了。

解决这种缺点的方法是环绕式处理,即让队尾指针回到数组的第一个位置:

这就是循环队列(也成为缓冲环)。虽然在存储上是线形的,但是在逻辑上它是一个首尾衔接的环形。

  1. public class Queue { 
  2.        
  3.       private int [] queArray; 
  4.       private int maxSize; 
  5.       public int front;   //存储队头元素的下标 
  6.       public int rear;    //存储队尾元素的下标 
  7.       private int length; //队列长度 
  8.        
  9.       //构造方法,初始化队列 
  10.       public Queue(int maxSize){ 
  11.              this.maxSize = maxSize; 
  12.              queArray = new int [maxSize]; 
  13.              front = 0
  14.              rear = -1
  15.              length = 0
  16.       } 
  17.        
  18.       //插入 
  19.       public void insert(int elem) throwsException{ 
  20.              if(isFull()){ 
  21.                     throw new Exception("队列已满,不能进行插入操作!"); 
  22.              } 
  23.              //如果队尾指针已到达数组的末端,插入到数组的第一个位置 
  24.              if(rear == maxSize-1){ 
  25.                     rear = -1
  26.              } 
  27.              queArray[++rear] = elem; 
  28.              length++; 
  29.       } 
  30.        
  31.       //移除 
  32.       public int remove() throws Exception{ 
  33.              if(isEmpty()){ 
  34.                     throw new Exception("队列为空,不能进行移除操作!"); 
  35.              } 
  36.              int elem = queArray[front++]; 
  37.              //如果队头指针已到达数组末端,则移到数组第一个位置 
  38.              if(front == maxSize){ 
  39.                     front = 0
  40.              } 
  41.              length--; 
  42.              returnelem; 
  43.       } 
  44.        
  45.       //查看队头元素 
  46.       public int peek() throws Exception{ 
  47.              if(isEmpty()){ 
  48.                     throw new Exception("队列内没有元素!"); 
  49.              } 
  50.              return queArray[front]; 
  51.       } 
  52.        
  53.       //获取队列长度 
  54.       public int size(){ 
  55.              return length; 
  56.       } 
  57.        
  58.       //判空 
  59.       public boolean isEmpty(){ 
  60.              return (length == 0); 
  61.       } 
  62.        
  63.       //判满 
  64.       public boolean isFull(){ 
  65.              return (length == maxSize); 
  66.       } 
  67.        

 

还有一种称为双端队列的数据结构,队列的每一端都可以进行插入和移除操作。

其实双端队列是队列和栈的综合体。如果限制双端队列的一段只能插入,而另一端只能移除,就变成了平常意义上的队列;如果限制双端队列只能在一端进行插入和移除,就变成了栈。

优先级队列

像普通队列一样,优先级队列有一个队头和一个队尾,并且也是从队头移除数据,从队尾插入数据,不同的是,在优先级队列中,数据项按关键字的值排序,数据项插入的时候会按照顺序插入到合适的位置。

除了可以快速访问优先级最高的数据项,优先级队列还应该可以实现相当快的插入,因此,优先级队列通常使用一种称为堆的数据结构来实现。在下例中,简便起见,我们仍然使用数组来实现

在数据项个数比较少,或不太关心速度的情况下,用数组实现优先级队列还可以满足要求,如果数据项很多,或对速度要求很高,采用堆是更好的选择

优先级队列的实现跟上面普通队列的实现有很大的区别。

优先级队列的插入本来就需要移动元素来找到应该插入的位置,所以循环队列那种不需要移动元素的优势就不太明显了。在下例中,没有设置队头和队尾指 针,而是使数组的第一个元素永远是队尾,数组的最后一个元素永远是队头,为什么不是相反的呢?因为队头有移除操作,所以将队头放在数组的末端,便于移除, 如果放在首段,每次移除队头都需要将队列向前移动。

                                                                                  插入元素示意图

 

                                                                                             

                                                                                                移除元素示意图


在下例中,我们设置了一个基准点,认为元素到里基准点的距离越近则优先级越高,如设置的基准点为2,3到2的距离就是|3-2|=1,而-1到2的距离是|-1-2|=3,所以2的优先级就比-1要高。

 

  1. public class PriorityQueue { 
  2.        
  3.       private int [] queArray; 
  4.       private int maxSize; 
  5.       private int length; //队列长度 
  6.       private int referencePoint;  //基准点 
  7.        
  8.       //构造方法,初始化队列 
  9.       public PriorityQueue(int maxSize,intreferencePoint){ 
  10.              this.maxSize= maxSize; 
  11.              this.referencePoint =referencePoint; 
  12.              queArray = new int [maxSize]; 
  13.              length = 0
  14.       } 
  15.        
  16.       //插入 
  17.       public void insert(int elem) throwsException{ 
  18.              if(isFull()){ 
  19.                     throw new Exception("队列已满,不能进行插入操作!"); 
  20.              } 
  21.              
  22.              //如果队列为空,插入到数组的第一个位置 
  23.              if(length == 0){ 
  24.                     queArray[length++] = elem; 
  25.              }else
  26.                     int i; 
  27.                     for(i=length;i>0;i--){ 
  28.                            
  29.                            int dis =Math.abs(elem-referencePoint);  //待插入元素的距离 
  30.                            int curDis =Math.abs(queArray[i-1]-referencePoint); //当前元素的距离 
  31.                            
  32.                            //将比插入元素优先级高的元素后移一位 
  33.                            if(dis>= curDis){ 
  34.                                   queArray[i] =queArray[i-1]; 
  35.                            }else
  36.                                   break
  37.                            } 
  38.                     } 
  39.                     queArray[i] = elem; 
  40.                     length++; 
  41.              } 
  42.       } 
  43.        
  44.       //移除 
  45.       public int remove() throws Exception{ 
  46.              if(isEmpty()){ 
  47.                     throw new Exception("队列为空,不能进行移除操作!"); 
  48.              } 
  49.              int elem = queArray[--length]; 
  50.              return elem; 
  51.       } 
  52.        
  53.       //查看队头元素 
  54.       public int peek() throws Exception{ 
  55.              if(isEmpty()){ 
  56.                     throw new Exception("队列内没有元素!"); 
  57.              } 
  58.              return queArray[length-1]; 
  59.       } 
  60.        
  61.       //返回队列长度 
  62.       public int size(){ 
  63.              return length; 
  64.       } 
  65.        
  66.       //判空 
  67.       public boolean isEmpty(){ 
  68.              return (length == 0); 
  69.       } 
  70.        
  71.       //判满 
  72.       public boolean isFull(){ 
  73.              return (length == maxSize); 
  74.       } 
  75.        

  76. 原文链接:http://blog.csdn.net/u012152619/article/details/41799569




收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款