队列数据结构
什么是队列？
队列是一种线性数据结构，其元素按先进先出（FIFO）原则存储，即最先插入的元素将最先被访问。队列是一种类似于栈的抽象数据类型 (ADT)，其与栈的不同之处在于队列的两端都是开放的。数据从一端插入队列，从另一端删除。队列在大多数编程语言中都非常常用。
队列在现实世界中的一个例子是单车道单行道，车辆先进入，先离开。更多现实世界的例子可以看作是售票窗口和公交车站的排队。
队列的表示
与堆栈ADT类似，队列ADT也可以使用数组、链表或指针来实现。在本教程中，我们将使用一维数组作为一个小示例来实现队列。
队列的基本操作
队列操作还包括队列的初始化、使用以及从内存中永久删除数据。
队列ADT中最基本的操作包括：enqueue()、dequeue()、peek()、isFull()、isEmpty()。这些都是内置操作，用于执行数据操作和检查队列状态。
队列使用两个指针：front 和 rear。front 指针从前端访问数据（帮助入队），而 rear 指针从后端访问数据（帮助出队）。
队列插入操作：Enqueue()
enqueue() 是一个数据操作操作，用于将元素插入堆栈。以下算法以更简单的方式描述了 enqueue() 操作。
算法
1. 启动 2. 检查队列是否已满。 3. 如果队列已满，则产生溢出错误并退出。 4. 如果队列未满，则增加 rear 指针指向 下一个空位。 5. 将数据元素添加到队列尾部指向的位置。 6. 返回成功。 7. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
bool isEmpty(){
return itemCount == 0;
}
int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int main(){
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
while(!isEmpty()) {
int n = removeData();
printf("%d ",n);
}
}
输出
Queue: 3 5 9 1 12 15
#include <iostream>
#include <string>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
bool isEmpty(){
return itemCount == 0;
}
int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int main(){
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
while(!isEmpty()) {
int n = removeData();
printf("%d ",n);
}
}
输出
Queue: 3 5 9 1 12 15
import java.util.*;
public class Demo{
static final int MAX = 6;
static int intArray[] = new int[MAX];
static int front = 0;
static int rear = -1;
static int itemCount = 0;
public static boolean isFull(){
return itemCount == MAX;
}
public static boolean isEmpty(){
return itemCount == 0;
}
public static int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
public static void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
public static void main(String[] args){
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
System.out.print("Queue: ");
while(!isEmpty()) {
int n = removeData();
System.out.print(n + " ");
}
}
}
输出
Queue: 3 5 9 1 12 15
MAX = 6;
intArray = [0] * MAX
front = 0;
rear = -1;
itemCount = 0;
def isFull():
return itemCount == MAX
def isEmpty():
return itemCount == 0
def removeData():
data = intArray[front+1]
if(front == MAX):
front = 0
itemCount-1
return data
def insert(data):
global rear, itemCount
if(not isFull()):
if(rear == MAX-1):
rear = -1
rear = rear + 1
intArray[rear] = data
itemCount+1
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
print("Queue: ")
for i in range(MAX):
print(intArray[i], end = " ")
while(not isEmpty()):
n = removeData()
print(n, end = " ")
输出
Queue: 3 5 9 1 12 15
队列删除操作：dequeue()
dequeue() 是一个数据操作操作，用于从堆栈中删除元素。以下算法以更简单的方式描述了 dequeue() 操作。
算法
1. 开始 2. 检查队列是否为空。 3. 如果队列为空，则产生下溢错误并退出。 4. 如果队列非空，则访问 front 指向的数据。 5. 增加 front 指针，使其指向下一个可用的 数据元素。 6. 返回成功。 7. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
bool isEmpty(){
return itemCount == 0;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
int main(){
int i;
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
// remove one item
int num = removeData();
printf("
Element removed: %d
",num);
printf("Updated Queue: ");
while(!isEmpty()) {
int n = removeData();
printf("%d ",n);
}
}
输出
Queue: 3 5 9 1 12 15 Element removed: 3 Updated Queue: 5 9 1 12 15
#include <iostream>
#include <string>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
bool isEmpty(){
return itemCount == 0;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
int main(){
int i;
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
// remove one item
int num = removeData();
printf("
Element removed: %d
",num);
printf("Updated Queue: ");
while(!isEmpty()) {
int n = removeData();
printf("%d ",n);
}
}
输出
Queue: 3 5 9 1 12 15 Element removed: 3 Updated Queue: 5 9 1 12 15
public class Demo{
static final int MAX = 6;
static int intArray[] = new int[MAX];
static int front = 0;
static int rear = -1;
static int itemCount = 0;
public static boolean isFull(){
return itemCount == MAX;
}
public static boolean isEmpty(){
return itemCount == 0;
}
public static void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
public static int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
public static void main(String[] args){
int i;
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
System.out.print("Queue: ");
for(i = 0; i < MAX; i++)
System.out.print(intArray[i] + " ");
// remove one item
int num = removeData();
System.out.print("
Element removed: " + num);
System.out.print("
Updated Queue: ");
while(!isEmpty()) {
int n = removeData();
System.out.print(n + " ");
}
}
}
输出
Queue: 3 5 9 1 12 15 Element removed: 3 Updated Queue: 5 9 1 12 15
MAX = 6
intArray = [0] * MAX
front = 0
rear = -1
itemCount = 0
def isFull():
return itemCount == MAX
def isEmpty():
return itemCount == 0
def insert(data):
global rear, itemCount
if not isFull():
if rear == MAX-1:
rear = -1
rear += 1
intArray[rear] = data
itemCount += 1
def removeData():
global front, itemCount
data = intArray[front]
if front == MAX-1:
front = 0
else:
front += 1
itemCount -= 1
return data
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
print("Queue: ")
for i in range(MAX):
print(intArray[i], end = " ")
num = removeData()
print("
Element removed: ", num)
print("Updated Queue: ")
while(not isEmpty()):
n = removeData()
print(n, end = " ")
输出
Queue: 3 5 9 1 12 15 Element removed: 3 Updated Queue: 5 9 1 12 15
队列 - peek() 操作
peek() 操作用于检索队列中最前端的元素，但不删除它。此操作借助指针检查队列的状态。
算法
1. 开始 2. 返回队列前端的元素 3. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isFull(){
return itemCount == MAX;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int main(){
int i;
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("
Element at front: %d
",peek());
}
输出
Queue: 3 5 9 1 12 15 Element at front: 3
#include <iostream>
#include <string>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isFull(){
return itemCount == MAX;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int main(){
int i;
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("
Element at front: %d
",peek());
}
输出
Queue: 3 5 9 1 12 15 Element at front: 3
public class Demo{
final static int MAX = 6;
static int intArray[] = new int[MAX];
static int front = 0;
static int rear = -1;
static int itemCount = 0;
public static int peek(){
return intArray[front];
}
public static boolean isFull(){
return itemCount == MAX;
}
public static void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
public static void main(String[] args){
int i;
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
System.out.print("Queue: ");
for(i = 0; i < MAX; i++)
System.out.print(intArray[i] + " ");
System.out.print("
Element at front: " + peek());
}
}
输出
Queue: 3 5 9 1 12 15 Element at front: 3
MAX = 6
intArray = [0] * MAX
front = 0
rear = -1
itemCount = 0
def peek():
return intArray[front]
def isFull():
return itemCount == MAX
def insert(data):
global rear, itemCount
if(not isFull()):
if(rear == MAX-1):
rear = -1
rear = rear + 1
intArray[rear] = data
itemCount+1
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
print("Queue: ")
for i in range(MAX):
print(intArray[i], end = " ")
print("
Element at front: ", peek())
输出
Queue: 3 5 9 1 12 15 Element at front: 3
队列 - isFull() 操作
isFull() 操作用于验证堆栈是否已满。
算法
1. 开始 2. 如果队列元素数量等于队列大小， 则返回 true 3. 否则，返回 false 4. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int main(){
int i;
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("
");
if(isFull()) {
printf("Queue is full!
");
}
}
输出
Queue: 3 5 9 1 12 15 Queue is full!
#include <iostream>
#include <string>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isFull(){
return itemCount == MAX;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int main(){
int i;
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("
");
if(isFull()) {
printf("Queue is full!
");
}
}
输出
Queue: 3 5 9 1 12 15 Queue is full!
import java.io.*;
public class QueueExample {
static private int intArray[];
private int front;
private int rear;
private int itemCount;
static private int MAX;
QueueExample(int size) {
intArray = new int[size];
front = 0;
rear = -1;
MAX = size;
itemCount = 0;
}
public boolean isFull() {
return itemCount == MAX;
}
public void insert(int key) {
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = key;
itemCount++;
}
}
public static void main (String[] args) {
QueueExample q = new QueueExample(5);
q.insert(1); // inserting 1 in the stack
q.insert(2);
q.insert(3);
q.insert(4);
q.insert(5);
System.out.print("Queue: ");
for(int i = 0; i<MAX; i++){
System.out.print(intArray[i] + " ");
}
if(q.isFull()){
System.out.print("
Queue is full!");
}
}
}
输出
Queue: 1 2 3 4 5 Queue is full!
#队列中 isFull 的 Python 代码
MAX = 6
intArray = [None] * MAX
front = 0
rear = -1
itemCount = 0
def isFull():
return itemCount == MAX
def insert(data):
global rear, itemCount
if not isFull():
if rear == MAX-1:
rear = -1
rear += 1
intArray[rear] = data
itemCount += 1
#将 5 个项目插入队列
insert(3)
insert(5)
insert(9)
insert(1)
insert(12)
insert(15)
print("Queue: ", end="")
for i in range(MAX):
print(intArray[i], end=" ")
print()
if isFull():
print("Queue is full!")
输出
Queue: 3 5 9 1 12 15 Queue is full!
队列 - isEmpty() 操作
isEmpty() 操作用于验证堆栈是否为空。此操作借助栈顶指针来检查堆栈的状态。
算法
1. 开始 2. 如果队列元素数量为零，则返回 true 3. 否则，返回 false 4. 结束
示例
以下是此操作在各种编程语言中的实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isEmpty(){
return itemCount == 0;
}
int main(){
int i;
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("
");
if(isEmpty()) {
printf("Queue is Empty!
");
}
}
输出
Queue: 0 0 0 0 0 0 Queue is Empty!
#include <iostream>
#include <string>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
bool isEmpty(){
return itemCount == 0;
}
int main(){
int i;
printf("Queue: ");
for(i = 0; i < MAX; i++)
printf("%d ", intArray[i]);
printf("
");
if(isEmpty()) {
printf("Queue is Empty!
");
}
}
输出
Queue: 0 0 0 0 0 0 Queue is Empty!
public class Demo{
final static int MAX = 6;
static int intArray[] = new int[MAX];
static int front = 0;
static int rear = -1;
static int itemCount = 0;
public static boolean isEmpty(){
return itemCount == 0;
}
public static void main(String[] args){
int i;
System.out.print("Queue: ");
for(i = 0; i < MAX; i++)
System.out.print(intArray[i] + " ");
if(isEmpty()) {
System.out.print("
Queue is Empty!");
}
}
}
输出
Queue: 0 0 0 0 0 0 Queue is Empty!
#python code for isFull in Queue
MAX = 6
intArray = [None] * MAX
front = 0
rear = -1
itemCount = 0
def isEmpty():
return itemCount == 0
print("Queue: ", end="")
for i in range(MAX):
print(intArray[i], end=" ")
print()
if isEmpty():
print("Queue is empty!")
输出
Queue: None None None None None None Queue is empty!
队列完整实现
以下是各种编程语言中队列的完整实现 −
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isEmpty(){
return itemCount == 0;
}
bool isFull(){
return itemCount == MAX;
}
int size(){
return itemCount;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
int main(){
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
printf("Queue size: %d", size());
printf("
Queue: ");
for(int i = 0; i < MAX; i++){
printf("%d ", intArray[i]);
}
if(isFull()) {
printf("
Queue is full!");
}
// remove one item
int num = removeData();
printf("
Element removed: %d", num);
printf("
Size of Queue after deletion: %d", size());
printf("
Element at front: %d", peek());
}
输出
Queue size: 6 Queue: 3 5 9 1 12 15 Queue is full! Element removed: 3 Size of Queue after deletion: 5 Element at front: 5
#include <iostream>
using namespace std;
#include <string>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isEmpty(){
return itemCount == 0;
}
bool isFull(){
return itemCount == MAX;
}
int size(){
return itemCount;
}
void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
int main(){
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
cout<<"Queue size: "<<size();
cout<<"
Queue: ";
for(int i = 0; i < MAX; i++){
cout<<intArray[i]<<" ";
}
if(isFull()) {
cout<<"
Queue is full!";
}
// remove one item
int num = removeData();
cout<<"
Element removed: "<<num;
cout<<"
Queue size after deletion: "<<size();
cout<<"
Element at front: " <<peek();
}
输出
Queue size: 6 Queue: 3 5 9 1 12 15 Queue is full! Element removed: 3 Queue size after deletion: 5 Element at front: 5
public class Demo{
final static int MAX = 6;
static int intArray[] = new int[MAX];
static int front = 0;
static int rear = -1;
static int itemCount = 0;
public static int peek(){
return intArray[front];
}
public static boolean isEmpty(){
return itemCount == 0;
}
public static boolean isFull(){
return itemCount == MAX;
}
public static int size(){
return itemCount;
}
public static void insert(int data){
if(!isFull()) {
if(rear == MAX-1) {
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
public static int removeData(){
int data = intArray[front++];
if(front == MAX) {
front = 0;
}
itemCount--;
return data;
}
public static void main(String[] args){
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
insert(15);
System.out.print("Queue size: " + size());
System.out.print("
Queue: ");
for(int i = 0; i < MAX; i++){
System.out.print(intArray[i] + " ");
}
if(isFull()) {
System.out.print("
Queue is full!");
}
// remove one item
int num = removeData();
System.out.print("
Element removed: " + num);
System.out.print("
Queue size after deletion: " + size());
System.out.print("
Element at front: " + peek());
}
}
输出
Queue size: 6 Queue: 3 5 9 1 12 15 Queue is full! Element removed: 3 Queue size after deletion: 5 Element at front: 5
MAX = 6
intArray = [0] * MAX
front = 0
rear = -1
itemCount = 0
def peek():
return intArray[front]
def isEmpty():
return itemCount == 0
def isFull():
return itemCount == MAX
def size():
return itemCount
def insert(data):
global rear, itemCount
if not isFull():
if rear == MAX-1:
rear = -1
rear += 1
intArray[rear] = data
itemCount += 1
def removeData():
global front, itemCount
data = intArray[front]
if front == MAX-1:
front = 0
else:
front += 1
itemCount -= 1
return data
def main():
insert(3)
insert(5)
insert(9)
insert(1)
insert(12)
insert(15)
print("Queue size: ", size())
print("Queue: ")
for i in range(MAX):
print(intArray[i], end = " ")
if isFull():
print("
Queue is full!")
num = removeData()
print("Element removed: ", num)
print("Queue size after deletion: ", size())
print("Element at front: ", peek())
main()
输出
Queue size: 6 Queue: 3 5 9 1 12 15 Queue is full! Element removed: 3 Queue size after deletion: 5 Element at front: 5
C 语言队列实现
点击查看C 语言队列程序的实现
