1. Queue
A queue is a linear table restricted to insert and delete operations at both ends.
The end that allows store operations is called the “tail” and the end that allows delete operations is called the “head strong>” When there are no elements in the linear list, it is called “empty queue”.
Features: First in first out (FIFO).
2. Circular queue
Regulations: front points to the position of the element at the head of the queue; rear points to the next position of the element at the tail of the queue.
During the operation of the queue, in order to improve the efficiency, the movement of the queue elements is replaced by adjusting the pointer, and the array is used as the operation space of the circular queue.
To distinguish between an empty queue and a full queue, the number of full queue elements is one less than the number of array elements.
3. Sequential queue
Full and Empty are required.
sq->front = sq->rear = 0; // empty queue
(sq->rear + 1) % N == sq->front // Judging that the queue is full
Structure Description
typedef int data_t ; /Define the data type of the data element in the queue/
#define N 64 /Define the capacity of the queue/
typedef struct {
data_t data[N] ; /use the array as the storage space of the queue/
int front, rear ; /Pointers indicating the position of the head and tail of the queue/
} sequeue_t ; /sequence queue type definition/
sequeue * queue_create(); // create
int enqueue(sequeue *sq,datatype value); // enqueue
datatype dequeue(sequeue *sq); // dequeue
int queue_empty(sequeue *sq); // Interpret the empty queue
int queue_full(sequeue *sq); // read queue full
int queue_clear(sequeue *sq); // clear the queue
sequeue * queue_free(sequeue *sq); // release the queue
Implementation Framework
sequeue.h
typedef int datatype;
#define N 128
typedef struct{<!-- -->
datatype data[N];
int front;
int rear;
} sequeue;
sequeue * queue_create(); // create
int enqueue(sequeue *sq,datatype value); // enqueue
datatype dequeue(sequeue *sq); // dequeue
int queue_empty(sequeue *sq); // Interpret the empty queue
int queue_full(sequeue *sq); // read queue full
int queue_clear(sequeue *sq); // clear the queue
sequeue * queue_free(sequeue *sq); // release the queue
sequeue.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "sequeue.h"
sequeue * queue_create()
{<!-- -->
sequence *sq;
if((sq = (sequeue *)malloc(sizeof(sequeue))) == NULL){<!-- -->
printf("malloc failed\
");
return NULL;
}
memset(sq->data, 0 , sizeof(sq->data));
// This step is critical
sq->front = sq->rear = 0; // empty queue
\t
return sq;
}
int enqueue(sequeue *sq, datatype value)
{<!-- -->
if(sq == NULL){<!-- -->
printf("sq is NULL\
");
return -1;
}
if((sq->rear + 1) % N == sq->front){<!-- --> //queue full
printf("sequeue is full\
");
return -1;
}
sq->data[sq->rear] = value;
sq->rear = (sq->rear + 1) % N;
return 0;
}
datatype dequeue(sequeue *sq)
{<!-- -->
if(sq == NULL){<!-- -->
printf("sq is NULL\
");
return -1;
}
datatype t;
t = sq->data[sq->front];
sq->front = (sq->front + 1) % N;
return t;
}
int queue_full(sequeue *sq)
{<!-- -->
if(sq == NULL){<!-- -->
printf("sq is NULL\
");
return -1;
}
if((sq->rear + 1 ) % N == sq->front){<!-- -->
return 1;
}else{<!-- -->
return 0;
}
}
int queue_clear(sequeue *sq)
{<!-- -->
if(sq == NULL){<!-- -->
printf("sq is NULL\
");
return -1;
}
sq->front = sq->rear = 0;
return 0;
}
sequeue *queue_free(sequeue *sq)
{<!-- -->
if(sq == NULL){<!-- -->
printf("sq is NULL\
");
return NULL;
}
free(sq);
//Need to be empty, otherwise it will become a wild pointer
sq = NULL;
\t
return NULL;
}
int queue_empty(sequeue *sq)
{<!-- -->
if(sq == NULL){<!-- -->
printf("sq is NULL\
");
return -1;
}
return (sq->front == sq->rear ? 1 : 0);
}
test.c
#include <stdio.h>
#include "sequeue.h"
int main(int argc, const char *argv[])
{<!-- -->
sequence *sq;
\t
sq = queue_create();
if(sq == NULL){<!-- -->
return -1;
}
enqueue(sq,10);
enqueue(sq,20);
enqueue(sq,30);
enqueue(sq,40);
enqueue(sq,50);
enqueue(sq,666);
while(!queue_empty(sq)){<!-- -->
printf("dequeue:%d\
",dequeue(sq));
\t
}
queue_free(sq);
return 0;
}
4. Chain queue
The insertion operation is performed at the end of the queue, and the deletion operation is performed at the head of the queue. The operation of the queue is controlled by the queue head pointer and the queue tail pointer.
Question: Does the chained queue have false overflow? Does the chained queue need to judge empty and full? Why?
answer:
(1) There is no false overflow. Because when performing queue operations, you can only enter the queue from the tail of the queue, and exit the queue from the head of the queue.
(2) It needs to be judged empty, because the chained queue may have no elements. There is no need to judge full, because enqueueing is implemented from the end of the queue, and chained queues can apply for dynamic space.
Structure Description:
typedef int datatype;
typedef struct node{
datatype data;
struct node * next;
}listnode,*linklist;
typedef struct{
linklist front;
linklist rear;
}linkqueue;
Create empty queue:
linkqueue_t *CreateQueue()
{
linkqueue_t *lq = (linkqueue_t *)malloc(sizeof(linkqueue_t));
lq->front = lq->rear = (linklist_t)malloc(sizeof(linknode_t));
lq->front->next = NULL ; /empty queue/
return lq; /return queue pointer/
}
Judging that the queue is empty:
int EmptyQueue(linkqueue_t *lq) {
return (lq->front == lq->rear) ;
}
Join the team:
void EnQueue (linkqueue_t *lq, data_t x)
{
Bold style lq->rear->next = (linklist_t)malloc(sizeof(linknode_t)) ;
lq->rear = lq->rear->next; /Modify the tail pointer/
lq->rear->data = x ; /New data is stored in the new node/
lq->rear->next = NULL ; /The new node is the end of the queue/
return;
}
Dequeue
data_t DeQueue(linkqueue_t *lq)
{
data_t x;
linklist_t p; /Define an auxiliary pointer to the queue head node/
p = lq->front->next ; /point it to the front of the queue/
lq->front->next = p->next ; /*Delete the original queue head node
x = p->data;
free§ ; /Release the original head node/
if (lq->front->next == NULL) lq->rear = lq->front;
return x;
}
Implementation Framework
linkqueue.h
typedef int datatype;
typedef struct node{<!-- -->
datatype data;
struct node * next;
}listnode,*linklist;
typedef struct{<!-- -->
linklist front;
linklist rear;
}linkqueue;
linkqueue * queue_create();
int enqueue(linkqueue *lq, datatype x);
datatype dequeue(linkqueue *lq);
int queue_empty(linkqueue *lq);
int queue_clear(linkqueue *lq);
linkqueue * queue_free(linkqueue *lq); // return linkqueue * to prevent the program from performing other queue operations
linkqueue.c
#include <stdio.h>
#include <stdlib.h>
#include "linkqueue.h"
linkqueue * queue_create()
{<!-- -->
linkqueue *lq;
if( (lq = (linkqueue *)malloc(sizeof(linkqueue))) == NULL){<!-- -->
printf("malloc linkqueue failed\
");
return NULL;
}
// The two mallocs are different
lq->front = lq->rear = (linklist)malloc(sizeof(listnode));
if(lq->front == NULL){<!-- -->
printf("malloc node failed\
");
return NULL;
}
\t
// head node
lq->front->data = 0;
lq->front->next = NULL;
return lq;
\t
}
int enqueue(linkqueue *lq, datatype x)
{<!-- -->
linklist p;
if(lq == NULL){<!-- -->
printf("lq is NULL\
");
return -1;
}
if((p = (linklist)malloc(sizeof(listnode))) == NULL){<!-- -->
printf("malloc node failed\
");
return -1;
}
p->data = x;
p->next = NULL;
lq->rear->next = p;
lq->rear = p;
return 0;
}
datatype dequeue(linkqueue *lq)
{<!-- -->
linklist p;
if(lq == NULL){<!-- -->
printf("lq is NULL\
");
return -1;
}
\t
p = lq->front;
lq->front = p->next;
free(p);
p = NULL;
return (lq->front->data);
}
int queue_empty(linkqueue *lq)
{<!-- -->
if(lq == NULL){<!-- -->
printf("lq is NULL\
");
return -1;
}
return (lq->front == lq->rear ? 1 : 0);
}
int queue_clear(linkqueue *lq)
{<!-- -->
linklist p;
if(lq == NULL){<!-- -->
printf("lq is NULL\
");
return -1;
}
while(lq->front->next){<!-- --> //There will be the last one left
p = lq->front;
lq->front = p->next;
printf("clear free:%d\
",p->data);
free(p);
p = NULL;
}
return 0;
}
linkqueue * queue_free(linkqueue *lq)
{<!-- -->
linklist p;
if(lq == NULL){<!-- -->
printf("lq is NULL\
");
return NULL;
}
while(lq->front){<!-- -->
p = lq->front;
lq->front = p->next;
printf("free:%d\
",p->data);
free(p);
}
free(lq);
lq = NULL;
return NULL;
}
test.c
#include <stdio.h>
#include "linkqueue.h"
int main(int argc, const char *argv[])
{<!-- -->
linkqueue *lq;
lq = queue_create();
if (lq == NULL)
return -1;
enqueue(lq, 10);
enqueue(lq, 20);
enqueue(lq, 30);
enqueue(lq, 40);
//while (!queue_free_empty(lq)) {<!-- -->
printf("dequeue:%d\
", dequeue(lq));
}
queue_clear(lq);
\t
lq = queue_free(lq);
enqueue(lq, 50);
\t
return 0;
}