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
- #define N 64 // The data type of the data element in the queue
- typedef int data_t;
- typedef struct
- {
- data_t data[N]; // Use arrays as storage space for queues
- int front,rear; // A pointer to the position of the head and the back of the team
- }sequeue_t;
1. Create an empty queue
[cpp] view plain copy
- sequeue_t *CreateEmptySequeue()
- {
- sequeue_t *queue;
- queue = (sequeue_t *)malloc(sizeof(sequeue_t));
- if (NULL == queue) return NULL;
- queue->front = queue->rear = 0;
- return queue;
- }
2. Destroy a queue
[cpp] view plain copy
- void DestroySequeue(sequeue_t *queue)
- {
- if (NULL ! = queue)
- {
- free(queue);
- }
- }
3. Check whether a queue is empty
[cpp] view plain copy
- int EmptySequeue(sequeue_t *queue)
- {
- if (NULL == queue)
- return -1;
- return (queue->front == queue->rear ? 1:0);
- }
4. Check whether a queue is full
[cpp] view plain copy
- int FullSequeue(sequeue_t *queue)
- {
- if (NULL == queue) return -1;
- return ((queue->rear + 1) % N == queue->front ? 1:0);
- }
5. Empty a queue
[cpp] view plain copy
- void ClearSequeue(sequeue_t *queue)
- {
- if (NULL == queue) return;
- queue->front = queue->rear = 0;
- return;
- }
6, team
[cpp] view plain copy
- int EnQueue(sequeue_t *queue, data_t x)
- {
- if (NULL == queue) return – 1;
- if (1 == FullSequeue(queue)) return -1; /* full */
- queue->rear = (queue->rear + 1) % N;
- queue->data[queue->rear] = x;
- return 0;
- }
7, out of the team
[cpp] view plain copy
- int DeQueue(sequeue_t *queue, data_t *x)
- {
- if (NULL == queue) return -1;
- if (1 == EmptySequeue(queue)) return -1; /* empty */
- queue->front = (queue->front + 1) % N;
- if (NULL ! = x) {
- *x = queue->data[queue->front];
- }
- return 0;
- }
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
- #include
- #include
// include the malloc function
- / *
- * Loop queue, with array implementation
- * /
- // Queue structure definition
- typedef struct Queue
- {
- int * pBase; // For dynamic memory allocation,pBase holds the first address of the array
- int front; // point to the header
- int rear; // points to the next node of the last element
- } QUEUE;
- // Function declaration
- void initQueue(QUEUE * pQueue); // Queue initialization function
- bool isEmpty(QUEUE * pQueue); // A function to determine whether the queue is empty
- bool isFull(QUEUE * pQueue); // A function to determine whether the queue is full
- bool enQueue(QUEUE * pQueue, int value); // Join the queue function
- bool outQueue(QUEUE * pQueue, int * pValue); // The queue function holds the queue element
- void traverseQueue(QUEUE * pQueue); // A function to traverse the queue
- / *
- * the main program
- * /
- int main(void)
- {
- int value; // Used to save the queue element
- // Create a queue object
- QUEUE queue;
- // Call the function that initializes the queue
- initQueue(&queue);
- // Call the queue function
- enQueue(&queue, 1);
- enQueue(&queue, 2);
- enQueue(&queue, 3);
- enQueue(&queue, 4);
- enQueue(&queue, 5);
- enQueue(&queue, 6);
- enQueue(&queue, 7);
- enQueue(&queue, 8);
- // Call the function that traverses the queue
- traverseQueue(&queue);
- // Call the queue function
- if(outQueue(&queue, &value))
- {
- Printf (” queue once, element: %d\n”, value);
- }
- traverseQueue(&queue);
- if(outQueue(&queue, &value))
- {
- Printf (” queue once, element: %d\n”, value);
- }
- traverseQueue(&queue);
- getchar();
- return 0;
- }
- / *
- * Initializes the implementation of the function
- * /
- void initQueue(QUEUE * pQueue)
- {
- // Allocate memory
- pQueue->pBase = (int *)malloc(sizeof(int) * 6); // Allocate the space occupied by 6 ints
- pQueue->front = 0; // The front and rear values are 0 during initialization
- pQueue->rear = 0;
- return;
- }
- / *
- * Implementation of the queue function
- * /
- bool enQueue(QUEUE * pQueue, int value)
- {
- if(isFull(pQueue))
- {
- Printf (” Queue is full, can’t insert any more elements! \n”);
- return false;
- }
- else
- {
- // Add a new element to the queue
- pQueue->pBase[pQueue->rear] = value;
- // Assign the new appropriate value to rear
- pQueue->rear = (pQueue->rear+1) % 6;
- return true;
- }
- }
- / *
- * The implementation of queue function
- * /
- bool outQueue(QUEUE * pQueue, int * pValue)
- {
- // If the queue is empty, return false
- if(isEmpty(pQueue))
- {
- Printf (” Queue empty, queue failed! \n”);
- return false;
- }
- else
- {
- *pValue = pQueue->pBase[pQueue->front]; // First in, first out
- pQueue->front = (pQueue->front+1) % 6; // Move to the next position
- return true;
- }
- }
- / *
- * Function implementation of traversal queue
- * /
- void traverseQueue(QUEUE * pQueue)
- {
- int i = pQueue->front; // Start from the beginning
- Printf (” traversal queue: \n”);
- while(i ! = pQueue->rear) // Loop if no rear position is reached
- {
- printf(“%d “, pQueue->pBase[i]);
- i = (i+1) % 6; // Move to the next position
- }
- printf(“\n”);
- return;
- }
- / *
- * The implementation of a function to determine whether the queue is full
- * /
- bool isFull(QUEUE * pQueue)
- {
- If ((pQueue->rear+1) % 6 == pQueue->front
- return true;
- else
- return false;
- }
- / *
- * Determines whether the queue is an implementation of an empty function
- * /
- bool isEmpty(QUEUE * pQueue)
- {
- if(pQueue->front == pQueue->rear)
- return true;
- else
- return false;
- }</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.
\