6.用java代码实现队列
时间: 2023-05-08 07:02:01 浏览: 77
队列是一种常见的数据结构,简单来说,就是先进先出(FIFO)的操作方式。在Java中,可以使用数组或链表来实现队列。下面我们分别介绍这两种方式的实现方法。
1. 使用数组实现队列
首先我们需要定义一个数组来表示队列,然后定义队列的头尾指针front和rear,初始值都为0。当往队列中插入元素时,我们先将元素插入到队列尾部,即arr[rear] = element,然后将rear指针向后移动一个位置,即rear++。当从队列中取出元素时,我们先将队列头部的元素取出,即element = arr[front],然后将front指针向后移动一个位置,即front++。
下面是使用数组实现队列的Java代码:
```
public class ArrayQueue {
private int capacity;
private int[] arr;
private int front;
private int rear;
public ArrayQueue(int capacity) {
this.capacity = capacity;
this.arr = new int[capacity];
this.front = 0;
this.rear = 0;
}
public void enqueue(int element) {
if (rear == capacity) {
throw new RuntimeException("Queue is full.");
}
arr[rear] = element;
rear++;
}
public int dequeue() {
if (front == rear) {
throw new RuntimeException("Queue is empty.");
}
int element = arr[front];
front++;
return element;
}
public int size() {
return rear - front;
}
public boolean isEmpty() {
return front == rear;
}
}
```
2. 使用链表实现队列
使用链表来实现队列的话,则不需要像数组一样限制队列大小,我们只需要定义一个指向队列头部的指针head和指向队列尾部的指针tail,对于每个元素,我们将其插入到tail的后面,并将tail指针向后移动一个位置,当从队列中取出元素时,我们将head指针向后移动一个位置,并返回head指向的元素。
下面是使用链表实现队列的Java代码:
```
public class LinkedQueue {
private Node head;
private Node tail;
private int size;
private class Node {
private int data;
private Node next;
public Node(int data) {
this.data = data;
}
}
public void enqueue(int element) {
Node newNode = new Node(element);
if (tail == null) {
head = tail = newNode;
} else {
tail.next = newNode;
tail = tail.next;
}
size++;
}
public int dequeue() {
if (head == null) {
throw new RuntimeException("Queue is empty.");
}
int element = head.data;
head = head.next;
size--;
if (head == null) {
tail = null;
}
return element;
}
public int size() {
return size;
}
public boolean isEmpty() {
return head == null;
}
}
```
以上两种实现方式各有优缺点,在实际开发中应该根据实际需求选择最适合的方法。