C language queue

 

Catalog

Queue related concepts

Queue creation

Initialization of the queue

Queue insertion

Queue deletion

Take the head of the queue

Take the end of the queue

  Number of queue elements

Determines if the queue is empty

Destroy queue

---

Queue related concepts

First of all, the biggest feature of the queue is “ fifo ”, Only insert... At one end , Delete on the other end , The inserted end is the tail of the team , The deleted end is the head of the team .

Queue creation

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;
typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

Here we will create two structures , Because here we need to record his head and tail , This makes it easy to insert and delete .

Initialization of the queue

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

Queue insertion

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->tail == NULL)
    {
        pq->tail = pq->head = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}

Queue deletion

void QueuePoq(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QNode* cur = pq->head->next;
        free(pq->head);
        pq->head = cur;
    }
}

Take the head of the queue

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

Take the end of the queue

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

  Number of queue elements

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

Determines if the queue is empty

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

Destroy queue

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