Queue

queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue, analogously to the words used when people line up to wait for goods or services.

We know the python list could easy to implement the function of queue. But C need we build a struct and some methods to complete it.

Complexity

Algorithm	Avg	Worse
Space	O(n)	O(n)
Seach	O(n)	O(n)
Insert	O(1)	O(1)
delete	O(1)	O(1)

Define node of queue

typedef struct node
{
	nodetype *data;//数据域
	struct node *Next; //指向下一个节点
}queuenode;

nodetype means the data’s type could define to any type.

Define queue struct

typedef struct
{
	queuenode *front;//队首指针
	queuenode *end; //队尾指针
	int len;//队列长度
	
}cqueue;

Create a node

queuenode *createnode(nodetype *num){
	queuenode *node = (queuenode*)malloc(sizeof(queuenode));
	node->data = num;
	node->Next = NULL;
	return node;
}

Initial queue

cqueue *init_queue(){
	cqueue *queue = (cqueue*)malloc(sizeof(cqueue));
	queue->front = NULL;
	queue->end = NULL;
	queue->len = 0;
	return queue;
}

Push

void push(cqueue *queue, nodetype *data){
	queuenode* node = createnode(data);
	if(!queue->len){
		queue->front = node;
		queue->end = node;
	}else{
		queue->end->Next = node;
		queue->end = node;
	}
	queue->len++;
}

Pop

queuenode *pop(cqueue *queue){
	if(!queue->len){
		return NULL;
	}else{
		queuenode *node = queue->front;
		queue->front = node->Next ;
		node->Next = NULL;
		if(queue->end = node){
			queue->end = NULL;
		}
		queue->len--;
		return node;
	}
}

isEmpty

bool isEmpty(cqueue* queue){
	if(!queue->len){
		return 0;
	}else{
		return 1;
	}
}

Destory queue

void destory_queue(cqueue* queue){
	while(queue->len){
		queuenode *tmp = pop(queue)
		free(tmp);
	}
	printf("Success! The queue is None now\n");
}

Print queue

void printqueue(cqueue *queue){
	queuenode *tmp = queue->front;
	while(tmp){
		printf("%d ", tmp->data->val);
		tmp = tmp->Next;
	}
}

Search

bool search_queue(cqueue *queue, nodetype* num){
	queuenode *tmp = queue->front;
	while(tmp){
		if(tmp->data == num){
			return 1;
		}
		tmp = tmp->Next;
	}
	return 0;
}

how to implement a queue by C