队列（顺序存储结构）

时间：2022-07-17 17:38:26
  • 队列：具有一定操作约束的线性表，只能在一端作插入、删除，与堆栈类似
  • 具有先入先出的特性（First In First Out）
  • 同理，分顺序存储结构、链式存储结构两种形式



队列（顺序存储结构）

  • 通常由一个一维数组和一个队列头元素变量front和一个队列尾元素变量rear组成
  • 加入一个元素rear加1，删除一个元素front加1

  • 空的时候front=rear,但是填满时front/rear也相等，这时便不利于区分；为此通常采用加1求余的方式,同时构成循环队列

  • 1）判断是否为空：front == rear 即为空

  • 2）判断是否为满：（rear+1）%MaxSize == front 即为满

图解如下：

队列（顺序存储结构）

队列（顺序存储结构）

0、结构初始化

#define Size ###
struct QueueNode {
    ElementType *Data;
int MaxSize;
int front;
int rear;
};


1、建立空队列 createQueue

struct QueueNode* createQueue() {
struct QueueNode* q=malloc(sizeof(struct QueueNode));
    q->Data=(ElementType*)malloc(MaxSize*sizeof(ElementType));
    q->front=q->rear=0;
    q->MaxSize=Size;

return q;
}


2、判断队列是否充满 isFull

bool isFull(struct QueueNode* q) {
return ( (q->rear+1)%q->MaxSize == q->front );
}


3、判断队列是否为空 isEmpty

bool isEmpty(struct QueueNode* q) {
return ( q->rear == q->front );
}


4、入队操作addQueue

void addQueue(struct QueueNode* q,ElementType x) {
if (isFull(q)) return false;
else {
        q->rear = (q->rear+1)%q->MaxSize;
        q->Data[q->rear]=x;
    }
}


5、出队操作deleteQueue

ElementType deleteQueue(struct QueueNode* q) {
if (isEmpty(q)) return false;
else {
        q->front = (q->front+1)%q->MaxSize;
return q->Data[q->front];
    }
}
标签：

相关文章