算法:队列算法
队列是一种抽象的数据结构,有点类似于Stacks。与堆栈不同,队列的两端都是开放的。一端始终用于插入数据(入队),另一端用于删除数据(出队)。队列遵循先进先出方法,即首先访问先存储的数据项。
一个真实的队列示例可以是单车道单向道路,车辆首先进入,首先退出。更多真实世界的例子可以看作是售票窗口和公共汽车站的队列。
队列表示
我们现在明白,在队列中,我们出于不同的原因访问两端。下面给出的下图试图将队列表示解释为数据结构
与堆栈一样,也可以使用数组,链接列表,指针和结构来实现队列。为简单起见,我们将使用一维数组实现队列。
基本操作
队列操作可能涉及初始化或定义队列,利用它,然后从存储器中完全擦除它。在这里,我们将尝试理解与队列相关的基本操作
- enqueue() - 将项添加(存储)到队列中。
- dequeue() - 从队列中删除(访问)一个项目。
为了使上述队列操作有效,需要更多的功能。这些是 -
- peek() - 获取队列前面的元素而不删除它。
- isfull() - 检查队列是否已满。
- isempty() - 检查队列是否为空。
在队列中,我们总是将 前端 指针指向的数据出列(或访问),并在队列中排队(或存储)数据时我们采用 后 指针的帮助。
让我们首先了解一下队列的支持功能
窥视()
此功能有助于查看队列 前面 的数据。peek()函数的算法如下
算法
begin procedure peek return queue[front] end procedure
用C编程语言实现peek()函数
例
int peek() { return queue[front]; }
已满()
由于我们使用单维数组来实现队列,我们只需检查后指针是否达到MAXSIZE以确定队列已满。如果我们将队列保存在循环链表中,算法将有所不同。isfull()函数的算法
算法
begin procedure isfull if rear equals to MAXSIZE return true else return false endif end procedure
在C编程语言中实现isfull()函数
例
bool isfull() { if(rear == MAXSIZE - 1) return true; else return false; }
是空的()
isempty()函数的算法
算法
begin procedure isempty if front is less than MIN OR front is greater than rear return true else return false endif end procedure
如果 front 的值小于MIN或0,则表示队列尚未初始化,因此为空。
这是C编程代码
例
bool isempty() { if(front < 0 || front > rear) return true; else return false; }
入队行动
队列维护两个数据指针, 前端 和 后端 。因此,其操作比堆栈的操作相对难以实现。
应采取以下步骤将数据排入(插入)到队列中
- 第1步 - 检查队列是否已满。
- 步骤2 - 如果队列已满,则产生溢出错误并退出。
- 步骤3 - 如果队列未满,则增加 后 指针以指向下一个空白区域。
- 步骤4 - 将数据元素添加到后方指向的队列位置。
- 第5步 - 返回成功。
有时,我们还会检查队列是否已初始化,以处理任何无法预料的情况。
入队操作算法
procedure enqueue(data) if queue is full return overflow endif rear ← rear + 1 queue[rear] ← data return true end procedure
在C编程语言中实现enqueue()
例
int enqueue(int data) if(isfull()) return 0; rear = rear + 1; queue[rear] = data; return 1; end procedure
出列操作
从队列中访问数据是两个任务的过程 - 访问 前端 指向的数据并在访问后删除数据。采取以下步骤来执行 出列 操作
- 第1步 - 检查队列是否为空。
- 步骤2 - 如果队列为空,则产生下溢错误并退出。
- 步骤3 - 如果队列不为空,请访问 前端 指向的数据。
- 步骤4 - 增加 前 指针以指向下一个可用数据元素。
- 第5步 - 返回成功。
出列操作的算法
procedure dequeue if queue is empty return underflow end if data = queue[front] front ← front + 1 return true end procedure
在C编程语言中实现dequeue()
例
int dequeue() { if(isempty()) return 0; int data = queue[front]; front = front + 1; return data; } front ← front + 1 return true end procedure
在C编程语言中实现dequeue()
例
int dequeue() { if(isempty()) return 0; int data = queue[front]; front = front + 1; return data; }