簡(jiǎn)介
- 隊(duì)列也是一種數(shù)據(jù)結(jié)構(gòu)，隊(duì)列也可以用來(lái)存放數(shù)字
- 每次只能向隊(duì)列里將入一個(gè)數(shù)字，每次只能從隊(duì)列里獲得一個(gè)數(shù)字
- 在隊(duì)列中，允許插入的一段稱為入隊(duì)口，允許刪除的一段稱為出隊(duì)口
- 它的原則是先進(jìn)先出(FIFO: first in first out)，先進(jìn)入隊(duì)列的數(shù)據(jù)先出去，后進(jìn)入的后出去。
- 隊(duì)列的插入操作稱為入隊(duì)
- 隊(duì)列的刪除操作稱為出隊(duì)
以下是隊(duì)列中進(jìn)行入隊(duì)和出隊(duì)的演示操作，數(shù)據(jù)1先進(jìn)，也是數(shù)據(jù)1先出
代碼實(shí)現(xiàn)
- 初始化隊(duì)列
typedef struct queue{
int* elements; // 存儲(chǔ)區(qū)
int cap; // 隊(duì)列的容量
int rear; // 入隊(duì)口
int front; // 出隊(duì)口
int size; // 隊(duì)列當(dāng)前大小
}queue_t;
- 初始化隊(duì)列
void queue_init(queue_t* pqueue, int cap){
// 分配存儲(chǔ)區(qū)空間
pqueue->elements = malloc(sizeof(int) * cap);
if(pqueue->elements == NULL){
printf("內(nèi)存分配失敗\n");
return;
}
// 賦值容量
pqueue->cap = cap;
// 此時(shí)因?yàn)闆](méi)有收數(shù)據(jù)，出隊(duì)口和入隊(duì)口都是0，隊(duì)列當(dāng)前大小也是0
pqueue->rear = 0;
pqueue->front = 0;
pqueue->size = 0;
}
- 銷毀隊(duì)列
void queue_deinit(queue_t* pqueue){
free(pqueue->elements);
pqueue->elements = NULL;
pqueue->cap = 0;
pqueue->rear = 0;
pqueue->front = 0;
pqueue->size = 0;
}
- 判斷隊(duì)列是否已滿
int queue_full(queue_t* pqueue){
// 當(dāng)size==cap的時(shí)候，說(shuō)明已滿，反之則沒(méi)滿
return pqueue->size == pqueue->cap;
}
- 判斷隊(duì)列是否為空
int queue_empty(queue_t* pqueue){
// 當(dāng)size==0的時(shí)候，說(shuō)明為空，反之則不為空
return pqueue->size == 0;
}
以下是一組入隊(duì)出隊(duì)的操作
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-637490.html
- 入隊(duì)
void queue_push(queue_t* pqueue, int data){
// 參考上面的視頻，當(dāng)此時(shí)還存在入隊(duì)操作時(shí)，說(shuō)明隊(duì)列還沒(méi)滿，
// 但是此時(shí)rear已經(jīng)超過(guò)索引值了(也就是與cap值相等)，需要將rear重置為0;
if(pqueue->rear == pqueue=>cap)
pqueue->rear = 0;
pqueue->elements[pqueue->rear++] = data;
pqueue->size++;
}
- 出隊(duì)
int queue_pop(queue_t* pqueue){
// 與入隊(duì)函數(shù)類似，當(dāng)此時(shí)還存在出隊(duì)操作時(shí)，說(shuō)明隊(duì)列不為空，
// 但是此時(shí)front已經(jīng)超過(guò)索引值了（也就是與cap值相等），需要將front重置為0
if(pqueue->front == pqueue->cap)
pqueue->front = 0;
pqueue->size--;
return pqueue->elements[pqueue->front++];
}
實(shí)例代碼
創(chuàng)建三個(gè)文件: queue.c、queue.h、main.c，實(shí)現(xiàn)上面動(dòng)圖中的操作文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-637490.html
-
queue.c定義隊(duì)列具體的函數(shù)
#include "queue.h"
// 初始化隊(duì)列
void queue_init(queue_t* pqueue, int cap){
pqueue->elements = malloc(sizeof(int) * cap);
if(pqueue->elements == NULL){
printf("分配隊(duì)列存儲(chǔ)區(qū)失敗!\n");
return;
}
pqueue->cap = cap;
pqueue->rear = 0;
pqueue->front = 0;
pqueue->size = 0;
}
// 銷毀隊(duì)列
void queue_deinit(queue_t* pqueue){
free(pqueue->elements);
pqueue->elements = NULL;
pqueue->cap = 0;
pqueue->rear = 0;
pqueue->front = 0;
pqueue->size = 0;
}
// 入隊(duì)
void queue_push(queue_t* pqueue, int data){
if(pqueue->rear == pqueue->cap)
pqueue->rear = 0;
pqueue->elements[pqueue->rear++] = data;
pqueue->size++;
}
// 出隊(duì)
int queue_pop(queue_t* pqueue){
if(pqueue->front == pqueue->cap)
pqueue->front = 0;
pqueue->size--;
return pqueue->elements[pqueue->front++];
}
//判斷隊(duì)列是否已滿
int queue_full(queue_t* pqueue){
return pqueue->size == pqueue->cap;
}
// 判斷隊(duì)列是否為空
int queue_empty(queue_t* pqueue){
return pqueue->size == 0;
}
-
queue.h聲明隊(duì)列的相關(guān)函數(shù)和定義隊(duì)列
#ifndef __QUEUE_H
#define __QUEUE_H
#include <stdio.h>
#include <stdlib.h>
// 定義隊(duì)列
typedef struct queue{
int* elements;
int cap;
int rear;
int front;
int size;
}queue_t;
extern void queue_init(queue_t* pqueue, int cap);
extern void queue_deinit(queue_t* pqueue);
extern void queue_push(queue_t* pqueue, int data);
extern int queue_pop(queue_t* pqueue);
extern int queue_full(queue_t* pqueue);
extern int queue_empty(queue_t* pqueue);
#endif
-
main.c主函數(shù)使用隊(duì)列
#include "queue.h"
int main(void){
// 1. 創(chuàng)建一個(gè)隊(duì)列
queue_t queue;
// 2. 初始化隊(duì)列
queue_init(&queue, 4);
// 3. 入隊(duì)4個(gè)數(shù)據(jù)
printf("開(kāi)始第一次入隊(duì)（4個(gè)數(shù)據(jù)）: ");
int data = 10;
for(int i = 0; i < 4; i++){
if(!queue_full(&queue)){
printf("%d ", data);
queue_push(&queue, data);
data += 10;
}
}
printf("\n此時(shí)還剩%d個(gè)數(shù)據(jù)\n\n", queue.size);
// 4. 出隊(duì)2個(gè)數(shù)據(jù)
printf("開(kāi)始第一次出隊(duì)（2個(gè)數(shù)據(jù)）: ");
for(int i = 0; i < 2; i++){
if(!queue_empty(&queue)){
data = queue_pop(&queue);
printf("%d ", data);
}
}
printf("\n此時(shí)還剩%d個(gè)數(shù)據(jù)\n\n", queue.size);
// 5. 入隊(duì)2個(gè)數(shù)據(jù)
printf("開(kāi)始第二次入隊(duì)（2個(gè)數(shù)據(jù)）: ");
data = 10;
for(int i = 0; i < 2; i++){
if(!queue_full(&queue)){
printf("%d ", data);
queue_push(&queue, data);
data += 10;
}
}
printf("\n此時(shí)還剩%d個(gè)數(shù)據(jù)\n\n", queue.size);
// 6. 將所有數(shù)據(jù)全部取出
printf("將全部數(shù)據(jù)取出: ");
while(!queue_empty(&queue)){
data = queue_pop(&queue);
printf("%d ", data);
}
printf("\n此時(shí)還剩%d個(gè)數(shù)據(jù)\n\n", queue.size);
// 銷毀隊(duì)列
queue_deinit(&queue);
return 0;
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-隊(duì)列（C語(yǔ)言的簡(jiǎn)單實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
