假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点,但不设头指针,要求给出队列类型表示,并写出队列相应的初始化、入队和出队算法。
时间: 2024-04-30 15:04:28 浏览: 104
假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法 (Java)
这个问题是关于数据结构的,可以回答。队列类型的表示可以使用如下结构体:
```
typedef struct QueueNode{
int data;
struct QueueNode *next;
}QueueNode;
typedef struct Queue{
QueueNode *rear;
}Queue;
```
初始化算法:
```
void initQueue(Queue *q){
q->rear = NULL;
}
```
入队算法:
```
void enQueue(Queue *q, int data){
QueueNode *p = (QueueNode*)malloc(sizeof(QueueNode));
p->data = data;
p->next = q->rear->next;
q->rear->next = p;
q->rear = p;
}
```
出队算法:
```
void deQueue(Queue *q, int *data){
if (q->rear == NULL || q->rear->next == q->rear){ //空队列或只有一个元素
*data = -1; //标记出队失败
return;
}
QueueNode *p = q->rear->next->next;
*data = q->rear->next->data;
free(q->rear->next);
q->rear->next = p;
if (p == NULL){ //此时队列已经为空
q->rear = NULL;
}
}
```
阅读全文