文章目录

• 队列
• • • 队列存储结构特点
    • 队列的相关概念：
    • 队列的操作：
    • 队列的分类：
    • 数组实现
    • 链表实现

队列

队列存储结构特点

（1）队列中的数据元素遵循“先进先出”的原则
（2）在队尾添加元素，在队头删除元素。

队列的相关概念：

（1）队头与队尾： 允许元素插入的一端称为队尾，允许元素删除的一端称为队头；
（2）入队：队列的插入操作；
（3）出队：队列的删除操作。

队列的操作：

（1）入队： 通常命名为push()
（2）出队： 通常命名为pop()
（3）求队列中元素个数
（4）判断队列是否为空
（5）获取队首元素

队列的分类：

（1）基于数组的循环队列（循环队列）
（2）基于链表的队列（链队列）

数组实现

#include <stdio.h>
#include <string.h>

#define QUE_SIZE 10  //最大队列长度+1 ,实际长度为9

typedef struct QueueInfo
{
	int front; //队头
	int tail;//队尾
	int queueArr[QUE_SIZE];

}QUEUE;

//判断队列是否为满

int QueueIsFull(QUEUE *queue)
{
	if ((queue->tail+2)% QUE_SIZE == queue->front) //队列满的条件
	{
		printf("queue is full\n");
		return -1;
	}

	else //队列不为满
		return 0;

}

//判断队列是否为空

int QueueIsEmpty(QUEUE *queue)
{
	if ((queue->tail + 1) % QUE_SIZE == queue->front) //为空的条件
	{
		printf("queue is empty\n");
		return -1;
	}

	else
		return 0;
}

//入队

int QueueInsert(QUEUE *queue, int value)
{
	if (QueueIsFull(queue)) //如果尾部入队失败，即队列已满
		return -1;

	queue->tail = (queue->tail+1)%QUE_SIZE;//更新队尾元素
	queue->queueArr[queue->tail] = value; //插入新的队尾元素

	printf("insert %d  to %d\n",value,queue->tail);	

	return 0;
}

//出队

int QueueDelete(QUEUE * queue, int *value)
{
	if (QueueIsEmpty(queue))
		return -1;

		*value = queue->queueArr[queue->front];//删除头存放在value中
		 printf("delete value from front %d  is %d\n",queue->front,*value);
		queue->front = (queue->front + 1)%QUE_SIZE;//更新头指针		

		return 0;
}


int main(int argc, char const *argv[])
{
	
	int value = 0;
	int i = 0;
	int j = 0;
	QUEUE queue;

    memset(&queue,0,sizeof(queue));
    queue.front = 1;
    queue.tail = 0;

    //假设入队位12个数据，则只有前10个在队内，剩下3个入队失败
    for (i = 0; i < 12; i ++)
    	QueueInsert(&queue,i);

    for (i = 0; i < 12; i++) //出队数据，最后3个出队失败
    	QueueDelete(&queue,&i);

	return 0;
}

链表实现

#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node *next;
}Qnode;
typedef struct 
{
    Qnode *front;//指向链表头结点 
    Qnode *rear;//指向链表尾结点 
}Q;

int deleteQ(Q *q)//删除结点并返回删除结点的值 
{
    Qnode *temp;
    int term;
    if(q->front == NULL)
    {
        printf("队列空！\n");
        return 0;
    }

    temp = q->front;//保留头结点 
    if(q->front == q->rear)//若队列只有一个元素 
    q->front = q->rear = NULL;//将头结点尾结点都设为空 
    else
    q->front = q->front->next;//否则改变头结点
    term = temp->data; 
    free(temp);//释放头结点 
    return term;//返回头结点的值 
}

void AddQ(Q *q,int num)//增添结点 
{
    Qnode *p = (Qnode *)malloc(sizeof(Qnode));
    p->data = num;
    Qnode *temp = q->rear;
    if(temp != NULL)//判断队列是否为空 
    {
        temp->next = p;
        q->rear = p;
        p->next = NULL;
    }
    else
    {
        q->front =  p;//若队列为空，将首尾均指向新增结点 
        q->rear = p;
        p->next = NULL;
    }
} 
int main()
{
    Q *q =(Q *) malloc(sizeof(Q));
    q->front = q->rear = NULL; 
    for(int i = 0;i < 2;i++)
    {
        AddQ(q,i);
    }
    for(int i = 0;i<2;i++)
    {
        int n = deleteQ(q);
        printf("%d\t",n);
    }
    free(q);
    return 0;
}