05_ queue

queue

The essence ： The linear table
principle ： fifo
Queued 2 A design ：

• Sequence table design , It's called a sequential queue
• Chain design , It's called a chained queue

1 Sequential queue

Design improvements ： Circular queue

The linear table itself is not a ring , But to solve the problem, we need to consider the problem of forming a ring ：

1. Joseph ring

2. Magic circle

2 Circular queue ：

Structure definition ：

API Realization

// queue ： A linear structure of first in first out , The end of the team is called the end of the team , The end of the team is called the opponent 
// There are two ways to store queues ： Sequential structure （ Sequential queue ）. The chain structure （ Chain queues ）

// The sequential queue must be designed as a ring queue , The reason is the linear queue entry O(1), Out of the team is O（n）
// The entry and exit of the ring queue are O（1）

// Full sentence ： The tail pointer takes another step to the end pointer ; Waste a space without , Mainly to distinguish between empty and full 

// Full contract improvement ： You can add a counter , Count how many elements are in the queue now , If the element is 0, The head and tail are equal , The queue is empty ; If not 0, The head and tail are equal , The queue is full ;

// Sequential queue mainly understands two designs ：1. Why ring ;2. Why waste a space 

// How to deal with the full queue ：1. Fixed length , If the team is full, you will fail to join the team （ Simple processing , Unpractical ）： Consistent with books 
              // 2. Length is not fixed , When the team is full, the capacity will be expanded （ The implementation is a little more complicated ）


#define SIZE 10

typedef struct
{
    
	int* base;// Point to dynamic memory 
	int front;// Header pointer , Subscript of header element 
	int rear;// Pointer to a party , Subscripts that can currently be inserted into data （ The subscript of the last element at the end of the team ）
// int queuesize;// The total capacity of the queue , To achieve automatic capacity expansion, you must add this member 
}SqQueue,*PSqQueue;



// initialization 
void InitQueue(PSqQueue ps);

// Full sentence 
static bool IsFull(PSqQueue ps);


// Put data into the queue （ Joining operation ）
bool Push(PSqQueue ps, int val);

// Get the value of the header element , But don't delete 
bool GetTop(PSqQueue ps, int* rtval);//rtval: Output parameters 


// Get the value of the header element , And delete 
bool Pop(PSqQueue ps, int* rtval);

// Sentenced to empty 
bool IsEmpty(PSqQueue ps);

// Get the number of valid data in the queue 
int GetLength(PSqQueue ps);

// Clear all data 
void Clear(PSqQueue ps);
// The destruction 
void Destory(PSqQueue ps);

3 Chain queues

Improve one ：

Improvement 2 ：

Structure definition ：

typedef struct Node
{
    
	ELEM_TYPE data;// Data fields 
	struct Node* next;// Pointer to the domain 
}Node, * PNode;

// We redesign the structure of the head node 
typedef struct Head
{
    
	struct Node* front;// Always point to the first node 
	struct Node* rear;// Always point to the last node 
	//int length;// If you need to get the effective length of the queue frequently , You can add length
}Head, * PHead;

API Realization ：

// initialization 
void Init_lqueue(PHead pq)
{
    
	assert(pq != nullptr);
	if (NULL == pq)
		return;

	pq->front = NULL;
	pq->rear = NULL;
	//pq->front = pq->rear = NULL;
}

// The team 
bool Push(PHead pq, ELEM_TYPE val)
{
    
	//assert pq
	// Apply for a new node 
	Node* pnewnode = (PNode)malloc(sizeof(Node) * 1);
	assert(pnewnode != NULL);
	pnewnode->data = val;

	// Find the right place to insert   There is no need to look for   Because the head node stores the address of the tail node 

	// Insert   A question needs to be considered ： Is there any data in it when inserting 
	if (pq->front == NULL)// This is an empty queue 
	{
    
		pnewnode->next = NULL;//=pq->front =pq->rear
		pq->front = pnewnode;
		pq->rear = pnewnode;
	}
	else
	{
    
		pnewnode->next = pq->rear->next;// = NULL;
		pq->rear->next = pnewnode;
		pq->rear = pnewnode;
	}

	return true;
}

// Out of the team 
bool Pop(PHead pq, int* rtval)
{
    
	assert(pq != NULL && rtval != NULL);
	if (pq == NULL || rtval == NULL)
		return false;

	if (pq->front == NULL)
	{
    
		return false;
	}


	// Find the deleted location   Head deletion   So there is no need to find 

	// Delete   A question needs to be considered ： Is the deleted node the only remaining node 
	if (pq->front->next == NULL)// If it is true   Only one node exists 
	{
    
		Node* p = pq->front;
		*rtval = p->data;// Through the output parameters   Take the value out 
		free(p);
		p = NULL;

		pq->front = pq->rear = NULL;
	}
	else// The deleted node is definitely not the only one （ There's at least 2 Nodes ）
	{
    
		Node* p = pq->front;
		*rtval = p->data;// Through the output parameters   Take the value out 
		pq->front = p->next;
		free(p);
		p = NULL;
	}

	return true;
}

// Get the top element of the queue 
bool Top(PHead pq, int* rtval)
{
    
	assert(pq != NULL && rtval != NULL);
	if (pq == NULL || rtval == NULL)
		return false;

	if (pq->front == NULL)// Sentenced to empty  
	{
    
		return false;
	}

	*rtval = pq->front->data;
	return true;
}

// Get the number of its effective length 
int Get_length(PHead pq)
{
    
	//assert
	int count = 0;

	Node* p = pq->front;
	for (p; p != NULL; p = p->next)
	{
    
		count++;
	}

	return count;
}

// Sentenced to empty 
bool IsEmpty(PHead pq)
{
    
	return pq->front == NULL;
}

 Full sentence   You don't need a full sentence 
//bool IsFull(PHead pq);

// Empty 
void Clear(PHead pq)
{
    
	Destroy(pq);
}

// The destruction   Head deletion 
void Destroy(PHead pq)
{
    
	while (pq->front != NULL)
	{
    
		Node* p = pq->front;
		pq->front = p->next;
		free(p);
		p = NULL;
	}

	pq->front = pq->rear = NULL;
}

void Show(PHead pq)
{
    
	//assert

	Node* p = pq->front;
	for (p; p != NULL; p = p->next)
	{
    
		printf("%d ", p->data);
	}

	printf("\n");
}