C 中的链表队列：抛出异常：读取访问冲突。温度是 0x740069
Linked List Queue in C: Exception thrown: read access violation. temp was 0x740069
我正在使用 C 编写简单的链表队列程序，但我从我的打印函数中得到了这个异常。
抛出异常：读取访问冲突。临时为 0x740069.
我在C语言方面还是个初学者，所以我还不习惯管理内存和使用指针。所以我不确定原因是来自我的推送功能还是我的打印功能。
所以想请教一下这个异常是什么原因造成的，如何解决
我的代码如下
struct node_struct {
char *data;
struct node_struct *next;
};
typedef struct node_struct Node;
struct queue_struct {
Node *head, *tail;
};
typedef struct queue_struct Queue;
void push(Queue *q, char *word)
{
// IMPLEMENT
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = (char*)malloc(sizeof(char));
temp->data = word;
temp->next = NULL;
if (q->head == NULL )
{
q->head= temp;
}
else
{
q->tail->next = temp;
}
q->tail = temp;
q->tail->next = q->head;
}
char *pop(Queue *q)
{
// IMPLEMENT
Node* temp = q->head;
char n = q->head->data;
q->head = q->head->next;
free(temp);
return(n);
}
void print(Queue *q)
{
// IMPLEMENT
if (q == NULL)
{
printf("No Items\n");
}
else
{
//Node* temp = (Node*)malloc(sizeof(Node));
Node* temp = q->head;
while (temp != NULL)
{
printf("%c\n", temp->data);
temp = temp->next;
}
}
}
void print(Queue *q)
{
// IMPLEMENT
if (q == NULL || isEmpty(q))
{
printf("No Items\n");
}
else
{
//Node* temp = (Node*)malloc(sizeof(Node));
Node* temp = q->head;
while (temp != NULL)
{
printf("%c\n", temp->data);
temp = temp->next;
}
}
}
int isEmpty(Queue *q)
{
// IMPLEMENT
if (q->head == NULL)
return 1;
return 0;
}
void delete(Queue *q)
{
// IMPLEMENT
Node* temp;
while (q->head != NULL)
{
temp = q->head;
q->head = q->head->next;
delete(temp);
}
q->tail = NULL;
}
int main(int argc, char **argv)
{
Queue *q = NULL;
// print the queue
print(q);
// push items
push(&q, "a");
push(&q, "b");
push(&q, "c");
print(q);
}
输出如下图
Current output of my Queue
您的代码中有几处错误。如果您打开了编译器的警告，很多人就会被抓到。
In push：您想接收指向队列的指针。但主要是你传递了一个双指针。在 main 中，您还将队列声明为空指针，Queue *q = NULL; 因此没有队列（甚至没有空队列）。你可以做两件事：
收到push中的双指针并在指针中分配一个你return的空队列；
将main中的队列声明为空队列而不是指针，Queue q = {0};现在调用push(&q, "a");
在push中你在分配数据时也出错了。
使用 temp->data = (char*)malloc(sizeof(char)); 你只分配一个字符。
然后 temp->data = word;
你把它扔掉。你应该这样做：
temp->data = malloc(strlen(word)+1);
strcpy(temp->data, word);
在我的例子中，我使用一个字段来存储列表的大小，但没有它也可以完成，这是我对队列的实现，为了清楚起见，我添加了一些注释，也许你会发现它有用。而且我只添加了几个功能，如果你喜欢可以添加更多，这只是为了给你一个启动:)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// make an alias for better readability
typedef char * String;
typedef struct node_struct {
String data;
struct node_struct *next;
} Node;
typedef struct queue_struct {
Node *head, *tail;
} Queue;
// create a new node, allocating the memory and copying the value...
Node * Node_create(String str) {
Node *node = (Node *)malloc(sizeof(Node));
if(node == NULL) return NULL;
node->data = (String)malloc(strlen(str) + 1);
if(node->data == NULL) return NULL;
strcpy(node->data, str);
node->next = NULL;
return node;
}
// delete the node
void Node_delete(Node *node) {
free(node->data);
free(node);
}
// create a new Queue and set the head and tail to NULL(empty)
Queue * Queue_create() {
Queue *queue = (Queue *)malloc(sizeof(Queue));
if(queue == NULL) return NULL;
queue->head = queue->tail = NULL;
return queue;
}
// add a new node to the queue
bool Queue_push(Queue *q, String str) {
Node* node = Node_create(str);
if(node == NULL) return false;
// empty queue
if(q->head == NULL) {
q->head = q->tail = node;
// has only one element
}else if(q->head == q->tail) {
q->head->next = q->tail = node;
// has more than one element
}else {
q->tail->next = node;
q->tail = q->tail->next;
}
return true;
}
// print the elements of the queue
void Queue_print(Queue *q) {
Node *tmpNode = q->head;
printf("{");
// loop over the queue
while(tmpNode != NULL) {
printf("%s", tmpNode->data);
// don't print ',' if its the last element
tmpNode != q->tail && printf(", ");
tmpNode = tmpNode->next;
}
printf("}");
}
// get the size of the queue
int Queue_size(Queue *q) {
Node *tmpNode = q->head;
int size = 0;
while(tmpNode != NULL) {
tmpNode = tmpNode->next;
size++;
}
return size;
}
// remove the last element in the queue
String Queue_pop(Queue *q) {
String s = NULL;
// empty queue
if(q->head == NULL) return s;
// has one element
if(q->head == q->tail) {
s = q->head->data;
Node_delete(q->head);
q->head = q->tail = NULL;
// has two elements
}else if(q->head->next == q->tail) {
s = q->tail->data;
Node_delete(q->tail);
q->tail = q->head;
q->head->next = q->tail;
q->tail->next = NULL;
// has more than two
}else {
s = q->tail->data;
Node *tmpNode = q->head, *lastNode;
// loop over the queue and get the element before the last one
while(tmpNode != NULL) {
lastNode = tmpNode;
tmpNode = tmpNode->next;
// delete the last element and replace it with the previous element
if(tmpNode == q->tail) {
Node_delete(q->tail);
q->tail = lastNode;
q->tail->next = NULL;
return s;
}
}
}
return s;
}
// remove the first element in the queue
String Queue_shift(Queue *q) {
String s = NULL;
// empty queue
if(q->head == NULL) return NULL;
// has one element
if(q->head == q->tail) {
s = q->head->data;
Node_delete(q->head);
q->head = q->tail = NULL;
// has more than one
} else {
// just delete the first element and replace it with the next one
Node *tmpNode = q->head->next;
s = q->head->data;
Node_delete(q->head);
q->head = tmpNode;
}
return s;
}
// remove all the elements in the queue
void Queue_clear(Queue *q) {
Node *tmpNode = q->head;
for(int i = 0, n = Queue_size(q);i < n; i++) {
tmpNode = tmpNode->next;
// using the Queue_shift instead of Queue_pop because it's faster(low processing cost)
Queue_shift(q);
}
}
// remove all the elements in the queue and free the memory of the queue
void Queue_delete(Queue *q) {
Queue_clear(q);
free(q);
}
// check if the queue is empty
bool Queue_isEmpty(Queue *q) {
return q->head == NULL;
}
int main(void) {
Queue *a = Queue_create();
printf("Is empty: %s\n", Queue_isEmpty(a) ? "true" : "false");
Queue_push(a, "txt1");
printf("Size: %d\n", Queue_size(a));
printf("Is empty: %s\n", Queue_isEmpty(a) ? "true" : "false");
Queue_push(a, "txt2");
Queue_push(a, "txt3");
Queue_print(a);
Queue_shift(a);
printf("\nSize: %d\n", Queue_size(a));
Queue_pop(a);
Queue_push(a, "txt4");
Queue_push(a, "txt5");
printf("Size: %d\n", Queue_size(a));
Queue_print(a);
Queue_clear(a);
printf("\nSize: %d\n", Queue_size(a));
Queue_print(a);
Queue_push(a, "txt");
printf("\nSize: %d\n", Queue_size(a));
Queue_print(a);
Queue_delete(a);
return 0;
}
输出
Is empty: true
Size: 1
Is empty: false
{txt1, txt2, txt3}
Size: 2
Size: 3
{txt2, txt4, txt5}
Size: 0
{}
Size: 1
{txt}
根据您的评论确定：
I currently experiment with your version right now i want to ask if i don't want to use Queue *a = Queue_create(); in the main function but instead i want to made Queue *a = NULL; and then allocate space for it in push function how would you do it?
您可以这样做，请注意，您仍然可以以相同的方式使用其他功能，无需修改。甚至你仍然可以像第一部分那样直接使用 Queue_create Queue *q = Queue_create();。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// make an alias for better readability
typedef char * String;
typedef struct node_struct {
String data;
struct node_struct *next;
} Node;
typedef struct queue_struct {
Node *head, *tail;
} Queue;
// create a new node, allocating the memory and copying the value...
Node * Node_create(String str) {
Node *node = (Node *)malloc(sizeof(Node));
if(node == NULL) return NULL;
node->data = (String)malloc(strlen(str) + 1);
if(node->data == NULL) return NULL;
strcpy(node->data, str);
node->next = NULL;
return node;
}
// delete the node
void Node_delete(Node *node) {
free(node->data);
free(node);
}
// create a new Queue and set the head and tail to NULL(empty)
Queue * Queue_create() {
Queue *queue = (Queue *)malloc(sizeof(Queue));
if(queue == NULL) return NULL;
queue->head = queue->tail = NULL;
return queue;
}
// add a new node to the queue
bool Queue_push(Queue **q, String str) {
// if there is no allocated Queue then we need to allocate one using the Queue_create() we already have
if(*q == NULL) {
*q = Queue_create();
if(*q == NULL) return false;
}
Node* node = Node_create(str);
if(node == NULL) return false;
// empty queue
if((*q)->head == NULL) {
(*q)->head = (*q)->tail = node;
// has only one element
}else if((*q)->head == (*q)->tail) {
(*q)->head->next = (*q)->tail = node;
// has more than one element
}else {
(*q)->tail->next = node;
(*q)->tail = (*q)->tail->next;
}
return true;
}
// print the elements of the queue
void Queue_print(Queue *q) {
if(q != NULL) {
Node *tmpNode = q->head;
printf("{");
// loop over the queue
while(tmpNode != NULL) {
printf("%s", tmpNode->data);
// don't print ',' if its the last element
tmpNode != q->tail && printf(", ");
tmpNode = tmpNode->next;
}
printf("}");
}
}
// get the size of the queue
int Queue_size(Queue *q) {
if(q == NULL) return 0;
Node *tmpNode = q->head;
int size = 0;
while(tmpNode != NULL) {
tmpNode = tmpNode->next;
size++;
}
return size;
}
// remove the last element in the queue
String Queue_pop(Queue *q) {
if(q == NULL) return NULL;
String s = NULL;
// empty queue
if(q->head == NULL) return s;
// has one element
if(q->head == q->tail) {
s = q->head->data;
Node_delete(q->head);
q->head = q->tail = NULL;
// has two elements
}else if(q->head->next == q->tail) {
s = q->tail->data;
Node_delete(q->tail);
q->tail = q->head;
q->head->next = q->tail;
q->tail->next = NULL;
// has more than two
}else {
s = q->tail->data;
Node *tmpNode = q->head, *lastNode;
// loop over the queue and get the element before the last one
while(tmpNode != NULL) {
lastNode = tmpNode;
tmpNode = tmpNode->next;
// delete the last element and replace it with the previous element
if(tmpNode == q->tail) {
Node_delete(q->tail);
q->tail = lastNode;
q->tail->next = NULL;
return s;
}
}
}
return s;
}
// remove the first element in the queue
String Queue_shift(Queue *q) {
if(q == NULL) return NULL;
String s = NULL;
// empty queue
if(q->head == NULL) return NULL;
// has one element
if(q->head == q->tail) {
s = q->head->data;
Node_delete(q->head);
q->head = q->tail = NULL;
// has more than one
} else {
// just delete the first element and replace it with the next one
Node *tmpNode = q->head->next;
s = q->head->data;
Node_delete(q->head);
q->head = tmpNode;
}
return s;
}
// remove all the elements in the queue
void Queue_clear(Queue *q) {
if(q != NULL) {
Node *tmpNode = q->head;
for(int i = 0, n = Queue_size(q);i < n; i++) {
tmpNode = tmpNode->next;
// using the Queue_shift instead of Queue_pop because it's faster(low processing cost)
Queue_shift(q);
}
}
}
// remove all the elements in the queue and free the memory of the queue
void Queue_delete(Queue *q) {
if(q != NULL) {
Queue_clear(q);
free(q);
}
}
// check if the queue is empty
bool Queue_isEmpty(Queue *q) {
return q == NULL || q->head == NULL;
}
int main(void) {
Queue *a = NULL;
Queue_print(a);
printf("Is empty: %s\n", Queue_isEmpty(a) ? "true" : "false");
Queue_push(&a, "txt1");
printf("Size: %d\n", Queue_size(a));
printf("Is empty: %s\n", Queue_isEmpty(a) ? "true" : "false");
Queue_push(&a, "txt2");
Queue_push(&a, "txt3");
Queue_print(a);
Queue_shift(a);
printf("\nSize: %d\n", Queue_size(a));
Queue_pop(a);
Queue_push(&a, "txt4");
Queue_push(&a, "txt5");
printf("Size: %d\n", Queue_size(a));
Queue_print(a);
Queue_clear(a);
printf("\nSize: %d\n", Queue_size(a));
Queue_print(a);
Queue_push(&a, "txt");
printf("\nSize: %d\n", Queue_size(a));
Queue_print(a);
Queue_delete(a);
return 0;
}
输出
Is empty: true
Size: 1
Is empty: false
{txt1, txt2, txt3}
Size: 2
Size: 3
{txt2, txt4, txt5}
Size: 0
{}
Size: 1
{txt}
我正在使用 C 编写简单的链表队列程序，但我从我的打印函数中得到了这个异常。
抛出异常：读取访问冲突。临时为 0x740069.
我在C语言方面还是个初学者，所以我还不习惯管理内存和使用指针。所以我不确定原因是来自我的推送功能还是我的打印功能。
所以想请教一下这个异常是什么原因造成的，如何解决
我的代码如下
struct node_struct {
char *data;
struct node_struct *next;
};
typedef struct node_struct Node;
struct queue_struct {
Node *head, *tail;
};
typedef struct queue_struct Queue;
void push(Queue *q, char *word)
{
// IMPLEMENT
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = (char*)malloc(sizeof(char));
temp->data = word;
temp->next = NULL;
if (q->head == NULL )
{
q->head= temp;
}
else
{
q->tail->next = temp;
}
q->tail = temp;
q->tail->next = q->head;
}
char *pop(Queue *q)
{
// IMPLEMENT
Node* temp = q->head;
char n = q->head->data;
q->head = q->head->next;
free(temp);
return(n);
}
void print(Queue *q)
{
// IMPLEMENT
if (q == NULL)
{
printf("No Items\n");
}
else
{
//Node* temp = (Node*)malloc(sizeof(Node));
Node* temp = q->head;
while (temp != NULL)
{
printf("%c\n", temp->data);
temp = temp->next;
}
}
}
void print(Queue *q)
{
// IMPLEMENT
if (q == NULL || isEmpty(q))
{
printf("No Items\n");
}
else
{
//Node* temp = (Node*)malloc(sizeof(Node));
Node* temp = q->head;
while (temp != NULL)
{
printf("%c\n", temp->data);
temp = temp->next;
}
}
}
int isEmpty(Queue *q)
{
// IMPLEMENT
if (q->head == NULL)
return 1;
return 0;
}
void delete(Queue *q)
{
// IMPLEMENT
Node* temp;
while (q->head != NULL)
{
temp = q->head;
q->head = q->head->next;
delete(temp);
}
q->tail = NULL;
}
int main(int argc, char **argv)
{
Queue *q = NULL;
// print the queue
print(q);
// push items
push(&q, "a");
push(&q, "b");
push(&q, "c");
print(q);
}
输出如下图
Current output of my Queue
您的代码中有几处错误。如果您打开了编译器的警告，很多人就会被抓到。
In push：您想接收指向队列的指针。但主要是你传递了一个双指针。在 main 中，您还将队列声明为空指针，Queue *q = NULL; 因此没有队列（甚至没有空队列）。你可以做两件事：
收到
push中的双指针并在指针中分配一个你return的空队列；将
main中的队列声明为空队列而不是指针，Queue q = {0};现在调用push(&q, "a");
在push中你在分配数据时也出错了。
使用 temp->data = (char*)malloc(sizeof(char)); 你只分配一个字符。
然后 temp->data = word;
你把它扔掉。你应该这样做：
temp->data = malloc(strlen(word)+1);
strcpy(temp->data, word);
在我的例子中，我使用一个字段来存储列表的大小，但没有它也可以完成，这是我对队列的实现，为了清楚起见，我添加了一些注释，也许你会发现它有用。而且我只添加了几个功能，如果你喜欢可以添加更多，这只是为了给你一个启动:)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// make an alias for better readability
typedef char * String;
typedef struct node_struct {
String data;
struct node_struct *next;
} Node;
typedef struct queue_struct {
Node *head, *tail;
} Queue;
// create a new node, allocating the memory and copying the value...
Node * Node_create(String str) {
Node *node = (Node *)malloc(sizeof(Node));
if(node == NULL) return NULL;
node->data = (String)malloc(strlen(str) + 1);
if(node->data == NULL) return NULL;
strcpy(node->data, str);
node->next = NULL;
return node;
}
// delete the node
void Node_delete(Node *node) {
free(node->data);
free(node);
}
// create a new Queue and set the head and tail to NULL(empty)
Queue * Queue_create() {
Queue *queue = (Queue *)malloc(sizeof(Queue));
if(queue == NULL) return NULL;
queue->head = queue->tail = NULL;
return queue;
}
// add a new node to the queue
bool Queue_push(Queue *q, String str) {
Node* node = Node_create(str);
if(node == NULL) return false;
// empty queue
if(q->head == NULL) {
q->head = q->tail = node;
// has only one element
}else if(q->head == q->tail) {
q->head->next = q->tail = node;
// has more than one element
}else {
q->tail->next = node;
q->tail = q->tail->next;
}
return true;
}
// print the elements of the queue
void Queue_print(Queue *q) {
Node *tmpNode = q->head;
printf("{");
// loop over the queue
while(tmpNode != NULL) {
printf("%s", tmpNode->data);
// don't print ',' if its the last element
tmpNode != q->tail && printf(", ");
tmpNode = tmpNode->next;
}
printf("}");
}
// get the size of the queue
int Queue_size(Queue *q) {
Node *tmpNode = q->head;
int size = 0;
while(tmpNode != NULL) {
tmpNode = tmpNode->next;
size++;
}
return size;
}
// remove the last element in the queue
String Queue_pop(Queue *q) {
String s = NULL;
// empty queue
if(q->head == NULL) return s;
// has one element
if(q->head == q->tail) {
s = q->head->data;
Node_delete(q->head);
q->head = q->tail = NULL;
// has two elements
}else if(q->head->next == q->tail) {
s = q->tail->data;
Node_delete(q->tail);
q->tail = q->head;
q->head->next = q->tail;
q->tail->next = NULL;
// has more than two
}else {
s = q->tail->data;
Node *tmpNode = q->head, *lastNode;
// loop over the queue and get the element before the last one
while(tmpNode != NULL) {
lastNode = tmpNode;
tmpNode = tmpNode->next;
// delete the last element and replace it with the previous element
if(tmpNode == q->tail) {
Node_delete(q->tail);
q->tail = lastNode;
q->tail->next = NULL;
return s;
}
}
}
return s;
}
// remove the first element in the queue
String Queue_shift(Queue *q) {
String s = NULL;
// empty queue
if(q->head == NULL) return NULL;
// has one element
if(q->head == q->tail) {
s = q->head->data;
Node_delete(q->head);
q->head = q->tail = NULL;
// has more than one
} else {
// just delete the first element and replace it with the next one
Node *tmpNode = q->head->next;
s = q->head->data;
Node_delete(q->head);
q->head = tmpNode;
}
return s;
}
// remove all the elements in the queue
void Queue_clear(Queue *q) {
Node *tmpNode = q->head;
for(int i = 0, n = Queue_size(q);i < n; i++) {
tmpNode = tmpNode->next;
// using the Queue_shift instead of Queue_pop because it's faster(low processing cost)
Queue_shift(q);
}
}
// remove all the elements in the queue and free the memory of the queue
void Queue_delete(Queue *q) {
Queue_clear(q);
free(q);
}
// check if the queue is empty
bool Queue_isEmpty(Queue *q) {
return q->head == NULL;
}
int main(void) {
Queue *a = Queue_create();
printf("Is empty: %s\n", Queue_isEmpty(a) ? "true" : "false");
Queue_push(a, "txt1");
printf("Size: %d\n", Queue_size(a));
printf("Is empty: %s\n", Queue_isEmpty(a) ? "true" : "false");
Queue_push(a, "txt2");
Queue_push(a, "txt3");
Queue_print(a);
Queue_shift(a);
printf("\nSize: %d\n", Queue_size(a));
Queue_pop(a);
Queue_push(a, "txt4");
Queue_push(a, "txt5");
printf("Size: %d\n", Queue_size(a));
Queue_print(a);
Queue_clear(a);
printf("\nSize: %d\n", Queue_size(a));
Queue_print(a);
Queue_push(a, "txt");
printf("\nSize: %d\n", Queue_size(a));
Queue_print(a);
Queue_delete(a);
return 0;
}
输出
Is empty: true
Size: 1
Is empty: false
{txt1, txt2, txt3}
Size: 2
Size: 3
{txt2, txt4, txt5}
Size: 0
{}
Size: 1
{txt}
根据您的评论确定：
I currently experiment with your version right now i want to ask if i don't want to use Queue *a = Queue_create(); in the main function but instead i want to made Queue *a = NULL; and then allocate space for it in push function how would you do it?
您可以这样做，请注意，您仍然可以以相同的方式使用其他功能，无需修改。甚至你仍然可以像第一部分那样直接使用 Queue_create Queue *q = Queue_create();。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// make an alias for better readability
typedef char * String;
typedef struct node_struct {
String data;
struct node_struct *next;
} Node;
typedef struct queue_struct {
Node *head, *tail;
} Queue;
// create a new node, allocating the memory and copying the value...
Node * Node_create(String str) {
Node *node = (Node *)malloc(sizeof(Node));
if(node == NULL) return NULL;
node->data = (String)malloc(strlen(str) + 1);
if(node->data == NULL) return NULL;
strcpy(node->data, str);
node->next = NULL;
return node;
}
// delete the node
void Node_delete(Node *node) {
free(node->data);
free(node);
}
// create a new Queue and set the head and tail to NULL(empty)
Queue * Queue_create() {
Queue *queue = (Queue *)malloc(sizeof(Queue));
if(queue == NULL) return NULL;
queue->head = queue->tail = NULL;
return queue;
}
// add a new node to the queue
bool Queue_push(Queue **q, String str) {
// if there is no allocated Queue then we need to allocate one using the Queue_create() we already have
if(*q == NULL) {
*q = Queue_create();
if(*q == NULL) return false;
}
Node* node = Node_create(str);
if(node == NULL) return false;
// empty queue
if((*q)->head == NULL) {
(*q)->head = (*q)->tail = node;
// has only one element
}else if((*q)->head == (*q)->tail) {
(*q)->head->next = (*q)->tail = node;
// has more than one element
}else {
(*q)->tail->next = node;
(*q)->tail = (*q)->tail->next;
}
return true;
}
// print the elements of the queue
void Queue_print(Queue *q) {
if(q != NULL) {
Node *tmpNode = q->head;
printf("{");
// loop over the queue
while(tmpNode != NULL) {
printf("%s", tmpNode->data);
// don't print ',' if its the last element
tmpNode != q->tail && printf(", ");
tmpNode = tmpNode->next;
}
printf("}");
}
}
// get the size of the queue
int Queue_size(Queue *q) {
if(q == NULL) return 0;
Node *tmpNode = q->head;
int size = 0;
while(tmpNode != NULL) {
tmpNode = tmpNode->next;
size++;
}
return size;
}
// remove the last element in the queue
String Queue_pop(Queue *q) {
if(q == NULL) return NULL;
String s = NULL;
// empty queue
if(q->head == NULL) return s;
// has one element
if(q->head == q->tail) {
s = q->head->data;
Node_delete(q->head);
q->head = q->tail = NULL;
// has two elements
}else if(q->head->next == q->tail) {
s = q->tail->data;
Node_delete(q->tail);
q->tail = q->head;
q->head->next = q->tail;
q->tail->next = NULL;
// has more than two
}else {
s = q->tail->data;
Node *tmpNode = q->head, *lastNode;
// loop over the queue and get the element before the last one
while(tmpNode != NULL) {
lastNode = tmpNode;
tmpNode = tmpNode->next;
// delete the last element and replace it with the previous element
if(tmpNode == q->tail) {
Node_delete(q->tail);
q->tail = lastNode;
q->tail->next = NULL;
return s;
}
}
}
return s;
}
// remove the first element in the queue
String Queue_shift(Queue *q) {
if(q == NULL) return NULL;
String s = NULL;
// empty queue
if(q->head == NULL) return NULL;
// has one element
if(q->head == q->tail) {
s = q->head->data;
Node_delete(q->head);
q->head = q->tail = NULL;
// has more than one
} else {
// just delete the first element and replace it with the next one
Node *tmpNode = q->head->next;
s = q->head->data;
Node_delete(q->head);
q->head = tmpNode;
}
return s;
}
// remove all the elements in the queue
void Queue_clear(Queue *q) {
if(q != NULL) {
Node *tmpNode = q->head;
for(int i = 0, n = Queue_size(q);i < n; i++) {
tmpNode = tmpNode->next;
// using the Queue_shift instead of Queue_pop because it's faster(low processing cost)
Queue_shift(q);
}
}
}
// remove all the elements in the queue and free the memory of the queue
void Queue_delete(Queue *q) {
if(q != NULL) {
Queue_clear(q);
free(q);
}
}
// check if the queue is empty
bool Queue_isEmpty(Queue *q) {
return q == NULL || q->head == NULL;
}
int main(void) {
Queue *a = NULL;
Queue_print(a);
printf("Is empty: %s\n", Queue_isEmpty(a) ? "true" : "false");
Queue_push(&a, "txt1");
printf("Size: %d\n", Queue_size(a));
printf("Is empty: %s\n", Queue_isEmpty(a) ? "true" : "false");
Queue_push(&a, "txt2");
Queue_push(&a, "txt3");
Queue_print(a);
Queue_shift(a);
printf("\nSize: %d\n", Queue_size(a));
Queue_pop(a);
Queue_push(&a, "txt4");
Queue_push(&a, "txt5");
printf("Size: %d\n", Queue_size(a));
Queue_print(a);
Queue_clear(a);
printf("\nSize: %d\n", Queue_size(a));
Queue_print(a);
Queue_push(&a, "txt");
printf("\nSize: %d\n", Queue_size(a));
Queue_print(a);
Queue_delete(a);
return 0;
}
输出
Is empty: true
Size: 1
Is empty: false
{txt1, txt2, txt3}
Size: 2
Size: 3
{txt2, txt4, txt5}
Size: 0
{}
Size: 1
{txt}