logo图片
数据结构与算法

队列

Queue 是一种抽象的数据结构,有点类似于 Stacks。与堆栈不同,队列的两端都是开放的。一端始终用于插入数据(入队),另一端用于移除数据(出队)。队列遵循先进先出的方法,即首先存储的数据项将首先被访问。
队列示例
队列的实际示例可以是单车道单向道路,车辆先进入,然后离开。更真实的例子可以看作是售票窗口和公交车站的队列。

队列表示

我们现在了解到,在队列中,我们出于不同的原因访问两端。下面给出的下图试图将队列表示解释为数据结构-
队列示例
与堆栈一样,队列也可以使用数组、链接列表、指针和结构来实现。为了简单起见,我们将使用一维数组来实现队列。

基本操作

队列操作可能涉及初始化或定义队列,利用它,然后将其从内存中完全擦除。在这里,我们将尝试了解与队列相关的基本操作-
enqueue()-将一个项目添加(存储)到队列中。 dequeue()-从队列中移除(访问)一个项目。
需要更多的函数来使上述队列操作高效。这些是-
peek()-获取队列前面的元素而不移除它。 isfull()-检查队列是否已满。 isempty()-检查队列是否为空。
在队列中,我们总是出队(或访问)数据,由 front 指针指向,而在队列中入队(或存储)数据时,我们借助 rear 指针.
我们先来了解一下队列的支持功能-

Peek()

此功能有助于查看队列 前端的数据。 peek() 函数的算法如下-
算法
begin procedure peek
   return queue[front]
end procedure
C语言中peek()函数的实现-
示例
int peek() {
   return queue[front];
}

isfull()

当我们使用一维数组来实现队列时,我们只需检查后指针到达 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()

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;
}

入队操作

队列维护两个数据指针, frontrear。因此,它的操作比栈的操作更难实现。
应采取以下步骤将数据入队(插入)到队列中-
第 1 步-检查队列是否已满。 第 2 步-如果队列已满,则产生溢出错误并退出。 第 3 步-如果队列未满,则增加 rear 指针以指向下一个空白空间。 第 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

出队操作

从队列中访问数据是两个任务的过程-访问 front 指向的数据并在访问后删除数据。采取以下步骤来执行 dequeue操作-
第 1 步-检查队列是否为空。 第 2 步-如果队列为空,则产生下溢错误并退出。 第 3 步-如果队列不为空,则访问 front 指向的数据。 第 4 步-增加 front 指针以指向下一个可用数据元素。 第 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;
}
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4