[数据结构与算法]数据结构-队列（Queue）-定义与基本操作

一. 循环队列（Loop Queue）

1. 定义

#define MaxSize 10								// 定义队列中元素的最大个数
typedef struct {
    int data[MaxSize];  						// 存放队列元素
    int front, rear;    						// 队头指针和队尾指针
}SqQueue;

2. 基本操作

2.1 初始化

// 初始化
void InitQueue(SqQueue &Q) {
    Q.front = Q.rear = 0;						// 初始化队头指针和队尾指针
}

2.2 入队

// 入队
bool EnQueue(SqQueue &Q, int x) {
    if ((Q.rear + 1) % MaxSize == Q.front) {	// 队满
        return false;
    }
    Q.data[Q.rear] = x;                         // 新元素插入队尾
    Q.rear = (Q.rear + 1) % MaxSize;            // 队尾指针向前移动
    return true;
}

2.3 出队

// 出队
bool DeQueue(SqQueue &Q, int &x) {
    if (Q.front == Q.rear) {                    // 队空
        return false;
    }
    x = Q.data[Q.front];						// x记录队头元素
    Q.front = (Q.front + 1) % MaxSize;			// 队头指针向前移动
    return true;
}

2.4 取队头元素

// 取队头元素
bool GetHead(SqQueue Q, int &x) {
    if (Q.front == Q.rear) {                    // 队空
        return false;
    }
    x = Q.data[Q.front];						// x记录队头元素
    return true;
}

2.5 判空

// 判断空队列
bool QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear;
}

二. 链队列（Linked Queue）

1. 定义

typedef struct QueueNode {                       // 定义链队列结点数据类型
    int data;                                    // 数据域
    struct QueueNode *next;                      // 指针域
}QueueNode;

typedef struct {                        		// 链队列
    QueueNode *front, *rear;            		// 队头指针和队尾指针
}LinkQueue;

2. 基本操作

2.1 初始化

// 初始化（带头结点）
void InitQueue(LinkQueue &Q) {
	// 创建头结点，初始时front、rear都指向头结点。
    Q.front = Q.rear = (QueueNode *)malloc(sizeof(QueueNode));  
    Q.front->next = NULL;
}

2.2 入队

// 入队（带头结点）
void EnQueue(LinkQueue &Q, int x) {
    QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
    p->data = x;
    p->next = NULL;
    Q.rear->next = p;                   		// 新结点p插入队尾
    Q.rear = p;                         		// 修改队尾指针指向p
}

2.3 出队

// 出队（带头结点）
bool DeQueue(LinkQueue &Q, int &x) {
    if (Q.front == Q.rear) {					// 队空
        return false;                    		
    }
    QueueNode *p = Q.front->next;				// p为队头结点
    x = p->data;                        		// x记录队头元素
    Q.front->next = p->next;            		// 修改队头指针指向下一个结点
    // 如果p为队尾结点，则出队后变为空队。
    if (Q.rear == p) {
        Q.rear = Q.front;
    }
    free(p);                            		// 释放原队头结点的空间
    return true;
}

2.4 取队头元素

// 取队头元素（带头结点）
bool GetHead(LinkQueue &Q, int &x) {
    if (Q.front == Q.rear) {            		// 队空
        return false;
    }
    QueueNode *p = Q.front->next;       		// p为队头结点
    x = p->data;                        		// x记录队头元素
    return true;
}

2.5 判空

// 判断空队
bool QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}