在C语言中创建一个队列

7 月 ago
文, 翔
4 minutes

在C中，队列基本上是一种线性数据结构，用于存储和操作数据元素。它遵循先进先出（FIFO）的顺序。

在队列中，进入数组的第一个元素是从数组中移除的第一个元素。

例如，让我们考虑一个公交车票预订摊位的情景。在这里，遵循C编程队列的方式。车票按先来先服务的方式分发，即第一个进入的人将第一个获得车票。

队列的两端都是开放的。一个端口用来插入数据，另一个端口用来删除数据。

一个队列可以用任何编程语言来实现，例如C、Java、Python等。

在C语言中与队列相关的操作

队列作为一种抽象数据结构，提供了以下对数据元素进行操作的方法：

  • isEmpty(): To check if the queue is empty
  • isFull(): To check whether the queue is full or not
  • dequeue(): Removes the element from the frontal side of the queue
  • enqueue(): It inserts elements to the end of the queue
  • Front: Pointer element responsible for fetching the first element from the queue
  • Rear: Pointer element responsible for fetching the last element from the queue

队列数据结构的工作原理

队列遵循先进先出的模式，第一个元素被首先从元素列表中取出。

  • Front and Rear pointers keep the record of the first and last element in the queue.
  • At first, we need to initialize the queue by setting Front = -1 and 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.
  • 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.

使用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

使用堆栈实现队列的功能

堆栈数据结构可以用来实现队列的操作。使用两个堆栈来实现队列。在你练习下面的例子之前，请确保你非常了解堆栈的运作。

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

  • Making the enqueue operation costly
  • Making the dequeue operation costly

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

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

  • If S1 is not empty, push all elements to stack 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.
  • Further, push all the elements of stack S2 back to Stack S1

注意：入队操作的时间复杂度将为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.

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

如果你分析使用栈进行Enqueue和Dequeue操作的时间复杂度，你会发现Enqueue操作比Dequeue操作更加昂贵。

因此，如上所述，我们将第一个进入或最早进入的元素保留在堆栈S1的顶部，以便在调用Dequeue操作时被移除。

方法二：将出队操作变得更加昂贵

让我们再次假设有两个栈：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).
  • 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.
  • 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.
  • Thus, the time complexity of the dequeue operation using Stacks becomes O(n).

队列数据结构的应用

  • CPU Scheduling
  • Disk Scheduling
  • Asynchronous data transfer between processors such as File IO, etc.
  • Breadth-First Search Algorithm (BFS)

结论

在这篇文章中，我们已经了解了队列数据结构的工作原理，并且也简单介绍了使用栈数据结构实现队列的方法。

参考文献

  • Queue in C
  • Queue using Stacks