Implementation of queue (C language)

Implementation of queues

A queue is a first in, first out （First in First Out） The linear table , abbreviation FIFO. Unlike stacks , A stack is a last in, first out （ First in, then out ） The linear table . In the queue , The end allowed to be inserted is called the end of the queue , The end allowed to be deleted is called the team leader . Suppose the queue is q=（a1,a2,…,an）, that a1 It's the team leader element , and an It's the tail of the team . So we can delete , Always from a1 Start , And when inserted , Listed last . This is also more in line with our usual habits in life , The first priority , The last one came, of course, at the end of the team . Queues are divided into sequential queues and cyclic queues . Sequential queue can be realized by array or linked list . here , We choose to use linked list to realize sequential queue .

Today, we mainly introduce the queue and circular queue implemented by linked list

Chain queues

What are the main basic operations of a queue

//  Initialize queue  
void QueueInit(Queue* q);
​
//  Tail in queue  
void QueuePush(Queue* q, QDataType data);
//  Team leader out of line  
void QueuePop(Queue* q);
//  Get queue header elements  
QDataType QueueFront(Queue* q);
//  Get queue tail element  
QDataType QueueBack(Queue* q);
//  Get the number of valid elements in the queue  
int QueueSize(Queue* q);
//  Check if the queue is empty , If NULL, return non-zero result , If not null, return 0 
bool QueueEmpty(Queue* q);
//  Destroy queue  
void QueueDestroy(Queue* q);

Definition of chain queue

typedef int QDataType;
//  The chain structure ： Represents a queue  
typedef struct QListNode
{
    struct QListNode* _next;
    QDataType _data;
}QNode;
​
//  The structure of the queue  
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
}Queue;

The implementation of chain queue

1、 Initialize queue

void QueueInit(Queue* q)
{
    assert(q);
    q->_front = NULL;
    q->_rear = NULL;
}

2、 Destroy queue

void QueueDestroy(Queue* q)
{
    assert(q);
    QNode* cur = q->_front;
    while (cur != NULL)
    {
        QNode* next = cur->_next;
        free(cur);
        cur = next;
    }
    q->_front = q->_rear = NULL;
}

3、 Queue empty

bool QueueEmpty(Queue* q)
{
    assert(q);
    //if (q->_front == NULL)
    //{
    //  return 1;
    //}
    //else
    //{
    //  return 0;
    //}
    return q->_front == NULL;
}

 

4、 Joining operation

void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        exit(-1);
    }
    newnode->_data = data;
    newnode->_next = NULL;
    if (q->_front == NULL)
    {
        q->_front = q->_rear = newnode;
    }
    else
    {
        q->_rear->_next = newnode;
        q->_rear = newnode;
    }
}

5、 Out of line operation

void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    QNode* next = q->_front->_next;
    free(q->_front);
    q->_front = next;
    if (q->_front == NULL)
    {
        q->_rear = NULL;
    }
}

6、 Take the team leader element

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->_front->_data;
}

7、 End of queue operation

QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    return q->_rear->_data;
}

​

8、 The number of effective elements in the team

int QueueSize(Queue* q)
{
    assert(q);
    int size = 0;
    QNode* cur = q->_front;
    while (cur) 
    {
        size++;
        cur = cur->_next;
    }
    return size;
}

Circular queue

Circular queue is to wrap the last position of queue storage space to the first position , Form a logical ring space , For queue recycling . In the circular queue structure , When the last position of the storage space has been used and it is necessary to enter the queue operation , Only the first location of the storage space is free , You can add the element to the first position , The first location of the storage space will be used as the tail of the team . Circular queues can more easily prevent pseudo overflow , But the queue size is fixed . In the loop queue , When the queue is empty , Yes front=rear, And when all the queue space is full , Also have front=rear. To distinguish between these two situations , Specifies that the circular queue can have at most MaxSize-1 Queue elements , When there is only one empty storage unit left in the circular queue , The queue is full . therefore , The condition of empty queue is front=rear, The condition for the queue to be full is front=（rear+1)%MaxSize.

The space of the circular queue can be reused , It solves the problem of space waste of ordinary queues

Implementation of circular queue

typedef struct {
    int *a;
    int front;
    int tail;
    int k;
} MyCircularQueue;
​
// Declare in advance that the sentence is empty and the sentence is full 
bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);
// Create circular queue 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    cq->a=(int*)malloc(sizeof(int)*(k+1));
    cq->front=cq->tail=0;
    cq->k=k;
    return cq;
}
// Loop queue in 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj)){
        return false;
    }
    obj->a[obj->tail]=value;
    obj->tail++;
    obj->tail%=(obj->k+1);
​
    return true;
}
// Loop queue out 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return false;
    }
    obj->front++;
    obj->front%=(obj->k+1);
    return true;
​
}
// Loop queue fetch header 
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    return obj->a[obj->front];
}
// End of loop queue 
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
    int i=(obj->tail+obj->k)%(obj->k+1);
    return obj->a[i];
}
// Circular queue null 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->tail;
}
// The loop queue is full 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->front;
}
// Destroy circular queue 
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

​