C语言中的队列基本上是一种用于存储和处理数据元素的"线性数据结构"。
它遵循先进先出(FIFO)的顺序。

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

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

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

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

与C中的队列相关联的操作

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

• isEmpty()：检查队列是否为空
• isFull()：检查队列是否已满
• dequeue()：从队列的正面移除元素
• enqueue()：将元素插入队列的末尾
• Front：指针元素，负责从队列中获取第一个元素
• 后方：指针元素，负责从队列中获取最后一个元素

队列数据结构的工作

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

• "前"和"后"指针保留队列中第一个和最后一个元素的记录。

• 首先，我们需要通过设置" Front = -1"和" Rear = -1"来初始化队列。

• 为了插入元素(入队)，我们需要检查队列是否已满，即检查溢出条件。
  如果队列未满，则必须将后方索引的值增加1，然后将元素放置在后方指针变量的位置。
  当我们将第一个元素插入队列时，我们需要将Front的值设置为0。

• 为了从队列中删除元素(出队)，我们需要检查队列是否已为空，即检查下溢条件。
  如果队列不为空，则必须删除并返回Front指针位置的元素，然后将Front索引值增加1。
  当我们从队列中删除最后一个元素时，我们将将前和后索引的值设置为-1。

队列在C中的实现

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

例：

#include <stdio.h>
# define SIZE 100
void 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");
  }
} 

输出：

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 1
Element to be inserted in the Queue: 20

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 3
Queue: 
10 20 

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations : 2
Element deleted from the Queue: 10

1.Enqueue Operation
2.Dequeue Operation
3.Display the Queue
4.Exit
Enter your choice of operations: 3
Queue: 
20 

使用堆栈实现队列

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

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

• 使入队操作成本高昂
• 使出队操作成本高昂

方法1：使入队操作变得昂贵

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

• 如果S1不为空，则将所有元素推入堆栈2(S2)

• 为了执行入队操作，我们假设" x"是要输入队列的元素。
  我们将" x"推回堆栈S1，使其出现在顶部。

• 此外，将堆栈S2的所有元素推回堆栈S1

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

• 为了执行出队操作，我们需要从堆栈S1中弹出项目，因为现在第一个插入的元素在S1中位于顶部，而不是位于底部。

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

如果您使用Stack分析入队和出队操作的时间复杂度，您会发现入队操作比出队操作要昂贵得多。

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

方法2：使出队操作变得昂贵

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

• 为了实现入队操作，我们将新输入的元素插入堆栈S1的顶部。
  因此，使用堆栈的入队操作的时间复杂度变为O(1)。

• 为了实现出队操作，它检查堆栈S1和S2的下溢条件。
  如果两个堆栈都突出显示为空，则会引发错误。

• 如果堆栈S2为空且S1不为空，则将堆栈S1中的所有元素移至堆栈S2，并弹出堆栈S2的顶部元素，并将其从出队操作中移出。

• 因此，使用堆栈的出队操作的时间复杂度变为O(n)。

队列数据结构的应用

• CPU调度

• 磁盘调度

• 处理器之间的异步数据传输，例如文件IO等。

• 广度优先搜索算法(BFS)