创建链队列,并实现置空、判断是否为空、入队、出队、返回 队头 元素基本算法。
时间: 2023-12-25 20:06:55 浏览: 98
好的,我可以回答这个问题。以下是链队列的基本算法实现:
1. 创建链队列
首先,我们需要定义一个队列结构体:
```
typedef struct QNode {
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LinkQueue;
```
其中,`QElemType` 是队列元素的数据类型。
创建空队列的代码如下:
```
Status InitQueue(LinkQueue *Q) {
Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
if (!Q->front) {
exit(OVERFLOW); // 存储空间已满
}
Q->front->next = NULL;
return OK;
}
```
2. 判断是否为空
如果队头指针和队尾指针相等,则说明队列是空的。
```
Status QueueEmpty(LinkQueue Q) {
if (Q.front == Q.rear) {
return TRUE;
} else {
return FALSE;
}
}
```
3. 入队
新元素入队时,需要创建一个新的节点并将其加入队列的尾部。
```
Status EnQueue(LinkQueue *Q, QElemType e) {
QueuePtr s = (QueuePtr) malloc(sizeof(QNode));
if (!s) {
exit(OVERFLOW); // 存储空间已满
}
s->data = e;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
return OK;
}
```
4. 出队
出队操作将队头的元素出队并返回其值。
```
Status DeQueue(LinkQueue *Q, QElemType *e) {
QueuePtr p;
if (Q->front == Q->rear) {
return ERROR; // 队列为空
}
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if (Q->rear == p) {
Q->rear = Q->front; // 已无元素,尾指针指向头结点
}
free(p);
return OK;
}
```
5. 返回队头元素
返回对头元素的值,但不删除该元素。
```
QElemType GetHead(LinkQueue Q) {
if (Q.front == Q.rear) {
exit(ERROR); // 队列为空
}
return Q.front->next->data;
}
```
这就是链队列的基本算法实现。希望能够帮到你!
阅读全文