9.0 KiB
Introduction
A queue is a special data structure with the First In First Out (FIFO) characteristic. Generally, it has only one entrance and one exit. Data enters from the rear of the queue and exits from the front. The operations of adding data to the queue is called "push", and removing data from the queue is called "pop".
-
Capacity: Capacity refers to the maximum number of queue items that can be stored during use. For example, for a queue with a capacity of 10, it can store at most 10 queue items. Once it's full, no more data can be pushed into it. The queue storage in varch has continuous addresses and is a queue with a limited capacity.
-
Access Mechanism: Generally, a queue only has two ways of operation, which are enqueueing (push) and dequeueing (pop). It can be quickly traversed and accessed based on continuous addresses.
Interface
Creation and Deletion of queue Objects
queue_t queue_create(int dsize, int capacity, void *base);
void queue_delete(queue_t queue);
#define queue(type, capacity) // For more convenient use, a macro definition is wrapped around queue_create
#define _queue(queue) // A macro definition is wrapped around queue_delete, and the queue is set to NULL after deletion
Here, queue_t is the structure of the queue. The creation method will return a queue object, and it will return NULL if the creation fails. Among the parameters, dsize is used to pass in the size of the data, capacity is used to pass in the queue capacity, and *base is used to pass in the address of the buffer (it can be omitted, and if omitted, space with the size of capacity will be automatically allocated to store queue data). The deletion method is used to delete the passed-in queue object. The creation method and the deletion method should be used in pairs. Once created, the queue object should be deleted when it's no longer in use.
void test(void)
{
queue_t queue = queue(int, 10); // Define and create a queue of the int type with a capacity of 10
_queue(queue); // Use them in pairs and delete it after use
}
Enqueueing and Dequeueing of queue
int queue_push(queue_t queue, void* data);
int queue_pop(queue_t queue, void* data);
These two methods can conveniently add data to the queue and remove data from the queue. For the push method, the data parameter should pass in the address of the data to be enqueued. For the pop method, the data parameter should pass in the address of the data to receive the dequeued data. In both methods, data can also be passed as NULL, which just serves as a placeholder. They return 1 if the operation is successful and 0 if it fails.
void test(void)
{
queue_t queue = queue(int, 10);
int i = 0;
for (i = 0; i < queue_capacity(queue); i++)
{
queue_push(queue, &i);
}
queue_pop(queue, NULL);
queue_pop(queue, NULL);
_queue(queue); // Use them in pairs and delete it after use
}
Size, Capacity, and Data Size of queue
int queue_size(queue_t queue);
int queue_capacity(queue_t queue);
int queue_dsize(queue_t queue);
The capacity of the queue is the capacity specified during creation, which indicates how many queue elements it can store. The size is the number of elements currently in the queue. The dsize is the size of the data passed in during creation. For example, for int data, the dsize is sizeof(int).
void test(void)
{
queue_t queue = queue(int, 10);
int i = 0;
for (i = 0; i < queue_capacity(queue); i++)
{
queue_push(queue, &i);
}
queue_pop(queue, NULL);
queue_pop(queue, NULL);
printf("queue capacity=%d, size=%d, dsize=%d\r\n", queue_capacity(queue), queue_size(queue), queue_dsize(queue));
_queue(queue);
}
Results:
queue capacity=10, size=8, dsize=4
Reading and Writing of queue Data
void* queue_data(queue_t queue, int index);
#define queue_at(queue, type, i)
The queue_data method is used to obtain the address of the data according to the index and returns the address of the specified data. NULL indicates failure. The queue_at method adds the data type on the basis of queue_data.
void test(void)
{
queue_t queue = queue(int, 10);
int i = 0;
for (i = 0; i < queue_capacity(queue); i++)
{
queue_push(queue, &i);
}
queue_pop(queue, NULL);
queue_pop(queue, NULL);
for (i = 0; i < queue_size(queue); i++)
{
printf("queue[%d] = %d\r\n", i, queue_at(queue, int, i));
}
_queue(queue);
}
Results:
queue[0] = 2
queue[1] = 3
queue[2] = 4
queue[3] = 5
queue[4] = 6
queue[5] = 7
queue[6] = 8
queue[7] = 9
Queue Data Storage Index
int queue_index(queue_t queue, int index);
The queue storage structure is a circular queue, which means that the continuous address storage space is connected end to end to form a circle, and the queue data enters and exits within this circle. Therefore, the index of the queue is not directly the index of the buffer. The queue_index method is used to map the index of the queue to the index of the buffer. It returns -1 if the mapping fails. Generally, this method is not used frequently. It's mainly used when the base address is passed in during the queue_create method, and then the queue_index method is used on the base address to obtain queue data.
Empty Queue and Full Queue
int queue_empty(queue_t queue);
int queue_full(queue_t queue);
These two methods are actually related to the size of the queue. If the size is equal to 0, the queue is empty. If the size is equal to the capacity, the queue is full.
Source Code Analysis
queue Structure
All the structures of the queue container are implicit, which means that the members of the structures can't be accessed directly. This way ensures the independence and security of the module and prevents external calls from modifying the members of the structures, which could otherwise damage the storage structure of the queue. So the queue parser only leaves the single declaration of the queue in the header file, and the definitions of the structures are placed in the source file. Only the methods provided by the queue container can be used to operate on queue objects. The declaration of the queue type:
typedef struct QUEUE *queue_t;
When using it, just use queue_t.
typedef struct QUEUE
{
void* base; /* base address of data */
int cst; /* base const */
int dsize; /* size of queue data */
int capacity; /* capacity of queue */
int size; /* size of queue */
int head; /* index of queue head */
int tail; /* index of queue tail */
} QUEUE;
The QUEUE structure contains 7 members: base (the base address of the data buffer of the queue structure), cst (indicating whether the space of base is passed in during the create method), size (the size of the queue, that is, the length of the queue), dsize (the size of each data), capacity (the capacity of the queue), and head and tail which are the indexes pointed to by the head and tail of the circular buffer respectively.
The main problem that the queue container needs to solve is the issue of the circular queue and the First In First Out characteristic of data. Other operations like creation and deletion are mainly for basic initialization such as space initialization.
#define at(i) (((unsigned char *)(queue->base))+(i)*(queue->dsize)) /* address of void array */
int queue_push(queue_t queue, void* data)
{
if (!queue) return 0;
if (queue_full(queue)) return 0; // Check if the queue is full before enqueueing
if (data) memcpy(at(queue->tail), data, queue->dsize); // If the data address is specified, copy the data at the address to the address pointed to by the tail
queue->tail++; // Increment the tail by 1, indicating that data is pushed at the tail
queue->tail %= queue->capacity; // Take the remainder of tail divided by capacity to ensure that tail doesn't exceed capacity and form a circular structure
queue->size++; // Increase the size by 1
return 1;
}
int queue_pop(queue_t queue, void* data)
{
if (!queue) return 0;
if (queue_empty(queue)) return 0; // Check if the queue is empty before dequeueing
if (data) memcpy(data, at(queue->head), queue->dsize); // If the data address is specified, copy the data at the head to the address pointed to by data
queue->head++; // Increment the head by 1, indicating that data is popped from the head
queue->head %= queue->capacity; // Take the remainder of head divided by capacity to ensure that head doesn't exceed capacity and form a circular structure
queue->size--; // Decrease the size by 1
return 1;
}
These two functions queue_push and queue_pop implement the key operations of enqueueing and dequeueing in the circular queue, ensuring the correct operation of the FIFO mechanism within the limited capacity and circular structure.