queue

数据结构汇总之 queue

原文见 仓库

good good study, day day leetcode


队列:具有一定操作约束的线性表,只能在一端作插入、删除,与堆栈类似

  • 具有先入先出的特性(First In First Out)
  • 同理,分顺序存储结构、链式存储结构两种形式

以下是关于queue的总结

一、队列的顺序存储结构

  • 通常由一个一维数组和一个队列头元素变量front和一个队列尾元素变量rear组成
  • 加入一个元素rear加1,删除一个元素front加1
  • 空的时候front=rear,但是填满时front/rear也相等,这时便不利于区分;为此通常采用加1求余的方式,同时构成循环队列

  • 1)判断是否为空:front == rear 即为空

  • 2)判断是否为满:(rear+1)%MaxSize == front 即为满

图解如下:



0、结构初始化
1
2
3
4
5
6
7
#define Size ###
struct QueueNode {
ElementType *Data;
int MaxSize;
int front;
int rear;
};


1、建立空队列 createQueue
1
2
3
4
5
6
7
8
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
1
2
3
bool isFull(struct QueueNode* q) {
return ( (q->rear+1)%q->MaxSize == q->front );
}


3、判断队列是否为空 isEmpty
1
2
3
bool isEmpty(struct QueueNode* q) {
return ( q->rear == q->front );
}


4、入队操作addQueue
1
2
3
4
5
6
7
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
1
2
3
4
5
6
7
ElementType deleteQueue(struct QueueNode* q) {
if (isEmpty(q)) return false;
else {
q->front = (q->front+1)%q->MaxSize;
return q->Data[q->front];
}
}




二、队列的链式存储结构(不常用)

  • 同理,实际上也可以用一个单链表实现
  • 插入、删除分别在链表两头进行,即插入在表尾(rear),删除在表头(front)

图解如下:

0、结构初始化
1
2
3
4
5
6
7
8
9
struct ListNode {
ElementType val;
struct ListNode* next;
};
struct QueueNode {
int size;
struct ListNode* front;
struct ListNode* rear;
};


1、建立空队列 createQueue
1
2
3
4
5
6
7
struct QueueNode* createQueue() {
struct QueueNode* q=malloc(sizeof(struct QueueNode));
q->front = q->rear = NULL;
q->size=0;

return q;
}


2、入队操作addQueue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//插入在表尾
void addQueue(struct QueueNode* q,ElementType x) {
struct ListNode* temp=malloc(sizeof(struct ListNode));
temp->val=x;

if (q->size==0) {
q->front = q->rear =temp;
}
else {
q->rear->next=temp;
q->rear=temp;
}

q->size++;
}


3、出队操作deleteQueue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//删除在表头
ElementType deleteQueue(struct QueueNode* q) {
struct ListNode* temp;
ElementType tmp;

if (q->size==0) return ERROR;
else {
temp=q->front;
q->front=temp->next;
tmp=temp->val;

free(temp)
q->size--;
return tmp;
}
}




三、队列题型总结

主要用于二叉树的层序遍历


-------------本文结束感谢您的阅读-------------