使用循环数组实现双端队列

2024年8月28日 | 阅读 12 分钟

在通过循环数组实现双端队列之前，我们先来了解一下什么是队列？

队列是一种有序的元素集合，其中新元素添加到一端，称为“队尾”，而现有元素则从另一端移除，称为“队头”。当一个元素加入队列时，它会从队尾开始，逐渐向队头移动，等待下一个元素被移除。队列中最新添加的元素必须等到它到达集合的末尾。最先进入集合的元素位于队头。FIFO，即先进先出，是这种排序方式的另一种说法。“先到先得”也是对它的另一种称呼。

操作系统使用各种不同的队列来管理计算机内的进程。下一个任务通常使用队列方法进行调度，以尽快运行程序，同时服务尽可能多的人。此外，当我们输入时，按键有时会比屏幕上的字符还要多，这是因为计算机目前正在处理其他任务。按键会排入缓冲区，稍后按正确顺序显示在屏幕上。

入队是将元素添加到队列尾部的过程，而出队是从队列头部移除元素的过程。其他操作，如查看或获取队头元素的操作，可以在不移除元素的情况下返回即将出队的下一个元素的值。

现在我们来理解双端队列。双端队列（deque，double-ended queue）是与队列功能相似的有序元素集合。它有两个端，队头和队尾，集合中的元素保持不变。双端队列的独特之处在于其对添加和移除元素的无限制性。新元素可以添加到队头或队尾。现有元素也可以从任一端移除。值得注意的是，虽然双端队列可以模仿栈和队列的许多属性，但它不强制要求这些数据结构强制执行的 LIFO（后进先出）和 FIFO（先进先出）顺序。这取决于您如何一致地使用添加和移除操作。以下是双端队列数据结构支持的各种操作：

insertFront(x): insertFront() 函数将在双端队列的队头插入元素 x。该函数有一个参数，表示我们要添加到双端队列数据结构队头的数据。
insertRear(x): insertRear() 函数将在双端队列的队尾插入元素 x。该函数有一个参数，表示我们要添加到双端队列数据结构队尾的数据。
deleteFront(): deleteFront() 函数将从双端队列的队头移除一个元素。
deleteRear(): deleteRear() 函数将从双端队列的队尾移除一个元素。
getFront(): getFront() 函数将返回双端队列队头的元素。
getRear(): getRear() 函数将返回双端队列队尾的元素。
isEmpty(): isEmpty() 函数将返回双端队列是否为空。
isFull(): isFull() 函数将返回双端队列是否已满。

Java 代码

现在，我们用 Java 编程语言编写代码，使用循环数组创建一个双端队列数据结构。

// A sample Java program to create a Deque Data structure using a circular array in Java

import java.util.Scanner;

// A class named Deque is created that have all the functions of the Deque Data structure in it 
class Deque
{
	// a static final Integer variable named MAX is created and initialized with 100 that will represent the total maximum capacity of the Deque Data structure
	static final int MAX = 100;
	// An Integer array named arr is created that will be the circular array
	int arr[];
	// An Integer variable named front is created that will represent the front of the Deque Data structure
	int front;
	// An Integer variable named rear is created that will represent the rear of the Deque Data structure
	int rear;
	// An Integer variable named size is created that will represent the size of the Deque Data structure
	int size;
	
	// A constructor of the Deque is created that will be used to initialize various variables of the Deque class
	public Deque(int size)
	{
	
		// The arr array is initialized with the MAX value defined earlier
		arr = new int[MAX];
		front = -1;
		rear = 0;
		this.size = size;
	}

	// The isFull() function will return whether or not the Deque is full or not
	// If the capacity of the Deque is full, then it will return True, and if there is capacity remaining, False will be returned
	boolean isFull()
	{
		return ((front == 0 && rear == size-1)||
			front == rear+1);
	}

	// The isEmpty() function will return whether or not the Deque is empty
	boolean isEmpty ()
	{
		return (front == -1);
	}


	// The insertFront() function will insert an element x at the front of Deque. There is one parameter to the insertFront() function representing the data that we want to add to the front of the Deque data structure.
	void insertfront(int key)
	{
		// check whether Deque if full or not
		if (isFull())
		{
			System.out.println("Overflow");
			return;
		}

		// If queue is initially empty
		if (front == -1)
		{
			front = 0;
			rear = 0;
		}
		
		// front is at first position of queue
		else if (front == 0)
			front = size - 1 ;

		else // decrement front end by '1'
			front = front-1;

		// insert current element into Deque
		arr[front] = key ;
	}


	// The insertRear() function will  insert an element x at the rear of Deque. There is one parameter to the insertRear() function representing the data that we want to add to the rear of the Deque data structure.
	void insertrear(int key)
	{
		if (isFull())
		{
			System.out.println(" Overflow ");
			return;
		}

		// If queue is initially empty
		if (front == -1)
		{
			front = 0;
			rear = 0;
		}

		// rear is at last position of queue
		else if (rear == size-1)
			rear = 0;

		// increment rear end by '1'
		else
			rear = rear+1;
		
		// insert current element into Deque
		arr[rear] = key ;
	}


	// The deleteFront() function will delete an element from the front of Deque
	void deletefront()
	{
		// check whether Deque is empty or not
		if (isEmpty())
		{
			System.out.println("Queue Underflow\n");
			return ;
		}

		// Deque has only one element
		if (front == rear)
		{
			front = -1;
			rear = -1;
		}
		else
			// back to initial position
			if (front == size -1)
				front = 0;

			else // increment front by '1' to remove current
				// front value from Deque
				front = front+1;
	}

	// The deleteRear() function will delete an element from the rear of Deque
	void deleterear()
	{
		if (isEmpty())
		{
			System.out.println(" Underflow");
			return ;
		}

		// Deque has only one element
		if (front == rear)
		{
			front = -1;
			rear = -1;
		}
		else if (rear == 0)
			rear = size-1;
		else
			rear = rear-1;
	}

	// The getFront() function will return the element present at the front of Deque
	int getFront()
	{
		// check whether Deque is empty or not
		if (isEmpty())
		{
			System.out.println(" Underflow");
			return -1 ;
		}
		return arr[front];
	}

	// The getRear() function will return the element present at the rear of Deque
	int getRear()
	{
		// check whether Deque is empty or not
		if(isEmpty() || rear < 0)
		{
			System.out.println(" Underflow\n");
			return -1 ;
		}
		return arr[rear];
	}

	void printDeque(){
		for (int o :arr){
			if (o != 0)
				System.out.print(o + " ");
		}
		System.out.println();
	}


	// main function is written to call all the functionalities functions of the Deque Data structure written above
	public static void main(String[] args)
	{
		
		Deque dq = new Deque(5);
		Scanner sc = new Scanner(System.in);

		int data;
		int count = 0;
	  	char ch;

            // Do-while loop
            // Do part for performing actions
            do
            // Menu is displayed
            // Users enter 'y' to continue 'n' if
            // entered by user , the program terminates

            {
                  // Menu
                  // Display messages
                  System.out.println("Please Choose one of the Operations::");
                  System.out.println("1. To Insert Data at the Front of Deque.");
                  System.out.println("2. To Insert Data at the Rear of Deque.");
                  System.out.println("3. To Print Data from the Front of Deque.");
                  System.out.println("4. To Print Data from the Rear of Deque.");
                  System.out.println("5. To Delete Data from the Front of Deque.");
                  System.out.println("6. To Delete Data from the Rear of Deque.");
                  System.out.println("7. To print the Deque.");                 

                  int choice;
                  choice = sc.nextInt();

                  // Switch case
                  switch (choice) {

                  // Case 1
                  case 1:

                        System.out.println("Enter the data :\n");
                        data = sc.nextInt();
                        dq.insertfront(data);
                        // Display message
                        System.out.println("Data Added Successfully.\n");
                        // Break statement to terminate a case
                        break;

                   // Case 2
                  case 2:

                        System.out.println("Enter the data :\n");
                        data = sc.nextInt();
                        dq.insertrear(data);
                        // Display message
                        System.out.println("Data Added Successfully.\n");
                        // Break statement to terminate a case
                        break;


                   // Case 3
                  case 3:

                        System.out.println("Data at front:" + dq.getFront() + "\n");
                        break;

                  // Case 4
                  case 4:

                        System.out.println("Data at rear:" + dq.getRear() + "\n");
                        break;

                  // Case 5
                  case 5:

                        dq.deletefront();
                        System.out.println("Data deleted from the front.");
                        break;
                 
                 // Case 6
                  case 6:

                        dq.deleterear();
                        System.out.println("Data deleted from the rear.");
                        break;


                   // Case 7
                  case 7:

                        System.out.println("Data in Deque::");
                        dq.printDeque();
                        break;


                  default:
                        // Print statement
                        System.out.println("Please enter a valid option from the menu to proceed further.\n \n");
                        // Break statement
                        break;
                  }


                  System.out.println("\nType [N or n] to terminate the program.\nType [Y or y] to continue the program.\n");
                  sc.nextLine();
                  ch = sc.nextLine().charAt(0);
                  
            } while (!(ch == 'N' || ch == 'n'));

	}
}

输出

上面的代码产生以下输出：

Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
1
Enter the data:

10
Data Added Successfully.


Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
2
Enter the data :

25
Data Added Successfully.


Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
1
Enter the data :

45
Data Added Successfully.


Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
2
Enter the data :

60
Data Added Successfully.


Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
7
Data in Deque::
45 10 25 60 

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
3
Data at front:45


Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
4
Data at rear:60


Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
5
Data deleted from the front.

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
7
Data in Deque::
10 25 60 

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
6
Data deleted from the rear.

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

y
Please Choose one of the Operations::
1. To Insert Data at the Front of Deque.
2. To Insert Data at the Rear of Deque.
3. To Print Data from the Front of Deque.
4. To Print Data from the Rear of Deque.
5. To Delete Data from the Front of Deque.
6. To Delete Data from the Rear of Deque.
7. To print the Deque.
7
Data in Deque::
10 25

Type [N or n] to terminate the program.
Type [Y or y] to continue the program.

n

在上面的代码中，我们首先创建了一个双端队列数据结构，并使用各自的插入函数从队头和队尾向该双端队列中添加元素。

成功将数据插入双端队列后，下一步是对双端队列数据结构的两个端执行删除操作。有两个函数可以从双端队列的两端删除数据。

每次操作后，我们都使用 printDeque() 函数打印双端队列数据结构的内容，该函数从队头开始打印双端队列的所有内容，直到队尾。为了创建双端队列数据，我们使用了循环数组。

应用

工作窃取算法是一个双端队列如何使用的例子。[6]该技术用于调度多个 CPU 之间的任务。为每个处理器维护一个单独的双端队列，其中包含要执行的线程。处理器从双端队列中获取第一个元素来启动下一个线程（使用“移除第一个元素”的双端队列操作）。如果当前线程分叉，则当前线程被放回双端队列的队头（“在队头插入一个元素”），并启动一个新线程。

当其中一个处理器完成了其自身线程的执行（即其双端队列为空）时，它可以从另一个处理器“窃取”一个线程，方法是检索另一个处理器双端队列的最后一个元素（“移除最后一个元素”）并执行它。英特尔的 Threading Building Blocks (TBB) 包使用工作窃取机制进行并行编程。

下一主题链表中的旋转操作

使用循环数组实现双端队列

Java 代码

应用

联系信息

关注我们

教程

面试题

在线编译器

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 选择题

其他

使用循环数组实现双端队列

Java 代码

应用

相关帖子

双指针技术

Morris 后序遍历

后序遍历

查找每个经理下的员工数量

翻转使二进制字符串交替的数量

获取二叉树中给定键的层级

树的左视图

数据结构中矩阵中回文路径的数量

AVL 树操作

检查二维矩阵中是否存在可能的路径

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器