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