app下载平台哪个好_网站建设说明_德州seo优化_宁波网络建站模板

逻辑结构：队列是一种操作受限的线性表，只允许从队尾入队，从队首出队。这个情形类型与排队

物理结构：分为顺序存储结构（一般通过循环队列实现），链式存储结构

1.队列的顺序存储

接下来主要介绍的是循环队列

1.1循环队列的初始化

typedef struct Queue
{int data[MaxSize];int front;//队首指针int rear;//队尾指针
}SqQueue;//初始化队列
void InitQueue(SqQueue* Q)
{Q->front = Q->rear = 0;
}

1.2判断队空

//队列的判空
bool Empty(SqQueue* Q)
{if (Q->front == Q->rear){return true;}else{return false;}
}

1.3入队

//入队
bool EnQueue(SqQueue* Q)
{//判断队列是否满了if ((Q->rear + 1) % MaxSize == Q->front){printf("队列已经满了\n");return false;}int x = 0;printf("请输入要插入的值:");scanf("%d", &x);Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize;return true;
}

1.4出队

//出队
bool DeQueue(SqQueue* Q,int* x)
{//判断队列是否为空if (Q->front == Q->rear){return false;}(*x) = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;return true;
}

1.5读出队首元素

//获取队首元素
bool GetQueue(SqQueue* Q,int* x)
{//判断队列是否为空if (Q->front == Q->rear){return false;}(*x) = Q->data[Q->front];return true;
}

1.6求队列元素个数

//求队列元素个数
int Length(SqQueue* Q)
{int len = ((Q->rear + MaxSize) - Q->front) % MaxSize;return len;
}

1.7循环队列整体代码

//顺序队列(也可以看做是循环队列）
typedef struct Queue
{int data[MaxSize];int front;//队首指针int rear;//队尾指针
}SqQueue;//初始化队列
void InitQueue(SqQueue* Q)
{Q->front = Q->rear = 0;
}//队列的判空
bool Empty(SqQueue* Q)
{if (Q->front == Q->rear){return true;}else{return false;}
}//入队
bool EnQueue(SqQueue* Q)
{//判断队列是否满了if ((Q->rear + 1) % MaxSize == Q->front){printf("队列已经满了\n");return false;}int x = 0;printf("请输入要插入的值:");scanf("%d", &x);Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize;return true;
}//出队
bool DeQueue(SqQueue* Q,int* x)
{//判断队列是否为空if (Q->front == Q->rear){return false;}(*x) = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;return true;
}//获取队首元素
bool GetQueue(SqQueue* Q,int* x)
{//判断队列是否为空if (Q->front == Q->rear){return false;}(*x) = Q->data[Q->front];return true;
}//求队列元素个数
int Length(SqQueue* Q)
{int len = ((Q->rear + MaxSize) - Q->front) % MaxSize;return len;
}int main()
{SqQueue Q;int x = 0;//初始化顺序队列InitQueue(&Q);//入队，入队5个元素int i = 0;for (i = 0; i < 5; i++){EnQueue(&Q);}//出队一个元素DeQueue(&Q,&x);printf("出队元素大小为%d\n", x);//获取当前队头元素GetQueue(&Q,&x);printf("当前队头元素大小为%d\n", x);return 0;
}

2.队列的链式存储

2.1队列的初始化

//队列节点
typedef struct LinkNode
{int data;struct LinkNode* next;
}LinkNode;typedef struct
{LinkNode* front;//队首指针LinkNode* rear;//队尾指针,这两个都是指向节点的指针
}LinkQueue;//LinkQueue是包含两个节点指针的结构体的结构体类型//队列的初始化，带头结点
void InitQueue(LinkQueue** Q)//传递的是队首指针和队尾指针
{(*Q)->front = (*Q)->rear = (LinkNode*)calloc(1, sizeof(LinkNode));(*Q)->front->next = NULL;
}int main()
{LinkQueue* Q=(LinkQueue*)malloc(sizeof(LinkQueue));int x = 0;InitQueue(&Q);return 0;
}

2.2队列的判空

//队列的判空操作bool Empty(LinkQueue** Q)
{if ((*Q)->front == (*Q)->rear)//还可以是Q->front->next==NULL;{return true;}else{return false;}
}

2.3入队操作

//入队
void EnQueue(LinkQueue** Q)
{//链表不存在队列已经满了，不需要判断// 创建新节点LinkNode* s = (LinkNode*)calloc(1, sizeof(LinkNode));if (s == NULL){return;}int x = 0;printf("请输入要插入的节点的数据：");scanf("%d", &x);s->data = x;s->next = NULL;(*Q)->rear->next = s;(*Q)->rear = s;}

2.4出队操作

// 出队bool DeQueue(LinkQueue** Q,int* x)
{//先判断队列是否为空if ((*Q)->front == (*Q)->rear){return false;}//出队从队首开始，也就是头结点LinkNode* p = (*Q)->front->next;//这个就是除头指针外队首的第一个节点地址(*x) = p->data;(*Q)->front->next = p->next;if ((*Q)->rear==p)//出队的是最后一个节点,修改队尾指针到头结点{(*Q)->rear = (*Q)->front;}free(p);//释放掉这一块空间return true;
}

2.5整体代码

//队列节点
typedef struct LinkNode
{int data;struct LinkNode* next;
}LinkNode;typedef struct
{LinkNode* front;//队首指针LinkNode* rear;//队尾指针,这两个都是指向节点的指针
}LinkQueue;//LinkQueue是包含两个节点指针的结构体的结构体类型//队列的初始化，带头结点
void InitQueue(LinkQueue** Q)//传递的是队首指针和队尾指针
{(*Q)->front = (*Q)->rear = (LinkNode*)calloc(1, sizeof(LinkNode));(*Q)->front->next = NULL;
}//队列的判空操作bool Empty(LinkQueue** Q)
{if ((*Q)->front == (*Q)->rear)//还可以是Q->front->next==NULL;{return true;}else{return false;}
}//入队
void EnQueue(LinkQueue** Q)
{//链表不存在队列已经满了，不需要判断// 创建新节点LinkNode* s = (LinkNode*)calloc(1, sizeof(LinkNode));if (s == NULL){return;}int x = 0;printf("请输入要插入的节点的数据：");scanf("%d", &x);s->data = x;s->next = NULL;(*Q)->rear->next = s;(*Q)->rear = s;}// 出队bool DeQueue(LinkQueue** Q,int* x)
{//先判断队列是否为空if ((*Q)->front == (*Q)->rear){return false;}//出队从队首开始，也就是头结点LinkNode* p = (*Q)->front->next;//这个就是除头指针外队首的第一个节点地址(*x) = p->data;(*Q)->front->next = p->next;if ((*Q)->rear==p)//出队的是最后一个节点,修改队尾指针到头结点{(*Q)->rear = (*Q)->front;}free(p);//释放掉这一块空间return true;
}int main()
{LinkQueue* Q=(LinkQueue*)malloc(sizeof(LinkQueue));int x = 0;InitQueue(&Q);//入队 入队5个元素int i = 0;for (i = 0; i < 5; i++){EnQueue(&Q);}//出队一个元素DeQueue(&Q,&x);printf("出队的元素是%d\n", x);return 0;
}