以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(不设头指针)。试编写相应的置空队列、判断队列是否为空、入队和出队 等算法。
时间: 2023-05-26 14:03:25 浏览: 92
假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法 (Java)
```
#define MAXSIZE 100 //假设队列的最大长度为100
typedef struct node{
int data;
struct node *next;
}Node;
typedef struct{
Node *rear; //队尾指针
}Queue;
void initQueue(Queue *Q){//置空队列
Q->rear = NULL; //队尾指针初始化为空
}
bool isEmpty(Queue Q){//判断队列是否为空
return Q.rear == NULL;
}
bool enQueue(Queue *Q, int x){//入队
Node *newNode = (Node *)malloc(sizeof(Node));
if(newNode == NULL){//分配内存失败,入队失败
return false;
}
newNode->data = x;
if(Q->rear == NULL){//如果队列为空
newNode->next = newNode; //新结点的下一个结点是自身
Q->rear = newNode; //队尾指针指向新结点
}else{
newNode->next = Q->rear->next; //新结点与原来队尾指针所指结点的下一个结点相连
Q->rear->next = newNode; //原来队尾指针所指结点的下一个结点改为新结点
Q->rear = newNode; //修改队尾指针
}
return true;
}
bool deQueue(Queue *Q, int *x){//出队
if(Q->rear == NULL){//队列为空,出队失败
return false;
}
Node *p = Q->rear->next; //指向队头结点
if(Q->rear == p){//如果队列只有一个结点,出队后队列为空
Q->rear = NULL; //队尾指针重置为空
}else{
Q->rear->next = p->next; //队尾指针的下一个结点改为队头结点的下一个结点
}
*x = p->data; //返回出队的元素
free(p); //释放队头结点的内存
return true;
}
```
阅读全文