数据结构中的 FIFO 方法

2025年3月17日 | 阅读32分钟

FIFO 的全称是 先进先出，在这种方法中，我们将数据元素输入到数据结构中；最后添加到任何数据结构中的数据元素将最后被移除，而首先添加的元素将首先被移除。在这里，我们平等对待数据元素；首先进入的元素将首先有机会离开。我们称之为先来先服务，它是通过一种名为队列的数据结构实现的。

理解 FIFO 原理的最佳示例是排队购买电影票，前面有很多人，我们别无选择，只能等待。如果我们观察上面的例子，我们可以清楚地看到，我们将排在前面的人之后，并被视为先来先服务。

FIFO 原理在各种进程调度算法中具有重要意义，操作系统使用这些算法来确定多个进程的调度顺序。
CPU 使用的算法之一是 FCFS（先来先服务），它为每个进程提供公平的机会，并且通过使用队列数据结构来实现。
在最早的调度算法之一中，我们将使用循环算法，而循环队列具有重要意义；通过使用循环队列，我们可以抢占进程，并使用循环队列为每个进程提供公平的机会。该算法由计算中的进程和网络调度程序使用。
它也用于计算机控制的交通信号系统。
它也用于 CPU 调度和内存管理。
基于 FIFO 原理的数据结构是队列。
在队列数据结构中，我们将执行两个主要操作：首先，Enqueue 操作用于将数据元素插入队列；另一个是 Dequeue 操作，用于从队列中移除数据元素。
在栈中，我们主要使用两个操作：push 用于将数据元素压入栈，另一个是 pop 用于从栈中移除元素。
队列有两个端，即队首和队尾。
许多程序都基于 FIFO 原理的概念。
队列是一种重要的线性数据结构，广泛用于各种计算机应用程序，并且它基于FIFO（先进先出）原理。它遵循特定的数据执行顺序来进行操作。在此数据结构中，数据从一端（即队尾）进入，下一个数据在前面的数据之后进入队列。删除操作从另一端（即队首）执行。
与栈相比，栈也是一种线性数据结构。虽然它基于LIFO（后进先出）原理，这意味着数据一次从一端进入栈，直到达到其末端限制，然后数据元素从同一端弹出。
在栈中，只需要一个指针来执行所有操作，即栈顶；而在队列中，需要两个指针，即队尾和队首，来执行所有操作。

如前所述，这种方法称为先进先出方法或 FIFO。

FIFO 方法的应用

FIFO 的应用如下：

1）数据结构

队列是一种基于 FIFO 方法的线性数据结构，其中数据元素通过队尾进入队列，并通过队首删除元素。

FIFO 方法主要用于网络桥接器、交换机和路由器。

它进一步被归类为线性队列。

线性队列

线性队列是一种基于 FIFO（先进先出）原理的线性数据结构，其中数据从队尾进入，从队首删除。线性队列被认为是简单队列，当我们讨论队列时，默认是指线性队列。我们将在后面的部分更详细地讨论这些端点。

其他示例，如 ->

人们在等公交车。排在队列前面的人将是第一个上车的人。
汽车排在收费站桥前。最先到达桥的汽车将是第一个离开的。

线性队列的操作

线性队列中有一些基本操作如下 ->

入队
- 此操作用于向队列添加数据元素。
- 通过应用此操作，数据按顺序一个接一个地进入队列。入队操作将一直持续，直到队列达到其末端限制。
- 一旦达到终点，就无法将数据添加到队列中，此时称为溢出条件。
- 入队操作从队尾执行。
出队
- 此操作用于从队列中删除数据元素。
- 使用出队操作，删除的是最先入队的那个数据元素，或者元素按入栈的相同顺序出栈。
- 此过程将删除队列中的数据元素，直到整个队列变空。一旦所有元素都被删除，则无法执行删除操作，此时称为下溢条件。
- 它从队首执行。
查看
此操作用于在不将其出队的情况下，找出最先要服务的队列元素。

线性队列的两个端

队首 - 指队列的初始或起始位置。队首主要用于从队列中删除数据元素或执行出队操作。
队尾 - 指队列的最后或后部位置。队尾主要用于插入队列数据元素或执行入队操作。

线性队列的实现方法

有各种实现队列的方法。

使用数组实现队列
使用栈实现队列
使用链表实现队列

使用数组实现线性队列

这里我们讨论使用数组实现队列 ->

队列可以很容易地通过使用线性数组来实现。如前所述，队列有队首和队尾指针，可以从中删除和插入数据元素。

步骤：

最初，我们需要创建一个大小为“n”的数组，无论是静态的还是动态的，取决于用户。
声明两个指针，分别称为 FRONT 和 REAR。
将 REAR 初始化为 -1，FRONT 初始化为 0。
创建三个函数，分别称为 Enqueue（用于向队列添加数据元素）、Dequeue（用于从队列删除数据元素）和 peek（用于在不将其出队的情况下找出队列的第一个元素）。

入队操作算法

步骤 1 - 检查 REAR == FRONT。

步骤 2 - 如果上述语句成立，则称这种情况为溢出，无法进一步插入数据元素。

步骤 3 - 如果不成立，则

将 REAR = REAR + 1，然后
在队尾位置将数据元素添加到队列中。
Queue[REAR] = data。

出队操作算法

步骤 1 - 检查 FRONT = REAR + 1。

步骤 2 - 如果上述语句成立，则

这种情况称为下溢。
返回 -1。

步骤 3 - 如果不成立，则

从队列的队首位置弹出值。
data = Queue[FRONT]。
返回数据。

步骤 4 - 然后设置 FRONT = FRONT + 1，它指向下一个数据元素。

Peek 操作算法

步骤 1 - 检查 FRONT = REAR + 1。

步骤 2 - 如果上述语句成立，则显示消息；队列为空。

步骤 3 - 如果不成立，则

返回队列中位于队首位置的数据元素。
data = Queue[FRONT]。
返回数据。

使用队列（数组实现）在 C 编程语言中实现 FIFO 方法

// C program to implement the FIFO Approach
// using queue by performing insertion and deletions operations in an array

#include<stdio.h>
#include<stdlib.h>
#define MAX 10             
int queue [ MAX ] ;            //Declaration of Array
int front = -1 , rear = -1 ;
void enqueue () ;
int dequeue () ;
int peek () ;
void display () ;

void main()
{
	int choice , data ;
	while ( 1 )
	{
		printf ( " \n \n ***************** Menu ******************** \n " ) ;
		printf ( " 1. Insert the element \n " ) ;
		printf ( " 2. Delete the element \n " ) ;
		printf ( " 3. Peek value on queue \n " ) ;
		printf ( " 4. Display Queue \n " ) ;
		printf ( " 5. Exit \n " ) ;
		printf ( " Enter your choice -> " ) ;
		scanf ( "%d" , &choice ) ;
		
		switch ( choice )
		{
			case 1 :
				enqueue () ;
				break ;
			case 2 :
				data = dequeue () ;
				if ( data != -1 )
				printf ( " \n The data element popped out from queue is -> %d " , data ) ;
				break ;
			case 3 :
				data = peek () ;
				if ( data != -1 )
				printf ( " \n The first value in queue is -> %d " , data ) ;
				break ;
			case 4 :
				display () ;
				break ;
			case 5 :
				exit ( 0 ) ;
				break ;
			default :
				printf ( " \n Choice not available \n " ) ;		
		}	
	}
}
void enqueue ()
{
	int val ;
	printf ( " Enter data to insert in queue -> " ) ;
	scanf ( "%d" , &val ) ;
	if ( rear == MAX - 1 )
	{
		printf ( " Overflow Condition " ) ;
	}
	else 
	{
	if ( front == -1 )
	{
		front = 0 ;
	}
	    rear = rear + 1 ;
		queue [ rear ] = val ;
		
	}
}
int dequeue ()
{
	int val ;
	if ( front == -1 || rear < front )
	{
		printf ( " \n Underflow condition " ) ;
		return -1 ;
	}
	else
	{
		val = queue [ front ] ;
		front = front + 1 ;
		if ( front > rear )
		{
			front = rear = -1 ;
		}
		return val ;
	}
}
int peek ()
{
	if ( front == -1 || rear < front )
	{
		printf ( " \n Queue is empty " ) ;
		return -1 ;
	}
	else
	{
		return queue [ front ] ;
	}	
}
void display()
{
	int i ;
	printf ( " \n " ) ;
	if ( front == -1 || front > rear )
	{
	printf ( " \n Queue is empty " ) ;
    }
	else
	{
		for ( i = front ; i <= rear ; i++ )
		{
			printf ( " %d \n " , queue [ i ] ) ;
		}
	}
}

上述程序的输出是

使用数组（队列实现）在 C++ 编程语言中实现 FIFO 方法

// C++ program to implement the FIFO Approach
// using queue by performing insertion and deletions operations in array

#include<iostream>
using namespace std;
#include<stdlib.h>
#define MAX 10             //changing this value will change the length of queue
int queue [ MAX ] ;            //Declaration of Array
int front = -1 , rear = -1 ;
void enqueue () ;
int dequeue () ;
int peek () ;
void display () ;

int main()
{
	int choice , data ;
	while ( 1 )
	{
		cout << endl ;
		cout << " ***************** Menu ******************** " << endl ;
		cout << " 1. Insert the element " << endl ;
		cout << " 2. Delete the element " << endl ;
		cout << " 3. Peek value on queue " << endl ;
		cout << " 4. Display Queue " << endl  ;
		cout << " 5. Exit " << endl ;
		cout << " Enter your choice -> " ;
		cin >> choice ;
		
		switch ( choice )
		{
			case 1 :
				enqueue () ;
				break ;
			case 2 :
				data = dequeue () ;
				if ( data != -1 )
				cout << " The data element popped out from queue is -> " << data << endl ;
				break ;
			case 3 :
				data = peek () ;
				if ( data != -1 )
				cout << " The first value in queue is -> " <<  data << endl ;
				break ;
			case 4 :
				display () ;
				break ;
			case 5 :
				exit ( 0 ) ;
				break ;
			default :
				cout << " Choice not available " << endl ;		
		}	
	}
}
void enqueue ()
{
	int val ;
	cout << " Enter data to insert in queue -> " ;
	cin >> val ;
	if ( rear == MAX - 1 )
	{
		cout << " Overflow Condition " << endl ;
	}
	else 
	{
	if ( front == -1 )
	{
		front = 0 ;
	}
	    rear = rear + 1 ;
		queue [ rear ] = val ;
		
	}
}
int dequeue ()
{
	int val ;
	if ( front == -1 || rear < front )
	{
		cout << " Underflow condition " << endl ;
		return -1 ;
	}
	else
	{
		val = queue [ front ] ;
		front = front + 1 ;
		if ( front > rear )
		{
			front = rear = -1 ;
		}
		return val ;
	}
}
int peek ()
{
	if ( front == -1 || rear < front )
	{
		cout << " Queue is empty " << endl ;
		return -1 ;
	}
	else
	{
		return queue [ front ] ;
	}	
}
void display()
{
	int i ;
	cout << endl ;
	if ( front == -1 || front > rear )
	{
	cout << " Queue is empty " << endl ;
    }
	else
	{
		for ( i = front ; i <= rear ; i++ )
		{
			cout << queue [ i ] << endl ;
		}
	}
}

上述程序的输出是

使用队列在 Java 编程语言中实现 FIFO 方法

// Java program to implement the FIFO Approach
// using queue by performing insertion and deletions operations in an array

class Queue {
    private static int front, rear, cap;
    private static int queue[];
 
    Queue(int c)
    {
        front = rear = 0;
        cap = c;
        queue = new int[cap];
    }
 
    
    static void queueenq(int data)
    {
        // check queue is full or not
        if (cap == rear) {
            System.out.printf("\nQueue is full\n");
            return;
        }
 
        // insert element at the rear
        else {
            queue[rear] = data;
            rear++;
        }
        return;
    }
 
    // function to delete an element
    // from the front of the queue
    static void queuedeq()
    {
       
        if (front == rear) {
            System.out.printf("\nQueue is empty\n");
            return;
        }
        else {
            for (int i = 0; i < rear - 1; i++) {
                queue[i] = queue[i + 1];
            }  
            if (rear < capacity)
                queue[rear] = 0;           
            rear--;
        }
        return;
    }
    static void queuedisplay()
    {
        int i;
        if (front == rear) {
            System.out.printf("\nQueue is Empty\n");
            return;
        }
        for (i = front; i < rear; i++) {
            System.out.printf(" %d <-- ", queue[i]);
        }
        return;
    }
    static void queuefront()
    {
        if (front == rear) {
            System.out.printf("\nQueue is Empty\n");
            return;
        }
        System.out.printf("\nFront Element is: %d", queue[front]);
        return;
    }
}
public class SQueue {
    public static void main(String[] args)
    {
        Queue q = new Queue(4);
        // print Queue elements
        q.queuedisplay();
        // inserting elements in the queue
        q.queueenq(20);
        q.queueenq(30);
        q.queueenq(40);
        q.queueenq(50);
 
        // print Queue elements
        q.queuedisplay();
        // insert element in the queue
        q.queueenq(60);
        // print Queue elements
        q.queuedisplay();
        q.queuedeq();
        q.queuedeq();
        System.out.printf("\n\nafter two node deletion\n\n");
        q.queuedisplay();        
        q.queuefront();
    }
}

上述程序的输出是

Queue is Empty
 20 <--  30 <--  40 <--  50 <-- 
Queue is full
 20 <--  30 <--  40 <--  50 <-- 

after two node deletion

 40 <--  50 <-- 
Front Element is: 40

使用队列在 Python 编程语言中实现 FIFO 方法

# Python program to implement the FIFO Approach
# using queue by performing insertion and deletions operations in an array
q = []
 

for i in range(5):
    q.append(i)
 

print("Elements of queue-" , q)
 

remove = q.pop(0)
print("removed element-" , remove)
 
print(q)
 
# To view the head of Queue
head = q[0]
print("head of the queue-", head)
 
size = len(q)
print("Size of queue-" , size)

上述程序的输出是

   Elements of queue - [ 0, 1, 2, 3, 4 ]
   removed element - 0
   [ 1, 2, 3, 4 ]
   Peek value of queue - 1
   Size of queue - 4

使用队列在 C# 编程语言中实现 FIFO 方法

// C# program to implement the FIFO Approach
// using queue by performing insertion and deletions operations in an array

using System;
using System.Collections.Generic;
 
public class QueueImplement
{
    public static void Main(String[] args)
    {
        Queue<int> q = new Queue<int>();
 

        for (int i = 0; i < 5; i++)
            q.Enqueue(i);
 
        
        Console.Write("Elements of queue-");
        foreach(int s in q)
                Console.Write(s + " ");
 
        

        int remove = q.Dequeue();
        Console.Write("\nremoved element-" + remove + "\n");
        foreach(int s in q)
                Console.Write(s + " ");
 
       
        int head = q.Peek();
        Console.Write("\n Peek value of queue-" + head);
 
        

        int size = q.Count;
        Console.WriteLine("\nSize of queue-" + size);
    }
}

上述程序的输出是

   Elements of queue - [ 0, 1, 2, 3, 4 ]
   removed element - 0
   [ 1, 2, 3, 4 ]
   Peek value of queue - 1
   Size of queue - 4

使用队列在 JavaScript 编程语言中实现 FIFO 方法

<script> 
// C# program to implement the FIFO Approach
// using queue by performing insertion and deletions operations in array
let q = [];

for (let i = 0; i < 5; i++)
    q.push(i);
 

document.write("Elements of queue-[" + q.join(", ")+"]<br>");
 

let remove = q.shift();
document.write("removed element-" + remove+"<br>");
 
document.write("["+q.join(", ")+"]<br>");
let head = q[0];
document.write("Peek value of queue-" + head+"<br>");
 

let size = q.length;
document.write("Size of queue-" + size+"<br>");

</script>

上述程序的输出是

   Elements of queue - [ 0, 1, 2, 3, 4 ]
   removed element - 0
   [ 1, 2, 3, 4 ]
   Peek value of queue - 1
   Size of queue - 4

使用栈（队列实现）在 C 编程语言中实现 FIFO 方法

// C program to implement the FIFO Approach
// using queue by performing push and pop operations in the stack

#include<stdio.h>
#include<stdlib.h>
#define N 5
int stack1 [ N ] , stack2 [ N ] ;
int top1 = -1 , top2 = -1 ;
void enq ( int ) ;
void dq ( ) ;
void push1 ( int ) ;
void push2 ( int ) ;
int pop1 ( ) ;
int pop2 ( ) ;
int count = 0 ;
void display ( ) ;

void enq ( int val )
{
	push1 ( val ) ;
	count = count  + 1 ;
}
void push2 ( int val )
{
		top2 = top2 + 1 ;
		stack2 [ top2 ] = val ;
}
void push1 ( int val )
{
	if ( top1 == N - 1 )
	{
		printf ( " Queue is full !! \n " ) ;
	}
	else
	{
		top1 = top1 + 1;
		stack1 [ top1 ] = val ;
	}
}
int pop1 ( )
{
	return stack1 [ top1-- ] ;
}
int pop2 ( )
{
	return stack2 [ top2 -- ] ;
}

void deq ( )
{
	if ( top1 == -1 && top2 == -1 )
	{
		printf ( "Queue is empty !! \n " ) ;
	}
	else
	{
		int i = 0 , b ;
		for ( i = 0 ; i < count ; i++ )
		{
			push2 ( pop1 ( ) ) ;
		}
		b = pop2 () ;
		count = count - 1 ;
		for ( i = 0 ; i < count ; i++ )
		{
			push1 ( pop2 () ) ;
		}
	}
}
void display()
{
	int i ;
	for ( i = 0 ; i <= top1 ; i++ )
	{
		printf ( " %d \n " , stack1 [ i ] ) ;
	}
}
void main()
{
	deq ( ) ;                         // queue is empty
	enq ( 10 ) ;
	enq ( 20 ) ;
	enq ( 30 ) ;
	enq ( 40 ) ;
	enq ( 50 ) ;
	enq ( 60 ) ;                            // queue is full
	deq ( ) ;
	display ( ) ;                            // 20 30 40 50
}

上述程序的输出是

  Queue is empty !!
  Queue is full !!
  20
  30
  40
  50

使用栈（队列实现）在 C++ 编程语言中实现 FIFO 方法

// C++ program to implement the FIFO Approach
// using queue by performing push and pop operations in stack
#include<iostream>
using namespace std;
#include<stdlib.h>
#define N 5
int stack1 [ N ] , stack2 [ N ] ;
int top1 = -1 , top2 = -1 ;
void enq ( int ) ;
void dq ( ) ;
void push1 ( int ) ;
void push2 ( int ) ;
int pop1 ( ) ;
int pop2 ( ) ;
int count = 0 ;
void display ( ) ;

void enq ( int val )
{
	push1 ( val ) ;
	count = count  + 1 ;
}
void push2 ( int val )
{
		top2 = top2 + 1 ;
		stack2 [ top2 ] = val ;
}
void push1 ( int val )
{
	if ( top1 == N - 1 )
	{
		cout << " Queue is full !! " << endl ;
	}
	else
	{
		top1 = top1 + 1;
		stack1 [ top1 ] = val ;
	}
}
int pop1 ( )
{
	return stack1 [ top1-- ] ;
}
int pop2 ( )
{
	return stack2 [ top2 -- ] ;
}

void deq ( )
{
	if ( top1 == -1 && top2 == -1 )
	{
		cout << "Queue is empty !! " << endl ;
	}
	else
	{
		int i = 0 , b ;
		for ( i = 0 ; i < count ; i++ )
		{
			push2 ( pop1 ( ) ) ;
		}
		b = pop2 () ;
		count = count - 1 ;
		for ( i = 0 ; i < count ; i++ )
		{
			push1 ( pop2 () ) ;
		}
	}
}
void display()
{
	int i ;
	for ( i = 0 ; i <= top1 ; i++ )
	{
		cout << stack1[ i ] << endl ;
	}
}
int  main()
{
	deq ( ) ;                         // queue is empty
	enq ( 7 ) ;
	enq ( 20 ) ;
	enq ( 3 ) ;
		display ( ) ;  
	enq ( 40 ) ;
	enq ( 50 ) ;
	                           // queue is full
	deq ( ) ;
	deq ( ) ;
	display ( ) ;                            // 20 30 40 50
}

上述程序的输出是

Queue is empty !!
  Queue is full !!
  20
  3
  40
  50

循环队列

使用循环队列实现 FIFO 方法

循环队列也是一种重要的队列类型。它与线性队列相似，但有一些变体。循环队列的末端位置连接回起始位置，形成类似圆形的结构并构成一个圆。循环队列也基于先进先出（FIFO）原理。它也称为“环形缓冲区”。

正如我们之前所见，在线性队列中，当 REAR 到达末端且 FRONT 也到达末端时，无法进一步插入数据元素。队列仍然为空，但它显示队列已满，因此引入了循环的概念来解决上述问题。在循环队列中，此问题不会出现。我们将在下面的部分中进一步详细讨论。

基于 FIFO 原理的数据结构是栈。我们主要对其进行两种操作：push 和 pop。Push 操作用于将数据元素压入栈，pop 操作用于从栈中弹出数据元素。

线性队列中有一些基本操作如下 ->

入队
- 此操作用于向队列插入数据元素。
- 在循环队列中，数据元素始终从队尾位置添加。
出队
- 此操作用于从队列中删除数据元素。
- 在循环队列中，数据元素的删除始终从队首位置进行。

循环队列的两个端

在循环队列中，有一个类似圆形的结构；因此没有两个端点区分开，但为了区分数据元素的插入和删除标准，我们仍然引用这两个端点。

队首 - 用于从队列中删除数据元素。
队尾用于向队列中插入数据元素。

使用数组实现循环队列

循环队列可以很容易地通过使用数组来实现。它基于循环增量过程。如前所述，它有两个指针，队首和队尾。从队尾可以插入数据元素。如果队尾指针到达末端，它会再次递增到队列的初始位置，以便还可以进行进一步插入，因此这表示一个增量过程。

从队首可以删除数据元素。如果队首指针到达末端，它会返回到队列的初始位置，以便可以进行进一步删除。

使用队列大小的模运算执行循环增量。

步骤：

最初，我们需要创建一个大小为“n”的数组，无论是静态的还是动态的，取决于用户。
然后声明两个指针，分别称为 FRONT 和 REAR。
将 REAR 初始化为 -1，FRONT 初始化为 -1。
创建两个函数，分别称为 Enqueue（用于向队列添加数据元素）和 Dequeue（用于从队列删除数据元素）。

循环队列的实现

入队操作算法

步骤 1 - 检查 FRONT == 0 && REAR == (n-1) || REAR == (FRONT - 1) % (n-1)。

步骤 2 - 如果上述语句成立，则称这种情况为溢出，无法进一步插入数据元素。

步骤 3 - 否则，如果 FRONT == -1，则

设置 REAR = 0，FRONT = 0，然后
在队尾位置将数据元素添加到队列中。
Queue[REAR] = data。

步骤 4 - 否则，如果 REAR == (n-1) && FRONT != 0

设置 REAR = 0，然后
在队尾位置将数据元素添加到队列中。
Queue[REAR] = data。

步骤 5 - 否则

设置 REAR = REAR + 1
在队尾位置将数据元素添加到队列中。
Queue[REAR] = data。

出队操作算法

步骤 1 - 检查 FRONT == -1。

步骤 2 - 如果上述语句成立，则

这种情况称为下溢。
返回 -1。

步骤 3 - 如果不成立，则

从队列的队首位置弹出值。
data = Queue[FRONT]。
返回数据。

步骤 4 - 然后设置 FRONT = FRONT + 1，它指向下一个数据元素。

步骤 5 - 如果 FRONT == REAR，则设置 FRONT = -1 和 REAR = -1。

步骤 6 - 否则，如果 FRONT == n-1，则设置 FRONT = 0。

使用循环队列在 C 编程语言中实现 FIFO 方法

// C program to implement the FIFO Approach
// using circular queue by performing insertion and deletion operations
#include<stdio.h>
#include<stdlib.h>
struct queue {
	int size ;
	int f , r ;
	int *arr ;
} ;
int isempty ( struct queue *q )
{
	if ( q -> f == q -> r )
	{ return 1 ;
	}
	return 0 ;
}

int isfull ( struct queue *q )
{
	if ( q -> r == ( q -> size ) - 1 )
	{
		return 1 ;
}
else
return 0 ;	
}
int dequeue ( struct queue *q )
{
	int a = - 1 ;
	if ( isempty ( q ) )
	{
		printf ( "Queue is Empty !! \n " ) ;
	}
	else
	{
		q -> f = q -> f + 1 ;
		a = q -> arr [ q -> f ] ;
	}
	return a ;
}
void enqueue ( struct queue *q , int val )
{
	if ( isfull ( q ) )
	{
		printf ( "Queue is full !! \n " ) ;
	}
	else
	{
		q -> r = q -> r + 1 ;
		q -> arr [ q -> r ] = val ;
		printf ( "Enqueue value %d successfully !! \n \n " , val ) ;
	}
}
int main()
{
	struct queue q ;
//	q = malloc ( sizeof ( struct queue ) ) ;
	q.size = 5 ;

	q.arr = ( int * ) malloc ( sizeof ( int ) * q.size ) ;
	q.f = q.r = - 1 ;
//  enqueue opration
    enqueue ( &q , 20 ) ;
    enqueue ( &q , 30 ) ;
    enqueue ( &q , 40 ) ;
    enqueue ( &q , 60 ) ;
    enqueue ( &q , 70 ) ;
    enqueue ( &q , 19 ) ;
// Dequeue operation
    printf ( "Deleting  value: %d \n \n " , dequeue( &q ) ) ;
    printf ( "Deleting  value: %d \n \n " , dequeue( &q ) ) ;
    printf ( "Deleting  value: %d \n \n " , dequeue( &q ) ) ;
    printf ( "Deleting  value: %d \n \n " , dequeue( &q ) ) ;
    dequeue ( &q ) ;

	return 0 ;
}

上述程序的输出是

 Enqueue value 20 successfully !!
 Enqueue value 30 successfully !!
 Enqueue value 40 successfully !!
 Enqueue value 60 successfully !!
 Enqueue value 70 successfully !!
 Queue is full !!
 Deleting  value: 20
 Deleting  value: 30
 Deleting  value: 40
 Deleting  value: 60

使用结构（循环队列实现）在 C++ 编程语言中实现 FIFO 方法

// C++ program to implement the FIFO Approach
// using circular queue by performing insertion and deletion operations
#include<iostream>
using namespace std;
#include<stdlib.h>
struct queue {
	int size ;
	int f , r ;
	int *arr ;
} ;
int isempty ( struct queue *q )
{
	if ( q -> f == q -> r )
	{ return 1 ;
	}
	return 0 ;
}

int isfull ( struct queue *q )
{
	if ( q -> r == ( q -> size ) - 1 )
	{
		return 1 ;
}
else
return 0 ;	
}
int dequeue ( struct queue *q )
{
	int a = - 1 ;
	if ( isempty ( q ) )
	{
		cout << "Queue is Empty !! " << endl ;
	}
	else
	{
		q -> f = q -> f + 1 ;
		a = q -> arr [ q -> f ] ;
	}
	return a ;
}
void enqueue ( struct queue *q , int val )
{
	if ( isfull ( q ) )
	{
		cout << "Queue is full !! " << endl ;
	}
	else
	{
		q -> r = q -> r + 1 ;
		q -> arr [ q -> r ] = val ;
		cout << "Enqueue value " << val << " successfully !! " << endl << endl ;
	}
}
int main()
{
	struct queue q ;
//	q = malloc ( sizeof ( struct queue ) ) ;
	q.size = 5 ;

	q.arr = ( int * ) malloc ( sizeof ( int ) * q.size ) ;
	q.f = q.r = - 1 ;
//  enqueue opration
    enqueue ( &q , 7 ) ;
    enqueue ( &q , 11 ) ;
    enqueue ( &q , 4 ) ;
    enqueue ( &q , 6 ) ;
    enqueue ( &q , 7 ) ;
    enqueue ( &q , 19 ) ;
// Dequeue operation
    cout << "Deleting  value: " << dequeue( &q ) << endl ;
    cout << "Deleting  value: " << dequeue( &q ) << endl ;
    cout << "Deleting  value: " << dequeue( &q ) << endl ;
    cout << "Deleting  value: " << dequeue( &q ) << endl ;
    dequeue ( &q ) ;

	return 0 ;
}

上述程序的输出是

Enqueue value 7 successfully !!
 Enqueue value 11 successfully !!
 Enqueue value 4 successfully !!
 Enqueue value 6 successfully !!
 Enqueue value 7 successfully !!
 Queue is full !!
 Deleting  value: 7
 Deleting  value: 11
 Deleting  value: 4
 Deleting  value: 6

使用数组（循环队列）在 Java 编程语言中实现 FIFO 方法

// Java program to implement the FIFO Approach
// using circular queue by performing insertion and deletion operations import java.util.ArrayList;
 
class Circularqueue{
 
private int size, front, rear;
 
private ArrayList<Integer> queue = new ArrayList<Integer>();
 
Circularqueue(int size)
{
    this.size = size;
    this.front = this.rear = -1;
}
 
public void enqueue(int data)
{
     
    
    if((front == 0 && rear == size - 1) ||
      (rear == (front - 1) % (size - 1)))
    {
        System.out.print("Queue is Full !!");
    }
 
    else if(front == -1)
    {
        front = 0;
        rear = 0;
        queue.add(rear, data);
    }
 
    else if(rear == size - 1 && front != 0)
    {
        rear = 0;
        queue.set(rear, data);
    }
 
    else
    {
        rear = (rear + 1);
     
        if(front <= rear)
        {
            queue.add(rear, data);
        }
     
      
        else
        {
            queue.set(rear, data);
        }
    }
}
 
public int dequeue()
{
    int temp;
 
    if(front == -1)
    {
        System.out.print("Queue is Empty");
         
        return -1;
    }
 
    temp = queue.get(front);
 
    
    if(front == rear)
    {
        front = -1;
        rear = -1;
    }
 
    else if(front == size - 1)
    {
        front = 0;
    }
    else
    {
        front = front + 1;
    }
     

    return temp;
}
public void displayqueue()
{
     
    
    if(front == -1)
    {
        System.out.print("Queue is Empty");
        return;
    }
 
    System.out.print("Elements in the " +
                     "circular queue are: ");
 
    if(rear >= front)
    {
     
        for(int i = front; i <= rear; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
        System.out.println();
    }
 
    
    else
    {
         
        for(int i = front; i < size; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
 
        for(int i = 0; i <= rear; i++)
        {
            System.out.print(queue.get(i));
            System.out.print(" ");
        }
        System.out.println();
    }
}
 

public static void main(String[] args)
{
     
    Circularqueue q = new Circularqueue(5);
     
    q.enqueue(14);
    q.enqueue(22);
    q.enqueue(13);
    q.enqueue(8);
     
    q.displayqueue();
 
    int del = q.dequeue();
 
        if(del != -1)
    {
        System.out.print("Deleted value = ");
        System.out.println(del);
    }
 
    del = q.dequeue();
 
        if(del != -1)
    {
        System.out.print("Deleted value = ");
        System.out.println(del);
    }
 
    q.displayqueue();
     
    q.enqueue(9);
    q.enqueue(20);
    q.enqueue(5);
     
    q.displayqueue();
     
    q.enqueue(20);
}
}

上述程序的输出是

Elements in Circular Queue are : 14   22  13   8
Deleted value = 14    
Deleted value = 22    
Elements in Circular Queue are : 13  8
Elements in Circular Queue are :  13  8   9   20   5
Queue is Full !!

使用数组（循环队列）在 Python 编程语言中实现 FIFO 方法

# Python program to implement the FIFO Approach
# using circular queue by performing insertion and deletion operations
class Circularqueue():
 
    
    def __init__(self, size): # initializing the class
        self.size = size
         
        self.queue = [None for i in range(size)]
        self.front = self.rear = -1
 
    def enqueue(self, data):
         
        if ((self.rear + 1) % self.size == self.front):
            print(" Queue is Full !! \n")
             
            elif (self.front == -1):
            self.front = 0
            self.rear = 0
            self.queue[self.rear] = data
        else:
             
            self.rear = (self.rear + 1) % self.size
            self.queue[self.rear] = data
             
    def dequeue(self):
        if (self.front == -1): # condition for empty queue
            print ("Queue is Empty\n")
             
            elif (self.front == self.rear):
            temp=self.queue[self.front]
            self.front = -1
            self.rear = -1
            return temp
        else:
            temp = self.queue[self.front]
            self.front = (self.front + 1) % self.size
            return temp
 
    def display(self):
     
        
        if(self.front == -1):
            print ("Queue is Empty")
 
        elif (self.rear >= self.front):
            print("Elements in the circular queue are:",
                                              end = " ")
            for i in range(self.front, self.rear + 1):
                print(self.queue[i], end = " ")
            print ()
 
        else:
            print ("Elements in Circular Queue are:",
                                           end = " ")
            for i in range(self.front, self.size):
                print(self.queue[i], end = " ")
            for i in range(0, self.rear + 1):
                print(self.queue[i], end = " ")
            print ()
 
        if ((self.rear + 1) % self.size == self.front):
            print("Queue is Full")
 

q = Circularqueue(5)
q.enqueue(4)
q.enqueue(22)
q.enqueue(3)
q.enqueue(-6)
q.display()
print ("Deleted value = ", q.dequeue())
print ("Deleted value = ", q.dequeue())
q.display()
q.enqueue(19)
q.enqueue(2)
q.enqueue(15)
q.display()

上述程序的输出是

Elements in Circular Queue are : 4   22   3   -6
Deleted value = 4    
Deleted value = 22    
Elements in Circular Queue are : 3  -6
Elements in Circular Queue are :  3  -6   19   2   15
Queue is Full !!

使用链表（循环队列）在 C 编程语言中实现 FIFO 方法

// C program to implement the FIFO Approach
// using circular queue by performing insertion and deletion operations
#include<stdio.h>
#include<stdlib.h>
struct cqueue
{
	int size ;
	int f , r ;
	int *array ;
} ;
int isfull ( struct cqueue *q )
{
	if ( (q -> r + 1 ) % q -> size == q -> f )
	return 1 ;
	else
	return 0 ;
}
int isempty ( struct cqueue *q )
{
	if ( q -> f == q -> r )
	{
		return 1 ;
	}
	else
	return 0 ;
}
void enqueue ( struct cqueue  *q , int val )
{
	if ( isfull ( q ) )
	{
		printf ( " Queue is full !! \n " ) ;
	}
	else
	{
		q -> r = ( q -> r + 1 ) % q -> size ;
		q -> array [ q -> r ] = val ;
		printf ( "Enqueue value is: %d \n " , val ) ;
	}
}
int dequeue ( struct cqueue *q )
{
	int a = - 1 ;
	if ( isempty ( q ) )
	{
		printf ( "Queue is empty !! \n " ) ;
	}
	else
	{
		q -> f = ( q -> f + 1 ) % q -> size ;
		a = q -> array [ q -> f ] ;
		
	}
	return a ;
}
int main()
{
	struct cqueue q ;
	q.size = 4 ;
	q.f = q.r = 0 ;
	q.array = ( int *) malloc ( sizeof ( int ) * q.size ) ;
//  enqueue opration
	enqueue ( &q , 20 ) ;
	enqueue ( &q , 30 ) ;
	enqueue ( &q , 40 ) ;
//	enqueue ( &q , 50 ) ;
//Dequeue operation
    printf ( "Deleting  value: %d \n \n " , dequeue ( &q ) ) ;
    printf ( "Deleting  value: %d \n \n " , dequeue ( &q ) ) ;
    printf ( "Deleting  value: %d \n \n " , dequeue ( &q ) ) ;
 //   printf ( dequeue ( &q ) ) ;
	if ( isempty ( &q ) )
	{
		printf ( "Queue is empty !! \n " ) ;
	}	
	enqueue ( &q , 60 ) ;
	enqueue ( &q , 50 ) ;
	enqueue ( &q , 70 ) ;
	enqueue ( &q , 90 ) ;
	
}

上述程序的输出是

Enqueue value is: 20
 Enqueue value is: 30
 Enqueue value is: 40
 Deleting  value: 20
 Deleting  value: 30
 Deleting  value: 40
 Queue is empty !!
 Enqueue value is: 60
 Enqueue value is: 50
 Enqueue value is: 70
  Queue is full !!

使用链表（循环队列）在 C++ 编程语言中实现 FIFO 方法

// C++ program to implement the FIFO Approach
// using circular queue by performing insertion and deletion operations
#include<iostream>
using namespace std ;
#include<stdlib.h>
struct cqueue
{
	int size ;
	int f , r ;
	int *array ;
} ;
int isfull ( struct cqueue *q )
{
	if ( (q -> r + 1 ) % q -> size == q -> f )
	return 1 ;
	else
	return 0 ;
}
int isempty ( struct cqueue *q )
{
	if ( q -> f == q -> r )
	{
		return 1 ;
	}
	else
	return 0 ;
}
void enqueue ( struct cqueue  *q , int val )
{
	if ( isfull ( q ) )
	{
		cout << " Queue is full !! " << endl ;
	}
	else
	{
		q -> r = ( q -> r + 1 ) % q -> size ;
		q -> array [ q -> r ] = val ;
		cout << "Enqueue value is: " << val << endl ;
	}
}
int dequeue ( struct cqueue *q )
{
	int a = - 1 ;
	if ( isempty ( q ) )
	{
		cout << "Queue is empty " << endl ;
	}
	else
	{
		q -> f = ( q -> f + 1 ) % q -> size ;
		a = q -> array [ q -> f ] ;
		
	}
	return a ;
}
int main()
{
	struct cqueue q ;
	q.size = 4 ;
	q.f = q.r = 0 ;
	q.array = ( int *) malloc ( sizeof ( int ) * q.size ) ;
//  enqueue opration
	enqueue ( &q , 20 ) ;
	enqueue ( &q , 30 ) ;
	enqueue ( &q , 40 ) ;
//	enqueue ( &q , 50 ) ;
//Dequeue operation
    cout << "Deleting  value: " << dequeue ( &q ) << endl ;
    cout << "Deleting  value: " << dequeue ( &q ) << endl ;
    cout << "Deleting  value: " << dequeue ( &q ) << endl ;
 //   printf ( dequeue ( &q ) ) ;
	if ( isempty ( &q ) )
	{
		cout << "Queue is empty !! " << endl ;
	}	
	enqueue ( &q , 60 ) ;
	enqueue ( &q , 50 ) ;
	enqueue ( &q , 70 ) ;
	enqueue ( &q , 90 ) ;
	
}

上述程序的输出是

Enqueue value is: 20
 Enqueue value is: 30
 Enqueue value is: 40
 Deleting  value: 20
 Deleting  value: 30
 Deleting  value: 40
 Queue is empty !!
 Enqueue value is: 60
 Enqueue value is: 50
 Enqueue value is: 70
  Queue is full !!

使用链表（循环队列）在 Java 编程语言中实现 FIFO 方法

// Java program to implement the FIFO Approach
// using circular queue by performing insertion and deletion operations
import java.util.*;
  
class Solution {
  
    // Structure of a Node
    static class Node {
        int data;
        Node next;
    }
  
    static class Queue {
        Node front, rear;
    }
  
    // Function to create Circular queue
    static void enqueue(Queue q, int value)
    {
        Node temp = new Node();
        temp.data = value;
        if (q.front == null)
            q.front = temp;
        else
            q.rear.next = temp;
  
        q.rear = temp;
        q.rear.next = q.front;
    }
  
   
    static int dequeue(Queue q)
    {
        if (q.front == null) {
            System.out.printf("Queue is empty");
            return Integer.MIN_VALUE;
        }
  
       
        int value; 
        if (q.front == q.rear) {
            value = q.front.data;
            q.front = null;
            q.rear = null;
        }
        else // There are more than one nodes
        {
            Node temp = q.front;
            value = temp.data;
            q.front = q.front.next;
            q.rear.next = q.front;
        }
  
        return value;
    }
  
    
    static void displayqueue(Queue q)
    {
        Node temp = q.front;
        System.out.printf("\nElements in Circular Queue are: ");
        while (temp.next != q.front) {
            System.out.printf("%d ", temp.data);
            temp = temp.next;
        }
        System.out.printf("%d", temp.data);
    }
  
    public static void main(String args[])
    {
        
        Queue q = new Queue();
        q.front = q.rear = null;
  
        
        enqueue(q, 10);
        enqueue(q, 2);
        enqueue(q, 16);
  
        
        displayqueue(q);
  
        
        System.out.printf("\nDeleted value = %d", dequeue(q));
        System.out.printf("\nDeleted value = %d", dequeue(q));
  
        
        displayqueue(q);
  
        enqueue(q, 19);
        enqueue(q, 7);
        displayqueue(q);
    }
}

上述程序的输出是

Elements in Circular Queue are : 10   2    16
Deleted value = 10    
Deleted value = 2    
Elements in Circular Queue are : 16
Elements in Circular Queue are : 16    19   7

使用链表（循环队列）在 Python 编程语言中实现 FIFO 方法

# Python program to implement the FIFO Approach
# using circular queue by performing insertion and deletion operations
  
# Structure of a Node 
class Node:
    def __init__(self):
        self.data = None
        self.next = None
  
class Queue:
    def __init__(self):
        front = None
        rear = None
  
# Function to create Circular queue 
def enqueue(q, value):
    temp = Node() 
    temp.data = value 
    if (q.front == None): 
        q.front = temp 
    else:
        q.rear.next = temp 
  
    q.rear = temp 
    q.rear.next = q.front
  
# Function to delete element from 
# Circular Queue 
def dequeue(q):
    if (q.front == None):
        print("Queue is empty") 
        return -1
  
    
    value = None                          # Value to be dequeued 
    if (q.front == q.rear):
        value = q.front.data
        q.front = None
        q.rear = None
    else: # There are more than one nodes 
        temp = q.front 
        value = temp.data 
        q.front = q.front.next 
        q.rear.next = q.front
  
    return value 
  
# Function displaying the elements 
# of Circular Queue 
def displayqueue(q):
    temp = q.front 
    print("Elements in Circular Queue are: ", 
                                   end = " ") 
    while (temp.next != q.front):
        print(temp.data, end = " ") 
        temp = temp.next
    print(temp.data)
  
if __name__ == '__main__':
  
    # Create a queue and initialize
    # front and rear 
    q = Queue() 
    q.front = q.rear = None
  
    # Inserting elements in Circular Queue 
    enqueue(q, 10) 
    enqueue(q, 2) 
    enqueue(q, 16) 
  
    # Display elements present in 
    # Circular Queue 
    displayqueue(q) 
  
    # Deleting elements from Circular Queue 
    print("Deleted value = ", dequeue(q)) 
    print("Deleted value = ", dequeue(q)) 
  
    # Remaining elements in Circular Queue 
    displayqueue(q) 
  
    enqueue(q, 19) 
    enqueue(q, 7) 
    displayqueue(q)

上述程序的输出是

Elements in Circular Queue are : 10   2    16
Deleted value = 10    
Deleted value = 2    
Elements in Circular Queue are : 16
Elements in Circular Queue are : 16    19   7

循环队列相对于线性队列的优点

与循环队列相比，线性队列消耗更多内存。
循环队列使用一种有效的方式进行内存利用。
在循环队列中，在删除某个位置的先前数据后，可以再次在该位置插入新数据。
在线性队列中，如果队尾指针到达最后，并且队首指针删除了队列中的所有数据，它仍然会显示溢出消息，这是线性队列的主要缺点。
当队列已满时，循环队列会显示溢出消息。
易于执行出队和入队操作。

下一主题数据结构中的连通图

数据结构中的 FIFO 方法

FIFO 方法的应用

1）数据结构

线性队列

线性队列的实现方法

使用数组实现线性队列

使用队列（数组实现）在 C 编程语言中实现 FIFO 方法

使用数组（队列实现）在 C++ 编程语言中实现 FIFO 方法

使用队列在 Java 编程语言中实现 FIFO 方法

使用队列在 Python 编程语言中实现 FIFO 方法

使用队列在 C# 编程语言中实现 FIFO 方法

使用队列在 JavaScript 编程语言中实现 FIFO 方法

使用栈（队列实现）在 C 编程语言中实现 FIFO 方法

使用栈（队列实现）在 C++ 编程语言中实现 FIFO 方法

循环队列

使用循环队列实现 FIFO 方法

使用数组实现循环队列

使用循环队列在 C 编程语言中实现 FIFO 方法

使用结构（循环队列实现）在 C++ 编程语言中实现 FIFO 方法

使用数组（循环队列）在 Java 编程语言中实现 FIFO 方法

使用数组（循环队列）在 Python 编程语言中实现 FIFO 方法

使用链表（循环队列）在 C 编程语言中实现 FIFO 方法

使用链表（循环队列）在 C++ 编程语言中实现 FIFO 方法

使用链表（循环队列）在 Java 编程语言中实现 FIFO 方法

使用链表（循环队列）在 Python 编程语言中实现 FIFO 方法

循环队列相对于线性队列的优点

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

数据结构中的 FIFO 方法

FIFO 方法的应用

1）数据结构

线性队列

线性队列的实现方法

使用数组实现线性队列

使用队列（数组实现）在 C 编程语言中实现 FIFO 方法

使用数组（队列实现）在 C++ 编程语言中实现 FIFO 方法

使用队列在 Java 编程语言中实现 FIFO 方法

使用队列在 Python 编程语言中实现 FIFO 方法

使用队列在 C# 编程语言中实现 FIFO 方法

使用队列在 JavaScript 编程语言中实现 FIFO 方法

使用栈（队列实现）在 C 编程语言中实现 FIFO 方法

使用栈（队列实现）在 C++ 编程语言中实现 FIFO 方法

循环队列

使用循环队列实现 FIFO 方法

使用数组实现循环队列

使用循环队列在 C 编程语言中实现 FIFO 方法

使用结构（循环队列实现）在 C++ 编程语言中实现 FIFO 方法

使用数组（循环队列）在 Java 编程语言中实现 FIFO 方法

使用数组（循环队列）在 Python 编程语言中实现 FIFO 方法

使用链表（循环队列）在 C 编程语言中实现 FIFO 方法

使用链表（循环队列）在 C++ 编程语言中实现 FIFO 方法

使用链表（循环队列）在 Java 编程语言中实现 FIFO 方法

使用链表（循环队列）在 Python 编程语言中实现 FIFO 方法

循环队列相对于线性队列的优点

相关帖子

二叉树枚举

经过恰好 K 步到达某个位置的方法数

使用堆的时间复杂度

给定父数组时 N 元树的高度

三向链表

将中缀表达式转换为前缀表达式

仅允许对给定数组进行旋转，求 Sum(i*arr[i]) 的最大值

未排序数组的平均值和中位数程序

Tango Tree 数据结构

滑动子数组的魅力

订阅 Tpoint Tech

联系信息

关注我们