用c语言设计一个双向队列,在表头、表尾两端都可以插入和删除。 1)画双向队列示例图,给出队列的数据类型定义。 2)当队空或满时,如何设定判定条件。3)设计入列、出列操作。
时间: 2023-05-12 07:04:16 浏览: 146
1) 双向队列示例图如下:
```
typedef struct node {
int data;
struct node *prev;
struct node *next;
} Node;
typedef struct deque {
Node *front;
Node *rear;
} Deque;
```
2) 当队空时,判定条件为 `front == NULL` 或 `rear == NULL`,当队满时,判定条件为 `无`,因为双向队列可以动态扩容。
3) 入列操作:
```
void enqueue_front(Deque *dq, int data) {
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->data = data;
new_node->prev = NULL;
new_node->next = dq->front;
if (dq->front == NULL) {
dq->rear = new_node;
} else {
dq->front->prev = new_node;
}
dq->front = new_node;
}
void enqueue_rear(Deque *dq, int data) {
Node *new_node = (Node *)malloc(sizeof(Node));
new_node->data = data;
new_node->prev = dq->rear;
new_node->next = NULL;
if (dq->rear == NULL) {
dq->front = new_node;
} else {
dq->rear->next = new_node;
}
dq->rear = new_node;
}
```
出列操作:
```
int dequeue_front(Deque *dq) {
if (dq->front == NULL) {
return -1;
}
int data = dq->front->data;
Node *temp = dq->front;
dq->front = dq->front->next;
if (dq->front == NULL) {
dq->rear = NULL;
} else {
dq->front->prev = NULL;
}
free(temp);
return data;
}
int dequeue_rear(Deque *dq) {
if (dq->rear == NULL) {
return -1;
}
int data = dq->rear->data;
Node *temp = dq->rear;
dq->rear = dq->rear->prev;
if (dq->rear == NULL) {
dq->front = NULL;
} else {
dq->rear->next = NULL;
}
free(temp);
return data;
}
```
阅读全文