种豆资源网

当前位置:首页 > 百科 > 百科综合 / 正文

顺序伫列

(2019-05-13 05:20:15) 百科综合
顺序伫列

顺序伫列

顺序伫列是伫列的顺序存储结构,顺序伫列实际上是运算受限的顺序表。和顺序表一样,顺序伫列用一个向量空间来存放当前伫列中的元素。由于伫列的队头和队尾的位置是变化的,设定两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置,它们的初值在伫列初始化时均应设定为0。

基本介绍

  • 中文名:顺序伫列
  • 外文名:sequential queue

套用背景

在现实世界中存在很多伫列的实例。例如,在电影院的售票视窗排队等待买票的人,就是通过伫列这种数据结构组织在一起的。人们按先来后到的顺序排成一队,最先买到票的人就是最先来的人。当某人买完票,他就会从伫列的最前端离开,这就相当于删除操作。而添加的操作却仅能在伫列的尾部进行,因此新来的人就只能排在伫列的最后。此外,还有像公共汽车站人们排队等车、医院中病人排队候诊等都是显示生活中伫列的例子。

表示方法

顺序伫列通常採用一维数组进行存储。其中,连续的存储单元依次存放伫列中的元素。同时,使用两个指针分别表示数组中存放的第一个元素和最后一个元素的位置。其中,指向第一个元素的指针被称为队头指针front,指向最后一个元素的位置的指针被称为队尾指针rear。
在实际编程过程中,通常设队头指针指向伫列的第一个元素,队尾指针指向队尾元素的后一个位置。front和rear的初值在伫列初始化时均应置为0;入队时将新元素插入rear所指的位置,然后将rear加1。出队时,删去front所指的元素,然后将front加1并返回被删元素:由此可见,当头尾指针相等时伫列为空。在非空伫列里,头指针始终指向队头元素,而尾指针始终指向队尾元素的下一个位置。

基本操作

入队时:将新元素插入rear所指的位置,然后将rear加1。
出队时:删去front所指的元素,然后将front加1并返回被删元素。
注意:
(1)当头尾指针相等时,伫列为空。
(2)在非空伫列里,队头指针始终指向队头元素,队尾指针始终指向队尾元素的下一位置。

存在问题

在普通顺序伫列中,入队操作就是先将尾指针rear后移一个单元(rear++),然后将元素值赋给rear单元(data[rear]=X)。出队时.则是头指针front后移(front++)。像这样进行了一定数量入队和出队操作后,可能会出现这样的情况:尾指针rear已指到数组的最后一个元素.即rear==MAXLEN-1.此时若再执行入队操作,便会出现队满“溢出”。然而,由于在此之前可能也执行了若干次出队操作.因而数组的前面部分可能还有很多闲置的元素空间,即这种溢出并非是真的没有可用的存储空间,故称这种溢出现象为“假溢出”。显然,必须要解决这一似溢出的问题,否则顺序伫列就没有太多使用价值。

标 签

搜索
随机推荐

Powered By 种豆资源网||