隊列是和堆棧一樣是一種特殊的線性表,和堆棧不一樣的地方是是,堆棧是以后進先出的的數(shù)據(jù)組織方式,而隊列則正好相反先進先出的組織方式.
隊列又分為兩種隊列,一種是單向隊列,一種是雙向隊列.
同時,單向隊列又可以衍生出單向循環(huán)隊列.
一般我們選用順序存儲來實現(xiàn)隊列的時候,都是構(gòu)造循環(huán)隊列,這樣可以提高內(nèi)存空間的利用率.
下面我們來用數(shù)組實現(xiàn)一個單向循環(huán)隊列.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 9
typedef int ElementType;
struct QNode{
ElementType data[MAX_SIZE];
int front;
int rear;
};
typedef struct QNode* Queue;
/**
* 入隊
* @param ptrQ
* @param e
*/
void AddQ(Queue ptrQ , ElementType e){
//加1求余表示轉(zhuǎn)了一周了,例如我們有9個元素,當(dāng)我們的front=0的時候,我們的rear =8;
//此時表示隊列已經(jīng)滿了,我們不能再添加元素了,那么如何判斷呢,我們知道(rear=8)+1等于9%9 = 0 = front;
//同樣當(dāng)我們賺了一周之后,front = 3, rear = 2; 2+1 = 3 %9 = 3 = front ,因此這樣是可以判斷的
if((ptrQ->rear+1)%MAX_SIZE == ptrQ->front){
printf("隊列已滿\n");
return;
}
ptrQ->rear = (ptrQ->rear+1) % MAX_SIZE;
ptrQ->data[ptrQ->rear] = e;
}
/**
* 出隊
* @param ptrQ
* @param e
* @return
*/
int deleteQ(Queue ptrQ,ElementType *e){
if(ptrQ->rear == ptrQ->front){
printf("隊列已空\n");
return -1;
}else{
*e = ptrQ->data[ptrQ->front];
ptrQ->front = (ptrQ->front+1) % MAX_SIZE;
return 0;
}
}
