preface

By and by, we have learned the sequence list, single linked list, double linked list and stack Today, what bloggers update is the queue in the data structure

1. What is a queue

Queue: a special linear table that only allows inserting data at one end and deleting data at the other end. The queue has the characteristics of first in first out

The end where only data insertion is allowed is called the end of the queue

Only one end of the data deletion operation is called the queue head

The deletion operation is called out of the queue, and the insertion operation is called in the queue

For all the above features, the blogger uses the following figure to show you:

2. How to implement queue

Since we want to implement the queue, we need to grab the supply according to the demand

So what are the main requirements of our queue? Yes, the answer is to join and leave the team

Join the team, there is no doubt that it is tail insertion operation, which is very convenient to realize with sequence table

Out of the team, there is no doubt that it is a header deletion operation, which is very convenient to realize with a linked list

In other words, we only consider the quality of the current operation. The linked list is the same as the sequence group. Let's consider the better possibility, huh ~ ~ Linked lists save more space than sequential lists

So we choose to implement the queue with linked list

However, if it is implemented with a linked list, the tail insertion operation is more troublesome (you need to traverse to the tail). How to solve this problem? Here, we use to open up another structure to contain the linked list nodes. There are only head and tail pointers in the new structure. Please see the next title for code implementation

3. Project construction

The blogger uses VS2019 here to demonstrate:

Create a queue first h,Queue. C and test C three documents

Queue.h is used to write file references and function declarations

Queue. The function of C is to write the definition of file function

test. The function of C is to test whether the written operation is correct

4. Define queue

Under the 2 title, it has been explained that the best way to implement the queue is to select the linked list structure and separate a structure for inclusion, so the following is the beginning of such implementation

typedef int QDataType;

typedef struct QueueNode  //Define queue node
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

typedef struct Queue   //Define queue
{
    QueueNode* head;  //Team leader
    QueueNode* tail;  //Team tail
}Queue;

5. All operations of the queue

For queues, we use the following operations most:

Queue entry (tail insertion), queue exit (head deletion), take the team head element, take the team tail element, judge the space, obtain the number of queue elements, and initialize and destroy space

So, bloggers first in queue All methods are declared in the H file and will be implemented in detail later

void QueueInit(Queue* pq);
bool QueueEmpty(Queue* pq);

void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
void QueueDestory(Queue* pq);

5.1 queue initialization

After we create a queue, the head and tail pointers of the queue are still wild pointers, so we initialize it to NULL

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

Test successful:

success!!

5.2 empty judgment of queue

Judge empty, that is, judge whether the queue is empty. How to judge? As long as the header pointer does not point to any space, the queue is empty

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    
    return pq->head == NULL;
}

5.3 queue entry

Join the team, that is, tail insertion. In the previous linked list and sequence chapters, we are still familiar with this operation:

The first step is to open up a new space to store data

Step 2: Tail - > next points to the new node (just note that when the linked list is empty)

void QueuePush(Queue* pq, QDataType elem)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if(newnode == NULL)
    {
        perror("Reason for space application failure:");
        exit(-1);
    }
    newnode->data = elem;
    newnode->next = NULL;
    
    //Note whether the queue here is empty
    pq->head == NULL ? (pq->tail = newnode ):(pq->tail->next = newnode,pq->tail = pq->tail->next); 
}

Test:

success!!!

5.4 leaving the queue

Obviously, when you leave the team, you delete the header. We are also familiar with the header deletion operation:

First, save the next node

The second step is to release the header node

Step 3: point to the next saved node

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq)); //If the queue is empty, it cannot be deleted
    
    QueueNode* next = pq->head->next;//Save next node
    free(pq->head);//release
    pq->head = next;//Point to the next node
}

Test successful:

Success??? Have you finished? Let's take a closer look at the above code and think about where there will be bugs

Yes, when there is only one node left at the end of the queue, the tail will be a wild pointer, as shown in the following figure:

You will find that when the last one is left, the tail still points to the original position to form a wild pointer

Modification code:

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq)); //If the queue is empty, it cannot be deleted
    
    QueueNode* next = NULL;
    
    pq->head->next == NULL?
    (free(pq->head),pq->head = pq->tail = NULL):
    (next = pq->head->next, free(pq->head),pq->head = next);//Conditional expression
}

Now the test is really successful

5.5 acquisition of queue leader

This is relatively simple and can be returned directly

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq)); //Cannot be empty
    
    return pa->head->data;
}

5.6 obtaining queue tail

Similarly, return directly

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq)); //Cannot be empty
    
    return pa->tail->data;
}

Test successful:

success!!

5.7 number of return queue elements

This directly opens a variable num, and then traverses the queue for counting

int QueueSize(Queue* pq)
{
    assert(pq);
    int num = 0;
    QueueNode* cur = pq->head;
    while(cur)
    {
        num++;
        cur = cur->next;
    }
    return num;
}

5.8 queue destruction space

Destroy each space one by one

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

Test successful:

success!!!

Total code

Queue.h header file

#pragma once
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int QDataType;

typedef struct QueueNode  //Define queue node
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

typedef struct Queue   //Define queue
{
    QueueNode* head;  //Team leader
    QueueNode* tail;  //Team tail
}Queue;


void QueueInit(Queue* pq);

void QueueDestory(Queue* pq);

void QueuePush(Queue* pq, QDataType elem);

void QueuePop(Queue* pq);

int QueueSize(Queue* pq);

QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);

Queue.c source file

#include "Queue.h"
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType elem)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("Reason for space application failure:");
		exit(-1);
	}
	newnode->data = elem;
	newnode->next = NULL;

	//Note whether the queue here is empty
	pq->head == NULL ? 
	(pq->tail = pq->head = newnode) : (pq->tail->next = newnode, pq->tail = pq->tail->next);
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq)); //If the queue is empty, it cannot be deleted

	QueueNode* next = NULL;

	pq->head->next == NULL ?
		(free(pq->head), pq->head = pq->tail = NULL) :
		(next = pq->head->next, free(pq->head), pq->head = next);//Conditional expression
}


int QueueSize(Queue* pq)
{
	assert(pq);

	int num = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		num++;
		cur = cur->next;
	}
	return num;
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}