数据结构-队列（数组实现）

我们使用数组来实现:定义了四个函数

EnQueue(x)、DeQueue(x)、front()、IsEmpty()

这四个函数时间复杂度是O(1)orConstant time，我们是用循环数组来实现的

循环数组的概念

我们原来的数组是这样子的：

 我们使用循环数组以后变成如下这样：

 

循环数组的原理

编程实战

四个函数与队列相关的函数

我们将数组、队头和队尾还有数组长度定义为全局变量

队列的定义是：先进先出，插入必须是在队尾进行的，删除必须是在队头进行的，队列被用来模拟一系列需要等待的场景

 

EnQueue(x)入队、DeQueue(x)出队、front()返回对首的值、IsEmpty()看队列是否为空

int front = -1;//队尾
int rear = -1;//对头
int A[10];//我们定义一个数组来实现队列
int N=10;//数组的长度为N，N=10
int Front(void) {
    //检查队列是否为空，只有front不为-1的时候才返回A[front]
    return A[front];
}
bool IsEmpty(void) {
    if ((front == -1) && (rear == -1))//表示队列为空，front==rear 要么为空，要么为一个元素；
        return 1;
    else
        return 0;
}
void  EnQueue(int x) {//调用完EnQueue之后的队列，front和rear是一样的
    if ((rear+1)%N==front)//如果rear已经等于数组A的最大索引值，我们就不能插入元素了//rear == sizeof(A) - 1
    {
        printf("front=%d，rear=%d\n",front, rear);
        printf("队列已满，入队失败\n");
        return;
    }
    else if (IsEmpty() == 1)//如果队列是空的
    {
        //我们可以把索引值0的位置加入队列，现在我们把x写入索引值是rear的位置,因为我们要插入一个元素，所以rear\front要加1变为0
        front = 0;
        rear = 0;
        A[rear] = x;
        printf("入队成功：队首值Front=%d\n", Front());
        printf("front=%d，rear=%d\n", front, rear);
    }
    else
    {
        rear =(rear +1 )%N;//原来这里不是循环的时候是rear=rear+1
        A[rear] = x;
        printf("front=%d，rear=%d\n", front, rear);
    }
    
    printf("入队成功：队首值A[%d]=%d，队尾值是：A[%d]=%d\n", front, Front(), rear,A[rear]);
}
void DeQueue() {
    if (IsEmpty() == 1)//如果队列为空，我们无法从中移出一个元素
    {
        printf("无法移出:");
        printf("front=%d，rear=%d\n", front, rear);
        return;
    }
    else if (front == rear)//队列中只有一个元素
    {
        //这时front和rear不是-1而是相等，把最后一个元素删除的同时，把front和rear同时设置为-1，DeQueue函数会让队列变空，为了把队列变空，front = rear=-1
        printf("队列只有一个元素,删除的元素为：%d\n", Front());
        A[front] = 0;
        front =-1;
        rear = -1;
        printf("front=%d，rear=%d\n", front, rear);
    }
    else
    {
        //使用循环数组
        A[front] = 0;//这段代码的意思是我们每次删除队头就将它的值置为0
        printf("出队成功：队首值A[%d]=%d，队尾值是：A[%d]=%d\n", front, Front(), rear, A[rear]);
        front =(front + 1)%N;//因为我们之前约定的是从对头删除，从队尾插入 front = front + 1
    
       
        printf("front=%d，rear=%d\n", front, rear);
    }
 
}

查询队列信息的函数

void show(void) {
    if((front == 1)&&(rear==1))
    {
        printf("该队列长度为1,剩余长度为9\n");
    }
    else if ((front == -1 )&&( rear == -1))
    {
        printf("该队列长度为%d\n", N);
        printf("剩余长度为%d\n", N );
    }
    else if(rear>front)//这里保证是入队
    {
        printf("该队列长度为%d\n", abs(front - rear)+1);
        printf("剩余长度为%d\n", N - abs(front - rear)-1);
    }
    else //这里保证是出队
    {
        printf("该队列长度为%d\n", abs(front - rear) );
        printf("剩余长度为%d\n", N - abs(front - rear) );
    }
 
}

全部代码

#include
#include
#include//为bool类型增加的头文件
/*
EnQueue(x)
DeQueue(x)
front()
IsEmpty()
//这四个函数时间复杂度是O(1)orConstant time
我们是用循环数组来实现的
*/
int front = -1;//队尾
int rear = -1;//对头
int A[10];//我们定义一个数组来实现队列
//数组的长度为N，N=10
int N=10;
int Front(void) {
    //检查队列是否为空，只有front不为-1的时候才返回A[front]
    return A[front];
}
bool IsEmpty(void) {
    if ((front == -1) && (rear == -1))//表示队列为空，front==rear 要么为空，要么为一个元素；
        return 1;
    else
        return 0;
}
void  EnQueue(int x) {//调用完EnQueue之后的队列，front和rear是一样的
    if ((rear+1)%N==front)//如果rear已经等于数组A的最大索引值，我们就不能插入元素了//rear == sizeof(A) - 1
    {
        printf("front=%d，rear=%d\n",front, rear);
        printf("队列已满，入队失败\n");
        return;
    }
    else if (IsEmpty() == 1)//如果队列是空的
    {
        //我们可以把索引值0的位置加入队列，现在我们把x写入索引值是rear的位置,因为我们要插入一个元素，所以rear\front要加1变为0
        front = 0;
        rear = 0;
        A[rear] = x;
        printf("入队成功：队首值Front=%d\n", Front());
        printf("front=%d，rear=%d\n", front, rear);
    }
    else
    {
        rear =(rear +1 )%N;//原来这里不是循环的时候是rear=rear+1
        A[rear] = x;
        printf("front=%d，rear=%d\n", front, rear);
    }
    
    printf("入队成功：队首值A[%d]=%d，队尾值是：A[%d]=%d\n", front, Front(), rear,A[rear]);
}
void DeQueue() {
    if (IsEmpty() == 1)//如果队列为空，我们无法从中移出一个元素
    {
        printf("无法移出:");
        printf("front=%d，rear=%d\n", front, rear);
        return;
    }
    else if (front == rear)//队列中只有一个元素
    {
        //这时front和rear不是-1而是相等，把最后一个元素删除的同时，把front和rear同时设置为-1，DeQueue函数会让队列变空，为了把队列变空，front = rear=-1
        printf("队列只有一个元素,删除的元素为：%d\n", Front());
        A[front] = 0;
        front =-1;
        rear = -1;
        printf("front=%d，rear=%d\n", front, rear);
    }
    else
    {
        //使用循环数组
        A[front] = 0;
        printf("出队成功：队首值A[%d]=%d，队尾值是：A[%d]=%d\n", front, Front(), rear, A[rear]);
        front =(front + 1)%N;//因为我们之前约定的是从对头删除，从队尾插入 front = front + 1
    
       
        printf("front=%d，rear=%d\n", front, rear);
    }
 
}
/*
循环数组，当我们遍历一个数组时，我们可以把它想象成是没有结尾的，
最后到达最大索引位置
对于一个循环数组来说，当前位置为i,下一个索引的不是简单的i+1，而是（i+1）%N;N为数组元素的个数
i不等于N-1，取模操作并不会有什么影响；但是i=N-1下一个位置将会是0，取余等于0；循环数组的前一个位置
将是（i+N-1）%N；我们可以直接是（i-1）%N，但是为了确保括号表达式是一个正数，我们加上了N
*/
void show(void) {
    if((front == 1)&&(rear==1))
    {
        printf("该队列长度为1,剩余长度为9\n");
    }
    else if ((front == -1 )&&( rear == -1))
    {
        printf("该队列长度为%d\n", N);
        printf("剩余长度为%d\n", N );
    }
    else if(rear>front)//这里保证是入队
    {
        printf("该队列长度为%d\n", abs(front - rear)+1);
        printf("剩余长度为%d\n", N - abs(front - rear)-1);
    }
    else //这里保证是出队
    {
        printf("该队列长度为%d\n", abs(front - rear) );
        printf("剩余长度为%d\n", N - abs(front - rear) );
    }
 
}
int main()
{
 
 
    /*
    队列的出队和入队就是通过这两个变量来实现的
    增加rear，相当于插入数字
    增加front，相当于删除数字
    对于一个空队列来说，front和rear都是-1，可以通过检查这两个的值来判断是不是空队列
    */
    EnQueue(2);
    EnQueue(5);
    EnQueue(4);
    EnQueue(8);
    EnQueue(0);
    EnQueue(1);
    EnQueue(3);
    EnQueue(1);
    EnQueue(3);
    EnQueue(1);
    show();
    for (int i = 0; i < 10; i++)
    {
        printf("A[%d]=%d\n", i, A[i]);
    }
    EnQueue(12);
 
    DeQueue();
    DeQueue();
    DeQueue();
    DeQueue();
    DeQueue();
    DeQueue();
    DeQueue();
    DeQueue();
    DeQueue();
    DeQueue();
    DeQueue();
    show();
    for (int i = 0; i < 10; i++)
    {
        printf("A[%d]=%d\n", i, A[i]);
    }
    return 0;
}

代码验证

 可能大家会觉得上面的代码太过于冗长，我们给出下面的简洁版代码

 

#include
#include
#include//为bool类型增加的头文件
int A[5];
int N = 5;
int rear = -1;
int front = -1;
int Front_value() {
 
	return A[front];
}
bool IsEmpty(void) {
	if ((rear == -1) && (front == -1))
		return 1;
	else
		return 0;
 
}
void Enqueue(int x) {
	if ((rear + 1) % N == front) {
		printf("队列已满，无法入队\n");
		return;
	
	}
	else if (IsEmpty()==1) {
		//这种情况是队列是空
		rear = 0;
		front = 0;
		A[rear] = x;
 
		printf("入队成功：队首值A[%d]=%d\n", front, Front_value());
		printf("front=%d，rear=%d\n", front, rear);
 
	}
	else {
		//这个就是不断移动队尾的值，因为是从队尾移动
		rear = (rear + 1) % N;
		A[rear] = x;
		printf("front=%d，rear=%d\n", front, rear);
 
	}
	printf("对首值A[%d] =%d,队尾值：A[%d] =%d,front=%d\n", front, Front_value(),rear, A[rear], front);
}
void Dequeue(void) {
	if (IsEmpty() == 1) {
		printf("队列为空，无法出队\n");
		return;
	}
	else if (rear ==front) {
		//这里必须要要rear ==front这样子写，如果是写成rear==0&&front==0,当对为空时，任然会执行rear==0这一个操作，就会出现问题
	//队列只有一个元素，从队头开始删除
		A[front] = 0;//把唯一的元素置为0
		rear = -1;
		front = -1;
		printf("front=%d，rear=%d\n", front, rear);
	}
	else {
	
		
		A[front] = 0;
		
		printf("对首值A[%d] =%d,队尾值：A[%d] =%d,front=%d\n", front, Front_value(), rear, A[rear], front);
		printf("front=%d，rear=%d\n", front, rear);
		front = (front + 1) % N;
		
	}
}
int main(void) {
	Enqueue(5);
	Enqueue(4);
	Enqueue(3);
	Enqueue(2);
	Enqueue(1);
	Enqueue(7);
	for (int i = 0; i < 5; i++)
	{
		printf("A[%d] =%d ",i, A[i]);
	}
	printf("\n");
	Dequeue();
	Dequeue();
	Dequeue();
	Dequeue();
	Dequeue();
	Dequeue();
	Dequeue();
	for (int i = 0; i < 5; i++)
	{
		printf("A[%d] =%d ", i, A[i]);
	}
	printf("\n");
	return 0;
}