数据结构和算法队列


队列是一种抽象的数据结构,有点类似于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;
}