622. Design Circular Queue
Разработайте свою реализацию круговой очереди. Круговая очередь - это линейная структура данных, в которой операции выполняются по принципу FIFO (First In First Out), а последняя позиция соединяется с первой, образуя круг. Одно из преимуществ круговой очереди заключается в том, что мы можем использовать пространство перед очередью. В обычной очереди, когда очередь становится полной, мы не можем вставить следующий element, даже если перед очередью есть свободное место. Но с помощью круговой очереди мы можем использовать пространство для хранения новых значений. Implementierung класса MyCircularQueue: MyCircularQueue(k) Инициализирует объект с размером очереди k. int Front() Получает первый element из очереди. Если очередь пуста, returnsся -1. int Rear() Получает последний element из очереди. Если очередь пуста, returnsся -1. boolean enQueue(int value) Вставляет element в циклическую очередь. returns true, если операция прошла успешно. boolean deQueue() Удаляет element из круговой очереди. returns true, если операция выполнена успешно. boolean isEmpty() Проверяет, пуста ли круговая очередь. boolean isFull() Проверяет, заполнена ли круговая очередь. Вы должны решить проблему без использования встроенной структуры данных очереди в вашем языке программирования.
Beispiel:
Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]
C# Lösung
zugeordnet/originalpublic class MyCircularQueue {
private int[] queue;
private int front;
private int rear;
private int size;
private int capacity;
public MyCircularQueue(int k) {
queue = new int[k];
front = 0;
rear = -1;
size = 0;
capacity = k;
}
public bool enQueue(int value) {
if (isFull()) {
return false;
}
rear = (rear + 1) % capacity;
queue[rear] = value;
size++;
return true;
}
public bool deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
size--;
return true;
}
public int Front() {
return isEmpty() ? -1 : queue[front];
}
public int Rear() {
return isEmpty() ? -1 : queue[rear];
}
public bool isEmpty() {
return size == 0;
}
public bool isFull() {
return size == capacity;
}
}C++ Lösung
Auto-Entwurf, vor dem Einreichen prüfen#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class MyCircularQueue {
private vector<int>& queue;
private int front;
private int rear;
private int size;
private int capacity;
public MyCircularQueue(int k) {
queue = new int[k];
front = 0;
rear = -1;
size = 0;
capacity = k;
}
public bool enQueue(int value) {
if (isFull()) {
return false;
}
rear = (rear + 1) % capacity;
queue[rear] = value;
size++;
return true;
}
public bool deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
size--;
return true;
}
public int Front() {
return isEmpty() ? -1 : queue[front];
}
public int Rear() {
return isEmpty() ? -1 : queue[rear];
}
public bool isEmpty() {
return size == 0;
}
public bool isFull() {
return size == capacity;
}
}Java Lösung
zugeordnet/originalpublic class MyCircularQueue {
private int[] queue;
private int front;
private int rear;
private int size;
private int capacity;
public MyCircularQueue(int k) {
this.queue = new int[k];
this.front = 0;
this.rear = -1;
this.size = 0;
this.capacity = k;
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
rear = (rear + 1) % capacity;
queue[rear] = value;
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
size--;
return true;
}
public int Front() {
return isEmpty() ? -1 : queue[front];
}
public int Rear() {
return isEmpty() ? -1 : queue[rear];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
}JavaScript Lösung
zugeordnet/originalclass MyCircularQueue {
constructor(k) {
this.queue = Array(k).fill(-1);
this.front = 0;
this.rear = -1;
this.size = 0;
this.capacity = k;
}
enQueue(value) {
if (this.isFull()) {
return false;
}
this.rear = (this.rear + 1) % this.capacity;
this.queue[this.rear] = value;
this.size++;
return true;
}
deQueue() {
if (this.isEmpty()) {
return false;
}
this.front = (this.front + 1) % this.capacity;
this.size--;
return true;
}
Front() {
return this.isEmpty() ? -1 : this.queue[this.front];
}
Rear() {
return this.isEmpty() ? -1 : this.queue[this.rear];
}
isEmpty() {
return this.size === 0;
}
isFull() {
return this.size === this.capacity;
}
}Python Lösung
zugeordnet/originalclass MyCircularQueue:
def __init__(self, k: int):
self.queue = [-1] * k
self.front = 0
self.rear = -1
self.size = 0
self.capacity = k
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
self.rear = (self.rear + 1) % self.capacity
self.queue[self.rear] = value
self.size += 1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.front = (self.front + 1) % self.capacity
self.size -= 1
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self.queue[self.front]
def Rear(self) -> int:
return -1 if self.isEmpty() else self.queue[self.rear]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacityGo Lösung
zugeordnet/originalpackage main
type MyCircularQueue struct {
queue []int
front int
rear int
size int
capacity int
}
func Constructor(k int) MyCircularQueue {
return MyCircularQueue{
queue: make([]int, k),
front: 0,
rear: -1,
size: 0,
capacity: k,
}
}
func (this *MyCircularQueue) enQueue(value int) bool {
if this.isFull() {
return false
}
this.rear = (this.rear + 1) % this.capacity
this.queue[this.rear] = value
this.size++
return true
}
func (this *MyCircularQueue) deQueue() bool {
if this.isEmpty() {
return false
}
this.front = (this.front + 1) % this.capacity
this.size--
return true
}
func (this *MyCircularQueue) Front() int {
if this.isEmpty() {
return -1
}
return this.queue[this.front]
}
func (this *MyCircularQueue) Rear() int {
if this.isEmpty() {
return -1
}
return this.queue[this.rear]
}
func (this *MyCircularQueue) isEmpty() bool {
return this.size == 0
}
func (this *MyCircularQueue) isFull() bool {
return this.size == this.capacity
}Algorithm
Используйте Array фиксированного размера для хранения elementов очереди и два указателя: front для отслеживания начала очереди и rear для отслеживания конца очереди.
Реализуйте методы enQueue и deQueue для вставки и удаления elementов, обновляя указатели по круговому принципу.
Реализуйте методы Front, Rear, isEmpty и isFull для доступа к elementам и проверки состояния очереди.
😎
Stellen zu dieser Aufgabe
aktive Stellen with overlapping task tags are angezeigt.