посмотреть значение в определенном индексе очереди, очереди и очереди, все 3 в постоянном времени - PullRequest
Новая
       42

посмотреть значение в определенном индексе очереди, очереди и очереди, все 3 в постоянном времени

0 голосов
/ 27 декабря 2018

Мне нужно реализовать очередь, в идеале на Java.Он должен реализовывать методы void push(int value), int pop() и int peek(int index), все в постоянном времени.

Обратите внимание, что для push () мы вводим значение, тогда как для peek () мы вводим индекс.

Мне удалось реализовать push, pop и peek за постоянное время с помощью кругового массива.для поп я возвращаю голову.для толчка я положил после хвоста.Для примера, я просто возвращаю элемент в массиве с переданным индексом.

Моя проблема: если массив не имеет фиксированного размера, как вы перемещаете новый элемент в постоянное время, сохраняя при этом другие 2 значенияпостоянная?Вы должны увеличить размер массива.так как ты это делаешь?

У меня есть 2 вопроса, написанных в виде комментариев в коде;пожалуйста, ответьте на оба вопроса, а также предоставьте обзор кода!

пожалуйста, также помогите мне разрешить этот комментарий в моем коде ниже: / один из способов, которым я могу найти 'if (индекс не между головой и хвостом)) ', циклически переходя от головы к хвосту и обеспечивая появление индекса.Чтобы определить в постоянное время, 1 идея состоит в том, чтобы добавить все признаки в arr к набору, как вы идете.любые другие идеи с постоянным временем? /

Код: 

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Queue q = new Queue();
  }

  public static class Queue<Integer> {

    //capacity == arr.length 
    private int capacity;
    private int head;
    private int tail;
    private int[] arr;
    private int size;

    public Queue () {
      capacity = 16;
      head = tail = 0; 
      arr = new int[capacity]; //0-15
      size = 0;
    }

    public void push(int value) {
      tail = (tail + 1) % capacity;

      //alternatively can look to use 'if (size == capacity)'
      if (tail == head) { 
        resize(); //not constant time when we're @ capacity; help!!
      }
      arr[tail] = i;
      size++;
    }

    private void resize() {
      int[] temp = new int[2 * capacity];
      int index = head;

      //arr.length == capacity
      for (int i = 0; i < capacity; i++) {
        temp[i] = arr[index];
        index = (index + 1) % capacity;
      }
      arr = temp;
      head = 0;
      tail = capacity + 1;
      this.capacity = capacity * 2;
    }


    public int pop() throws Exception{
      if (size == 0) {
        throw new EmptyQueueException();
      }
      int oldHead = head;
      head = (head + 1) % capacity; 
      size--;
      return oldHead; 
    }

    public int peek(int index) {
    /*one way I can think to find 'if (index not between head and tail)' is by looping circularly from head to tail and ensuring that index appears. to determine in constant time, 1 idea is to add all indicies in arr to a set as you go. any other constant time ideas?*/
    if (index not between head and tail) {
      throw new IllegalArgumentException();
    }
    return arr[index];
    }
  }
}
...