创建队列 c语言

A queue in C is basically a linear data structure to store and manipulate the data elements. It follows the order of First In First Out (FIFO).

C语言中的队列基本上是用于存储和操作数据元素的linear data structure 。 它遵循先进先出（FIFO）的顺序。

In queues, the first element entered into the array is the first element to be removed from the array.

在队列中，输入到数组中的第一个元素是要从数组中删除的第一个元素。

For example, let’s consider the scenario of a bus-ticket booking stall. Here, the fashion of a C programming queue is followed. The tickets are distributed on the first-come-first-serve basis i.e. the first one to enter is the first one to be served with the tickets.

例如，让我们考虑公交车票预订摊位的情况。 在此，遵循C编程队列的方式。 门票将按照先到先得的原则分配，即，第一个进入的门票将是第一个与门票一起出售的门票。

A queue is open at both ends. One end is provided for the insertion of data and the other end for the deletion of data.

两端都有一个队列 。 提供一端用于插入数据，另一端用于删除数据。

A queue can be implemented with any programming language such as C, Java, Python, etc.

可以使用任何编程语言（例如C，Java，Python等）来实现队列。

---

---

与C中的队列相关联的操作 (Operations Associated with a Queue in C )

A queue being an Abstract Data Structure provides the following operations for manipulation on the data elements:

作为抽象数据结构的队列为数据元素提供了以下操作：

• isEmpty(): To check if the queue is empty
  isEmpty() ：检查队列是否为空
• isFull(): To check whether the queue is full or not
  isFull() ：检查队列是否已满
• dequeue(): Removes the element from the frontal side of the queue
  dequeue() ：从队列的正面移除元素
• enqueue(): It inserts elements to the end of the queue
  enqueue() ：将元素插入队列的末尾
• Front: Pointer element responsible for fetching the first element from the queue
  Front ：负责从队列中获取第一个元素的指针元素
• Rear: Pointer element responsible for fetching the last element from the queue
  Rear ：负责从队列中获取最后一个元素的指针元素

---

---

队列数据结构的工作 (Working of Queue Data Structure )

Queue follows the First-In-First-Out pattern. The first element is the first to be pulled out from the list of elements.

队列遵循先进先出模式。 第一个元素是第一个从元素列表中拉出的元素。

• Front and Rear pointers keep the record of the first and last element in the queue.
  Front和Rear指针保持在队列中的第一个和最后一个元素的记录。
• At first, we need to initialize the queue by setting Front = -1 and Rear = -1
  首先，我们需要通过设置Front = -1和Rear = -1来初始化队列。
• In order to insert the element (enqueue), we need to check whether the queue is already full i.e. check the condition for Overflow. If the queue is not full, we’ll have to increment the value of the Rear index by 1 and place the element at the position of the Rear pointer variable. When we get to insert the first element in the queue, we need to set the value of Front to 0.
  为了插入元素（ enqueue ），我们需要检查队列是否已满，即检查Overflow的条件 。 如果队列未满，则必须将Rear索引的值增加1并将元素放置在Rear指针变量的位置。 当我们将第一个元素插入队列时，我们需要将Front的值设置为0。
• In order to remove the element (dequeue) from the queue, we need to check whether the queue is already empty i.e. check the condition for Underflow. If the queue is not empty, we’ll have to remove and return the element at the position of the Front pointer, and then increment the Front index value by 1. When we get to remove the last element from the queue, we will have to set the values of the Front and Rear index to -1.
  为了从队列中删除元素（ 出队 ），我们需要检查队列是否已经为空，即检查Underflow的条件 。 如果队列不为空，则必须删除并返回Front指针位置的元素，然后将Front索引值增加1。当我们从队列中删除最后一个元素时 ，我们将将前和后索引的值设置为-1。

---

---

队列在C中的实现 (Implementation of Queue in C)

Queues in C can be implemented using Arrays, Lists, Structures, etc. Below here we have implemented queues using .

C中的队列可以使用数组，列表，结构等实现。下面，我们使用实现队列。

Example:

例：

#include 
    
     # define SIZE 100void enqueue();void dequeue();void show();int inp_arr[SIZE];int Rear = - 1;int Front = - 1;main(){    int ch;    while (1)    {        printf("1.Enqueue Operation\n");        printf("2.Dequeue Operation\n");        printf("3.Display the Queue\n");        printf("4.Exit\n");        printf("Enter your choice of operations : ");        scanf("%d", &ch);        switch (ch)        {            case 1:            enqueue();            break;            case 2:            dequeue();            break;            case 3:            show();            break;            case 4:            exit(0);            default:            printf("Incorrect choice \n");        }     } }  void enqueue(){    int insert_item;    if (Rear == SIZE - 1)       printf("Overflow \n");    else    {        if (Front == - 1)              Front = 0;        printf("Element to be inserted in the Queue\n : ");        scanf("%d", &insert_item);        Rear = Rear + 1;        inp_arr[Rear] = insert_item;    }}  void dequeue(){    if (Front == - 1 || Front > Rear)    {        printf("Underflow \n");        return ;    }    else    {        printf("Element deleted from the Queue: %d\n", inp_arr[Front]);        Front = Front + 1;    }}  void show(){        if (Front == - 1)        printf("Empty Queue \n");    else    {        printf("Queue: \n");        for (int i = Front; i <= Rear; i++)            printf("%d ", inp_arr[i]);        printf("\n");    }}
    

Output:

输出：

1.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations : 1Element to be inserted in the Queue: 101.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations : 1Element to be inserted in the Queue: 201.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations : 3Queue: 10 20 1.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations : 2Element deleted from the Queue: 101.Enqueue Operation2.Dequeue Operation3.Display the Queue4.ExitEnter your choice of operations: 3Queue: 20

---

---

使用堆栈实现队列 (Implementation of Queue using Stacks)

can be used to implement the operations of the queue. We’ll need two stacks to implement a queue using them. Before you work through the examples below, make sure you understand the functioning of stacks very well.

可用于实现队列的操作。 我们将需要两个堆栈以使用它们来实现队列 。 在完成下面的示例之前，请确保您非常了解堆栈的功能。

A queue can be implemented using Stacks by either of the following ways:

可以通过以下两种方式之一使用Stacks实现队列：

• Making the enqueue operation costly
  使入队操作成本高昂
• Making the dequeue operation costly
  使出队操作昂贵

方法1：使入队操作变得昂贵 (Method 1: Making the enqueue Operation Costly)

Let us assume two stacks: S1 and S2 to implement queue operations using the same.

让我们假设两个堆栈：S1和S2，以使用它们来实现队列操作。

• If S1 is not empty, push all elements to stack 2 (S2)
  如果S1不为空，则将所有元素推入堆栈2（S2）
• In order to perform the enqueue operation, we will assume ‘x’ to be the element to be entered into the queue. We will push ‘x’ back to Stack S1 so it comes up on the top.
  为了执行入队操作 ，我们将假定“ x”为要输入队列的元素。 我们将'x'推回堆栈S1，使其出现在顶部。
• Further, push all the elements of stack S2 back to Stack S1
  此外，将堆栈S2的所有元素推回堆栈S1

Note: The time complexity of the enqueue operation would be O(n).

注意：入队操作的时间复杂度为O（n） 。

• In order to perform dequeue operation, we’ll need to pop an item from the Stack S1 since now the first inserted element is on the top in S1 instead of being at the bottom.
  为了执行出队操作 ，我们需要从堆栈S1中弹出一个项目，因为现在第一个插入的元素在S1中位于顶部，而不是位于底部。

Note: The time complexity of the dequeue operation would be O(1).

注意：出队操作的时间复杂度为O（1） 。

If you analyze the time complexities of the Enqueue and Dequeue operations using Stack, you’ll find out that the Enqueue operation is much costlier than the Dequeue operation.

如果使用堆栈分析Enqueue和Dequeue操作的时间复杂度，您会发现Enqueue操作比Dequeue操作要昂贵得多。

Thus, as mentioned above, we make the first entered or the oldest entered element to remain at the top of Stack S1 so that it gets removed when the Dequeue operation is invoked.

因此，如上所述，我们使第一个输入或最早输入的元素保留在堆栈S1的顶部，以便在调用出队操作时将其删除。

---

---

方法2：使出队操作变得昂贵 (Method 2: Making the Dequeue operation costly)

Let us again assume two Stacks: S1 and S2 to implement queue operations using the same.

让我们再次假设两个堆栈：S1和S2，使用它们来实现队列操作。

• In order to implement enqueue operation, we insert the newly entered element at the top of Stack S1. Thus, the time complexity of the Enqueue operation using Stacks becomes O(1).
  为了实现入队操作 ，我们将新输入的元素插入堆栈S1的顶部。 因此，使用堆栈的入队操作的时间复杂度变为O（1）。
• For the implementation of dequeue operation, it checks for the Underflow condition of Stack S1 and S2. If both the Stacks stands out to be empty, an error would be raised.
  为了实现出队操作 ，它检查堆栈S1和S2的下溢条件。 如果两个堆栈都突出显示为空，则会引发错误。
• If the Stack S2 is empty and S1 is not empty, then all the elements from Stack S1 are moved to Stack S2 and the top element of Stack S2 is popped out and returned out of the Dequeue operation.
  如果堆栈S2为空且S1不为空，则将堆栈S1中的所有元素移至堆栈S2，并弹出堆栈S2的顶部元素，并将其从出队操作中移出。
• Thus, the time complexity of the dequeue operation using Stacks becomes O(n).
  因此， 使用堆栈的出队操作的时间复杂度变为O（n） 。

---

---

队列数据结构的应用 (Applications of Queue Data Structure)

• CPU Scheduling
  CPU调度
• Disk Scheduling
  磁盘调度
• Asynchronous data transfer between processors such as File IO, etc.
  处理器之间的异步数据传输，例如文件IO等。
• Breadth-First Search Algorithm (BFS)
  广度优先搜索算法（BFS）

---

---

结论 (Conclusion)

In this article, we have understood the working of queue data structure and have also shadowed over the implementation of queues using stack data structure.

在本文中，我们了解了队列数据结构的工作原理，并且对使用堆栈数据结构的队列实现也有所了解。

---

---

参考资料 (References)

翻译自:

创建队列 c语言