C 中的排序基本上是存储和操纵数据元素的线性数据结构,它遵循 **First In First Out (FIFO)**的顺序。
在排列中,进入数组的第一个元素是从数组中删除的第一个元素。
举个例子,让我们来考虑一间公交车票预订站的场景。在这里,遵循C编程排队的时尚。门票以 **first-come-first-serve 基础分发,即第一个进入的门票是第一个与门票一起服务的门票。
**两端都有排队,一个端是用于输入数据,另一个端是用于删除数据。
排队可以与任何编程语言(如C、Java、Python等)实现。
与 C 中的队列相关的操作
排列是一个 **抽象数据结构 ** 提供了以下操作来操纵数据元素:
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
队列数据结构的运作
排队遵循First-In-First-Out模式,第一个元素是从元素列表中提取的第一个元素。
前方和后方指示器保持排列中的第一个和最后一个元素的记录
- 首先,我们需要通过设置
前方 = -1和后方 = -1来初始化排列,以便将元素(enqueue)插入排列中,我们需要检查排列的值是否已经满了,即 检查排列的条件。如果排列没有满,我们需要增加排列的值为1,并将元素放置在后排列变量的位置。当我们把第一个元素插入排列中时,我们需要将前方的值设置为 0. 以便从排列中删除元素( dequeue**),我们需要检查排列是否已经空了。 **
C 中的 Queue 应用
在 C 中的排列可以使用 Arrays、Lists、Structures 等实现,下面我们使用 Arrays in C实现排列。
** 例子:**
1#include <stdio.h>
2# define SIZE 100
3void enqueue();
4void dequeue();
5void show();
6int inp_arr[SIZE];
7int Rear = - 1;
8int Front = - 1;
9main()
10{
11 int ch;
12 while (1)
13 {
14 printf("1.Enqueue Operation\n");
15 printf("2.Dequeue Operation\n");
16 printf("3.Display the Queue\n");
17 printf("4.Exit\n");
18 printf("Enter your choice of operations : ");
19 scanf("%d", &ch);
20 switch (ch)
21 {
22 case 1:
23 enqueue();
24 break;
25 case 2:
26 dequeue();
27 break;
28 case 3:
29 show();
30 break;
31 case 4:
32 exit(0);
33 default:
34 printf("Incorrect choice \n");
35 }
36 }
37}
38
39void enqueue()
40{
41 int insert_item;
42 if (Rear == SIZE - 1)
43 printf("Overflow \n");
44 else
45 {
46 if (Front == - 1)
47
48 Front = 0;
49 printf("Element to be inserted in the Queue\n : ");
50 scanf("%d", &insert_item);
51 Rear = Rear + 1;
52 inp_arr[Rear] = insert_item;
53 }
54}
55
56void dequeue()
57{
58 if (Front == - 1 || Front > Rear)
59 {
60 printf("Underflow \n");
61 return ;
62 }
63 else
64 {
65 printf("Element deleted from the Queue: %d\n", inp_arr[Front]);
66 Front = Front + 1;
67 }
68}
69
70void show()
71{
72
73 if (Front == - 1)
74 printf("Empty Queue \n");
75 else
76 {
77 printf("Queue: \n");
78 for (int i = Front; i <= Rear; i++)
79 printf("%d ", inp_arr[i]);
80 printf("\n");
81 }
82}
出发点:**
11.Enqueue Operation
22.Dequeue Operation
33.Display the Queue
44.Exit
5Enter your choice of operations : 1
6Element to be inserted in the Queue: 10
7
81.Enqueue Operation
92.Dequeue Operation
103.Display the Queue
114.Exit
12Enter your choice of operations : 1
13Element to be inserted in the Queue: 20
14
151.Enqueue Operation
162.Dequeue Operation
173.Display the Queue
184.Exit
19Enter your choice of operations : 3
20Queue:
2110 20
22
231.Enqueue Operation
242.Dequeue Operation
253.Display the Queue
264.Exit
27Enter your choice of operations : 2
28Element deleted from the Queue: 10
29
301.Enqueue Operation
312.Dequeue Operation
323.Display the Queue
334.Exit
34Enter your choice of operations: 3
35Queue:
3620
使用 Stacks 执行队列
Stack Data Structure可用于执行队列的操作. 我们需要 两个队列来执行队列。
可以使用 Stacks 以下列方式实现队列:
- 使结尾操作昂贵
- 使结尾操作昂贵
方法1:使 enqueue 操作昂贵
假设有两个堆栈:S1和S2来执行使用相同的队列操作。
- 如果 S1 不是空的,请将所有元素推到 Stack 2(S2)
- 为了执行 enqueue 操作,我们将假定
x是要输入队列的元素. 我们将把x推回 Stack S1 以便它出现在顶部 - 然后,将所有元素推回 Stack S1
** 注意: ** 查询操作的时间复杂性将是 ** O(n)**。
- 为了执行 ** dequeue 操作,我们需要从 S1 堆栈中打开一个项目,因为现在第一个插入的元素位于 S1 的顶部,而不是在底部。
** 注:** 解码操作的时间复杂性将是 O(1)。
如果您使用 Stack 分析 Enqueue 和 Dequeue 操作的时间复杂性,您会发现 Enqueue 操作比 Dequeue 操作更昂贵。
因此,如上所述,我们使第一个输入或最古老的输入元素留在S1堆栈的顶部,以便在调用Dequeue操作时被删除。
方法2:使 Dequeue 操作昂贵
让我们再次假设有两个堆栈:S1和S2来执行使用相同的队列操作。
- 为了实现 ** enqueue 操作**,我们将新输入的元素插入 Stack S1 的顶部,因此使用 Stacks 的 Enqueue 操作的时间复杂性变为 O(1).
- 对于执行 ** dequeue 操作**,它会检查 Stack S1 和 S2 的 Underflow 状态。
Queue 数据结构的应用
- CPU 安排
- 磁盘安排
- 文件 IO 等处理器之间的无同步数据传输
- 宽度第一搜索算法(BFS)
结论
在本文中,我们了解了队列数据结构的运作,并对使用堆栈数据结构的队列实施进行了阴影。