Article source: blog.csdn.net/zqixiao_09/…

Yangzhizhen.iteye.com/blog/147234… \

Let me show you this picture for comparison and understanding:

 

A queue is a linear table that is limited to insert and delete operations at both ends. The end that allows storing operations is called the “tail” and the end that allows deleting operations is called the “head”. When there are no elements in a linear table, it is called an “empty queue”. Features: First in, first out (FIFO).

1. Sequential queue

**** To establish a sequential queue structure, you must statically allocate or dynamically apply for a contiguous piece of storage space and set two Pointers for management. One is front, which points to the header element. The other is the queue tail pointer, Rear, which points to where the next queue element is stored, as shown in the figure

Every time you insert an element at the end of the queue, rear increases by 1; Each time the header deletes an element, front increases by 1. As insert and delete operations progress, the number of queue elements changes, and the storage space occupied by the queue moves around the contiguous space allocated to the queue structure. When front=rear, there are no elements in the queue, it’s called an empty queue. When rear is outside the contiguous space that points to the allocated space, the queue cannot insert new elements, but there is usually a lot of free space that was once occupied by the out-of-queue element.

In practice, to make the queue space reusable, the queue is often used in a slightly modified way: whenever the rear pointer increases by 1 or the front pointer increases by 1 and exceeds the allocated queue space, it points to the starting position of the contiguous space. Rear %N and front%N are rear%N and front%N respectively. This is actually to think of the queue space as a ring space in which the storage units are recycled. Queues managed in this way are also called circular queues.

In a circular queue, there is front=rear when the queue is empty, and there is front=rear when all the queue space is full. To distinguish between the two cases, a circular queue can have at most MaxSize-1 queue elements. When there is only one empty storage unit left in the circular queue, the queue is full. So front=rear when the queue is empty, and front= (rear+1) %MaxSize when the queue is full.

Conclusion:

1, queue header pointer front, pointing to the position before the queue header element. That is to point to the reserved position;

2. Rear pointer, pointing to the position of the element at the end of the team;

Rear = (rear + 1) % N (maxsize);

Front = (front + 1) % N;

5, front == rear;

(rear + 1) % N == front, rear + 1 % N == front;

To distinguish empty lines from full lines, the number of full lines is one less than the number of array elements.

Here is the sequential queue operation:

A sequential queue is also a kind of sequential table. It has the same storage structure as a sequential table. It is defined by an array and uses a pointer to the head of the queue and a pointer to the tail of the queue represented by the table below the array to complete various operations:

[cpp]  view plain  copy

  1. #define N 64 // The data type of the data element in the queue
  2. typedef int data_t;  
  3. typedef struct  
  4. {  
  5. data_t data[N]; // Use arrays as storage space for queues
  6. int front,rear; // A pointer to the position of the head and the back of the team
  7. }sequeue_t;  

1. Create an empty queue

[cpp]  view plain  copy

  1. sequeue_t *CreateEmptySequeue()  
  2. {  
  3.     sequeue_t *queue;  
  4.     queue = (sequeue_t *)malloc(sizeof(sequeue_t));  
  5.     if (NULL == queue) return NULL;  
  6.       
  7.     queue->front = queue->rear = 0;  
  8.   
  9.     return queue;  
  10. }  

2. Destroy a queue

[cpp]  view plain  copy

  1. void DestroySequeue(sequeue_t *queue)  
  2. {  
  3. if (NULL ! = queue)
  4.     {  
  5.         free(queue);  
  6.     }  
  7. }  

3. Check whether a queue is empty

[cpp]  view plain  copy

  1. int EmptySequeue(sequeue_t *queue)  
  2. {  
  3.     if (NULL == queue)   
  4.         return -1;  
  5.   
  6. return (queue->front == queue->rear ? 1:0);
  7. }  

4. Check whether a queue is full

[cpp]  view plain  copy

  1. int FullSequeue(sequeue_t *queue)  
  2. {  
  3.     if (NULL == queue) return -1;  
  4.   
  5. return ((queue->rear + 1) % N == queue->front ? 1:0);
  6. }  

5. Empty a queue

[cpp]  view plain  copy

  1. void ClearSequeue(sequeue_t *queue)  
  2. {  
  3.     if (NULL == queue) return;  
  4.       
  5.     queue->front = queue->rear = 0;  
  6.   
  7.     return;  
  8. }  

6, team

[cpp]  view plain  copy

  1. int EnQueue(sequeue_t *queue, data_t x)  
  2. {  
  3.     if (NULL == queue) return – 1;  
  4.   
  5.     if (1 == FullSequeue(queue)) return -1; /* full */  
  6.   
  7.     queue->rear = (queue->rear + 1) % N;  
  8.     queue->data[queue->rear] = x;  
  9.   
  10.     return 0;  
  11. }  

7, out of the team

[cpp]  view plain  copy

  1. int DeQueue(sequeue_t *queue, data_t *x)  
  2. {  
  3.     if (NULL == queue) return -1;  
  4.   
  5.     if (1 == EmptySequeue(queue)) return -1; /* empty */  
  6.   
  7.     queue->front = (queue->front + 1) % N;  
  8.   
  9. if (NULL ! = x) {
  10.         *x = queue->data[queue->front];  
  11.     }  
  12.   
  13.     return 0;  
  14. }  

Queue of data structure (C implementation)

  • Blog category: 
  • C

Data structure queue implementation static queue based on array queue implementation

What is a queue

A queue is a first-in, first-out storage structure. In fact, to put it simply, the queue is the queue, with our daily life to the bank to withdraw money queue, queue for lunch in the truth is the same.

Queues can generally be divided into two types: (1) chain queues (implemented by linked lists). Static queues (implemented by arrays), static queues must always be circular queues. Since chained queues are similar to linked lists, we will only illustrate and practice circular queues here. Front,front refers to the first element of the queue. ②rear,rear points to the element next to the last valid element in the queue. The two basic operations of a queue are dequeueing and joining.

Second, queue structure

Here is the structure of a loop queue (implemented based on an array) :

    

3. Queue operations

Queue entry (queue entry of rear) ① Store the value in the position represented by rear. ② Rear = (rear+1)% Array length. ** queue out (head queue out) ** front = (front+1)% array length. If front and rear have the same value, the queue must be empty. Note: In a circular queue, there are n positions, usually n-1 value, empty 1 value in the circular queue, front and rear point to the values are not correlated, irregular. Front could be bigger than rear, it could be smaller than rear, it could be equal. Algorithm: ① add one more identification parameter. ② Use one less element, rear and front are right next to each other, and the queue is full. \

Fourth, the implementation of the queue

**** Concrete implementation of array-based loop queues

C code

  1. #include
  2. #include

    // include the malloc function
  3. / *
  4. * Loop queue, with array implementation
  5. * /
  6. // Queue structure definition
  7. typedef struct Queue  
  8. {  
  9. int * pBase; // For dynamic memory allocation,pBase holds the first address of the array
  10. int front; // point to the header
  11. int rear; // points to the next node of the last element
  12. } QUEUE;  
  13. // Function declaration
  14. void initQueue(QUEUE * pQueue); // Queue initialization function
  15. bool isEmpty(QUEUE * pQueue); // A function to determine whether the queue is empty
  16. bool isFull(QUEUE * pQueue); // A function to determine whether the queue is full
  17. bool enQueue(QUEUE * pQueue, int value); // Join the queue function
  18. bool outQueue(QUEUE * pQueue, int * pValue); // The queue function holds the queue element
  19. void traverseQueue(QUEUE * pQueue); // A function to traverse the queue
  20. / *
  21. * the main program
  22. * /
  23. int main(void)  
  24. {  
  25. int value; // Used to save the queue element
  26. // Create a queue object
  27.     QUEUE queue;  
  28. // Call the function that initializes the queue
  29.     initQueue(&queue);  
  30. // Call the queue function
  31.     enQueue(&queue, 1);  
  32.     enQueue(&queue, 2);  
  33.     enQueue(&queue, 3);  
  34.     enQueue(&queue, 4);  
  35.     enQueue(&queue, 5);  
  36.     enQueue(&queue, 6);  
  37.     enQueue(&queue, 7);  
  38.     enQueue(&queue, 8);  
  39. // Call the function that traverses the queue
  40.     traverseQueue(&queue);  
  41. // Call the queue function
  42.     if(outQueue(&queue, &value))  
  43.     {  
  44. Printf (” queue once, element: %d\n”, value);
  45.     }  
  46.     traverseQueue(&queue);  
  47.     if(outQueue(&queue, &value))  
  48.     {  
  49. Printf (” queue once, element: %d\n”, value);
  50.     }  
  51.     traverseQueue(&queue);  
  52.     getchar();  
  53.     return 0;  
  54. }  
  55. / *
  56. * Initializes the implementation of the function
  57. * /
  58. void initQueue(QUEUE * pQueue)  
  59. {  
  60. // Allocate memory
  61. pQueue->pBase = (int *)malloc(sizeof(int) * 6); // Allocate the space occupied by 6 ints
  62. pQueue->front = 0; // The front and rear values are 0 during initialization
  63.     pQueue->rear = 0;  
  64.     return;  
  65. }  
  66. / *
  67. * Implementation of the queue function
  68. * /
  69. bool enQueue(QUEUE * pQueue, int value)  
  70. {  
  71.     if(isFull(pQueue))  
  72.     {  
  73. Printf (” Queue is full, can’t insert any more elements! \n”);
  74.         return false;  
  75.     }  
  76.     else  
  77.     {  
  78. // Add a new element to the queue
  79.         pQueue->pBase[pQueue->rear] = value;  
  80. // Assign the new appropriate value to rear
  81.         pQueue->rear = (pQueue->rear+1) % 6;  
  82.         return true;  
  83.     }  
  84. }  
  85. / *
  86. * The implementation of queue function
  87. * /
  88. bool outQueue(QUEUE * pQueue, int * pValue)  
  89. {  
  90. // If the queue is empty, return false
  91.     if(isEmpty(pQueue))  
  92.     {  
  93. Printf (” Queue empty, queue failed! \n”);
  94.         return false;  
  95.     }  
  96.     else  
  97.     {  
  98. *pValue = pQueue->pBase[pQueue->front]; // First in, first out
  99. pQueue->front = (pQueue->front+1) % 6; // Move to the next position
  100.         return true;  
  101.     }  
  102. }  
  103. / *
  104. * Function implementation of traversal queue
  105. * /
  106. void traverseQueue(QUEUE * pQueue)  
  107. {  
  108. int i = pQueue->front; // Start from the beginning
  109. Printf (” traversal queue: \n”);
  110. while(i ! = pQueue->rear) // Loop if no rear position is reached
  111.     {  
  112.         printf(“%d  “, pQueue->pBase[i]);  
  113. i = (i+1) % 6; // Move to the next position
  114.     }     
  115.     printf(“\n”);  
  116.     return;  
  117. }  
  118. / *
  119. * The implementation of a function to determine whether the queue is full
  120. * /
  121. bool isFull(QUEUE * pQueue)  
  122. {  
  123. If ((pQueue->rear+1) % 6 == pQueue->front
  124.         return true;  
  125.     else  
  126.         return false;  
  127. }  
  128. / *
  129. * Determines whether the queue is an implementation of an empty function
  130. * /
  131. bool isEmpty(QUEUE * pQueue)  
  132. {  
  133.     if(pQueue->front == pQueue->rear)  
  134.         return true;  
  135.     else  
  136.         return false;  
  137. }</span>  

5. The application of queues

When we go to get a meal, we always have to queue up. Queuing is related to time. If there are many people in front of us, it takes us a long time to get a meal. It’s safe to say that any time related operation will basically involve queues.

Six, the concluding

One final disclaimer: The attached project was built in Visual Studio 2010.

\