7.队列算法

简介: 7.队列算法

算法:队列算法

队列是一种抽象的数据结构,有点类似于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;
}
相关文章
|
9天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
29天前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
20 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
5月前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
2月前
|
存储 算法 前端开发
深入理解操作系统:进程调度与优先级队列算法
【9月更文挑战第25天】在操作系统的复杂世界中,进程调度是维持系统稳定运行的核心机制之一。本文将深入探讨进程调度的基本概念,分析不同的进程调度算法,并着重介绍优先级队列算法的原理和实现。通过简洁明了的语言,我们将一起探索如何优化进程调度,提高操作系统的效率和响应速度。无论你是计算机科学的初学者还是希望深化理解的专业人士,这篇文章都将为你提供有价值的见解。
|
3月前
|
缓存 算法 Java
刷算法,你应该知道的队列经典应用
文章介绍了队列的基本特性和经典应用,包括如何用队列实现栈、使用优先级队列解决Top K问题,并通过LeetCode题目示例展示了队列在算法实现中的应用。
刷算法,你应该知道的队列经典应用
|
3月前
|
算法
【数据结构与算法】优先级队列
【数据结构与算法】优先级队列
15 0
|
3月前
|
存储 算法
【数据结构与算法】队列(顺序存储)
【数据结构与算法】队列(顺序存储)
29 0
|
5月前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
|
4月前
|
算法
数据结构与算法:栈与队列
数据结构与算法:栈与队列
|
5月前
|
算法 程序员 数据处理
【数据结构与算法】使用单链表实现队列:原理、步骤与应用
【数据结构与算法】使用单链表实现队列:原理、步骤与应用