循环队列的C语言实现

八月 01, 2021 2865

本文实现了循环队列的C语言实现。主要功能入队与出队。

1.代码部分

循环队列结构体的定义

循环队列的结构

1
2
3
4
5
typedef struct {
	int* base;
	int front;  // Integer front points at the first position of existed elements.
	int rear;  // Integer rear points at the empty position to be inserted.
}Queue;

初始化函数，接受一个分配好空间的循环队列，对内部进行初始化。

1
2
3
4
5
6
7
Queue* Initial(Queue* que)
{
	que->front = que->rear = 0;
	que->base = (int*)malloc(MAXSIZE * sizeof(int));
	if (!que->base) { printf("ERROR!"); }
	return que;
}

入队、出队函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void EnQueue(Queue* que)
{
	int e;
	// The method of using less than one spatial element is used to distinguish empty queues from full queues.
	if ((que->rear + 1) % MAXSIZE == que->front) { printf("Queue is full. Fail to insert.\n"); }
	else {
		printf("Input the number you want to add:\n");
		scanf_s("%d", &e);
		setvbuf(stdin, NULL, _IOFBF, 512);
		que->base[que->rear] = e;
		que->rear = (que->rear + 1) % MAXSIZE;  // Make queue a circle.
		printf("%d is added in.\n", e);
	}
}


void DeQueue(Queue* que)
{
	int e;
	if (que->front == que->rear) { printf("Queue is empty.\n"); }
	e = que->base[que->front];
	que->front = (que->front + 1) % MAXSIZE;
	printf("Number %d is deleted.\n", e);
}

经main函数验证正确。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int main() 
{
	Queue* sq = (Queue*)malloc(sizeof(Queue));
	sq = Initial(sq);
	int i;
	/*
	When EnQueue for the sixth time, it will be prompted that the queue is full, 
	indicating that the method of using less than one spatial element to distinguish 
	between empty queue and full queue is successful.
	*/
	for (i = 1; i <= 5; i++)
	{
		EnQueue(sq);
	}
	DeQueue(sq);
	DeQueue(sq);
	DeQueue(sq);
	EnQueue(sq);
	EnQueue(sq);
	DeQueue(sq);
	DeQueue(sq);
	EnQueue(sq);
	DeQueue(sq);
	EnQueue(sq);
	EnQueue(sq);
	DeQueue(sq);
	DeQueue(sq);
	return 0;
}

2.反思与改进

  1. 失败的show函数。试图通过一个函数按顺序展现队列的元素，但是由于空缺位置的存在与其位置的不确定性，未能实现相关功能。期望有时间的话进一步改进算法，也欢迎大佬们给出建议。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    /*  An unsuccessful try. Don't know how to show the queue correctly.
    void ShowQueue(Queue* que)
    {
    	int i, j, k;
    	k = QueueLength(que);
    	if (que->front < que->rear) 
    	{
    		for (i = que->front; i <= k; i++)
    		{
    			printf("Order: %d.\n", que->base[i]);
    		}
    	}
    	else if(que->front > que->rear)
    	{
    		for (i = que->front; i <= MAXSIZE; i++)
    		{
    			printf("Order:%d.\n", que->base[i]);
    		}
    		for (j = 0; j < que->rear; j++)
    		{
    			printf("Order:%d.\n", que->base[j]);
    		}
    	}
    	else {
    		printf("Empty.\n");
    	}
    }
    */

    1. 什么时候分配内存，什么时候直接定义：

      当初次使用结构体或者在函数内部需要对结构体内部成员进行赋值时要现malloc，当这个新结构体只是用来承载已存在的结构体的内容时（如直接指向同一内容：p = q）不需要malloc

查看评论