Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3965585
  • 博文数量: 408
  • 博客积分: 10227
  • 博客等级: 上将
  • 技术积分: 9820
  • 用 户 组: 普通用户
  • 注册时间: 2009-04-17 21:48
个人简介

非淡泊无以明志,非宁静无以致远

文章存档

2022年(1)

2021年(1)

2020年(2)

2019年(5)

2018年(4)

2017年(3)

2016年(24)

2015年(8)

2014年(7)

2013年(3)

2012年(1)

2011年(23)

2010年(179)

2009年(147)

分类: C/C++

2010-03-28 20:37:42

一.队列的定义及其运算

1
、定义
   
 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。
 
 (1)允许删除的一端称为队头(Front)。
  (2)允许插入的一端称为队尾(Rear)。
  (3)当队列中没有元素时称为空队列。
  (4)队列亦称作先进先出(First In First Out)的线性表,简称为FIFO表。

  队列的结构特点是先进队的元素先出队。假设有队列Q=(a1,a2,...,an),则队列Q中的元素是按a1,a2,...,an的次序进队,而第一个出队的应该是a1,第二个出队的应该是a2,只有在ai-1出队后, ai才可以出队(1≤i≤n),如图3.9所示。
   
 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾(即不允许"加塞"),每次离开的成员总是队列头上的(不允许中途离队),即当前"最老的"成员离队。
 
2
、队列的基本逻辑运算

与栈类似,队列的运算可以归纳为以下几种:
1. AddQ(ElemType x)
——
在队列的尾部插入一个新的元素x。队尾的位置由rear指出。

2. DelQ(Q)
——
删除队列的队头的元素。队头的位置由front指出。
3. EmptyQ(Q)
——
测试队列Q是否为空队。当队列为空时返回一个真值,否则返回一个假值。
4. FrontQ(Q)
——
取得队列Q的队头元素。该运算与DelQ(Q)不同,后者要修改队头元素指针。
5. SetNULL(Q)
——
创建一个空队Q,这个运算与线性表置空表类似

二.顺序队列
 
1)顺序队列的定义
   队列的顺序存储结构称为顺序队列,队列的顺序存储结构和栈类似,在计算机中,常借助于一维数组来存储队列中的元素,顺序队列实际上是运算受限的顺序表。
2) 顺序队列的表示
  和顺序表一样,顺序队列用一个向量空间来存放当前队列中的元素。
  由于队列的队头和队尾的位置是变化的,设置两个指针frontrear分别指示队头元素和队尾元素在向量空间中的位置,它们的初值在队列初始化时均应置为0,见图3.12
         
队列的顺序存储结构可描述为:
typedef int ElemType;
struct SeQueuestr { ElemType elem[MAXSIZE];
                    int front,rear;
} ;
    
3) 顺序队列的基本操作

  入队时:将新元素插入rear所指的位置,然后将rear1
  出队时:删去front所指的元素,然后将front1并返回被删元素。
 
注意:
     ①当头尾指针相等时,队列为空。
      ②
在非空队列里,队头指针始终指向队头元素,尾指针始终指向队尾元素的下一位置。
   
 顺序队列在入队和出队操作时的具体算法演示请点击查看

4)顺序队列中的溢出现象
  ① "下溢"现象
   
 当队列为空时,做出队运算产生的溢出现象。下溢是正常现象,常用作程序控制转移的条件。
  ② "真上溢"现象
   
 当队列满时,做进栈运算产生空间溢出的现象。真上溢是一种出错状态,应设法避免。
  ③ "假上溢"现象
  由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。

解决假溢出的方法有两种:
  (1) 采用平移元素的方法,即一旦发生假溢出就把整个队列的元素平移到存储区的首部。平移元素的方法效率是很低的。
  (2)将整个队列作为循环队列来处理,。这样,虽然物理上队尾在队首之前,但逻辑上队首仍然在前,作插入和删除运算时仍按"先进先出"的原则。

三.循环队列
   
 为充分利用向量空间,克服"假上溢"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。
     
在循环队列中只凭等式rear==front无法判别队空还是队满。因此,可再设置一个布尔变量来区分队空和队满,或者不设布尔变量,而把尾指针加1后等于头指针作为队满的标志。这意味着损失一个空间,或者反过来说,拥有MAXSIZE个数组元素的数组仅能表示一个长度为MAXSIZE-1的循环队列。
循环队列的类定义

循环队列实质上仍然还是顺序存储结构,只是形式上有所改变而已。现在用面向对象的方法来设计循环队列的类。
1.
循环队列的类定义:

class SeQueue
{ private:
      ElemType elem[MAXSIZE];
      int front,rear;
  public:
      SeQueue();
      ~SeQueue();
      void Display();
      void AddQ(ElemType x);
      ElemType DelQ();
};
2.
下面给出循环队列的运算算法:
(1)
将循环队列置为空
//
将队列初始化
SeQueue::SeQueue()
{  front=0;
   rear=0;
   cout<<"init!"<}
(2)
判断循环队列是否为空
int SeQueue::Empty()
{  if(rear==front) return(1);
   else return(0);
}
(3)
在循环队列中插入新的元素x
void SeQueue::AddQ(ElemType x)
{ if((rear+1) % MAXSIZE==front) cout<<" QUEUE IS FULL! "<  else{ rear=(rear+1) % MAXSIZE;
     elem[rear]=x;
     cout<<" OK!";
     }
}
(4)
删除队列中队首元素
ElemType SeQueue::DelQ()
{ if(front==rear)
     { cout<<" QUEUE IS EMPTY! "<  else{ front=(front+1) % MAXSIZE;
     return(elem[front]);
     }
}
(5)
取队列中的队首元素
ElemType SeQueue::Front()
{  ElemType x;
   if(front== rear)
     cout<<"QUEUE IS EMPTY "<   else x= elem[(front+1)%MAXSIZE];
   return (x);
}

四.链队列
1
链队列的定义
 
 用链表表示的队列简称为链队列.一个链队列显然需要两个指针才能唯一确定,它们分别指示队头和队尾(分别称为头指针和尾指针)。与线性表的单链表一样,为了操作方便起见,我们也给链队列添加了一个头结点,并令头指针指向头结点.由此,空的链队列的判别条件为头指针和尾指针均指向头结点   
2
链队列的类定义

队列采用链表存储结构时,需要两个指针才能唯一确定,它们分别指示队头和队尾(分别称为头指针和尾指针)。同时,我们把头、尾指针作为类的私有成员来处理。链队列的各种操作设计为类的函数成员。
class LsQueue
{  private:
      quenode *front, *rear;
   public:
      LsQueue();
      ~LsQueue();
      void Display();
      void AddQ(ElemType x);
      ElemType DelQ();
};

3
链队列的基本运算
(1)
判队列是否为空
int LsQueue::Empty()
{
   if(front==rear) return(1);
   else return(0);
}
(2)
在队尾结点之后插入一个元素
void LsQueue::AddQ(ElemType x)       //
值为x 的结点入队
{ quenode *s;
  s=new quenode;
  s->data=x;
  s->next=NULL;
  rear->next=s;
  rear=s;
}
(3)
删除队头元素
ElemType LsQueue::DelQ() //
出队一个元素
{ ElemType x; quenode *p;
  if ( front==rear) {cout<<"\n
队列为空。"<  else { p=front->next;
  front->next=p->next;
  if(p->next==NULL) rear=front; //
防止尾指针丢失

  x=p->data; free(p);
      }
  return x;
}
(4)
取队列首元素
ElemType LsQueue::Front()
{ ElemType x;
  NodeType *p;
  if(Empty())
  cout<<"QUEUE IS EMPTY!"<  else{
        p=front->next;
        x=p->data;
  return (x);
      }
}
  链式队列的优点是便于实现存储空间的共享.在同时存在多个队列的情况下,采用链式存崐储结构是比较理想的。
 
注意:
   
 和链栈类似,无须考虑判队满的运算及上溢。
   
 在出队算法中,一般只需修改队头指针。但当原队中只有一个结点时,该结点既是队头也是队尾,故删去此结点时亦需修改尾指针,且删去此结点后队列变空。
   
 以上讨论的是无头结点链队列的基本运算。和单链表类似,为了简化边界条件的处理,在队头结点前也可附加一个头结点,增加头结点的链队列的基本运算

阅读(6333) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~