C language data structures to determine if a loop list is empty or full

C language data structures to determine if a cyclic list is empty or full

Preface:

When is the queue empty? When is it full?

Since the tail pointer is chasing the head pointer forward when entering the team, and the head pointer is chasing the tail pointer forward when leaving the team, the head pointer is equal to the tail pointer when the team is empty and full. Therefore, we cannot tell whether the queue is "empty" or "full" by front=rear.

Note: the first to enter is' head ', the last to enter is' tail '.

There are at least three ways to solve this problem:

Its 1 is to set another Boolean variable to match the empty and full of the queue;

2 is the space with one less element. Before joining the team, it is agreed to test whether the tail pointer is equal to the head pointer after adding 1 in a circular sense. If it is equal, the team will be considered full (note: the unit referred to by rear is always empty);

Its 3 is to use a counter to record the total number of elements in the queue (actually the queue length).

The first method is not implemented, but the second and third methods are:

1. Use one less element space, and agree that "queue head pointer front is at the next position of queue tail pointer rear" shall be used as the symbol of queue "full" status. That is:

Queue time: front=rear
When the queue is full: (rear+1)%maxsize=front
front points to the element at the head of the team, rear points to the next element at the end of the team.

 
///////////////////////////////////////// 
//  
// author: kangquan2008@csdn 
// 
///////////////////////////////////////// 
#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 
 
#define QUEUE_SIZE 10 
#define EN_QUEUE 1 
#define DE_QUEUE 2 
#define EXIT   3 
 
typedef int  Item; 
typedef struct QUEUE{ 
 
  Item * item; 
  int front; 
  int tear; 
 
}Queue; 
 
int init_queue(Queue * queue) 
{ 
  queue->item = malloc(QUEUE_SIZE * sizeof(Item)); 
  if(!queue->item) 
  { 
    printf("%s\n","Alloc failed,not memory enough"); 
    exit(EXIT_FAILURE); 
  } 
 
  queue->front = queue->tear = 0; 
 
  return 1; 
} 
 
int en_queue(Queue * queue, Item item) 
{ 
  if((queue->tear+1) % QUEUE_SIZE == queue->front) 
  { 
    printf("%s\n","The queue is full"); 
    return -1; 
  } 
 
  queue->item[queue->tear] = item; 
  queue->tear = (queue->tear + 1) % QUEUE_SIZE; 
 
  return 1; 
} 
 
int de_queue(Queue * queue, Item * item) 
{ 
  if(queue->front == queue->tear) 
  { 
    printf("%s\n","The queue is empty"); 
    return -1; 
  } 
 
  (*item) = queue->item[queue->front]; 
  queue->front = (queue->front + 1) % QUEUE_SIZE; 
 
  return 1; 
} 
 
int destroy_queue(Queue * queue) 
{ free(queue->item); 
} 
 
int main() 
{ 
  Queue que; 
  init_queue(&que); 
  int elem; 
  bool flag = true; 
  while(flag) 
  { 
    int choice; 
    printf("1 for en_queue,2 for de_queue,3 for exit\r\nplease input:"); 
    scanf("%d",&choice); 
 
    switch((choice)) 
    { 
      case EN_QUEUE: 
        printf("input a num:"); 
        scanf("%d",&elem); 
        en_queue(&que,elem); 
        break; 
      case DE_QUEUE: 
        if(de_queue(&que,&elem) == 1) 
          printf("front item is:%d\n",elem); 
        break; 
      case EXIT: 
        flag = false; 
        break; 
      default: 
        printf("error input\n"); 
        break; 
    } 
  } 
 
  destroy_queue(&que); 
  return 0; 
} 

2. Example code:

#include <stdio.h> 
#include <assert.h> 
#define QueueSize 100 
typedef char datatype; 
// The data elements of a queue  
typedef struct 
{ 
   int front; 
   int rear; 
   int count; // A counter that records the number of elements  
   datatype data[QueueSize]; // The data content  
}cirqueue; 
// Empty team  
void InitQueue(cirqueue *q) 
{ 
   q->front = q->rear = 0; 
   q->count = 0; 
} 

// Judge team full  
int QueueFull(cirqueue *q) 
{ 
   return (q->count == QueueSize); 
} 

// Judge team empty  
int QueueEmpty(cirqueue *q) 
{ 
   return (q->count == 0); 
} 

// The team  
void EnQueue(cirqueue *q, datatype x) 
{ 
   assert(QueueFull(q) == 0); //q Full, terminate program  
 
   q->count++; 
   q->data[q->rear] = x; 
   q->rear = (q->rear + 1)%QueueSize; // Circular queue design to prevent memory waste  
} 

// Out of the team  
datatype DeQueue(cirqueue *q) 
{ 
   datatype temp; 
 
   assert(QueueEmpty(q) == 0);//q Null, terminates the program and prints an error message  
 
   temp = q->data[q->front]; 
   q->count--; 
   q->front = (q->front + 1)%QueueSize; 
   return temp; 
} 

If you have any questions, please leave a message or come to the site community to exchange discussion, thank you for reading, hope to help you, thank you for your support of the site!