队列
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;
}
入队操作
队列维护两个数据指针,
front和
rear。因此,它的操作比栈的操作更难实现。
应采取以下步骤将数据入队(插入)到队列中-
第 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;
}