BastterCode monthly challenge 2 - 622 - Design Circular Queue
comentada em 15/04/2023 14:06

O enunciado menciona "You must solve the problem without using the built-in queue data structure in your programming language."

Embora lista não seja o queue do Python per se, acho que usar o `pop()` e índices ([-1]) não vale, né?

Ref.: 5. Data Structures — Python 3.11.3 documentation

Já achei um comentário para uma submissão parecida com a minha:

"This is not a circular queue. It's a normal queue and it's also very inefficient (q.pop(0) will move all of the elements to the left)"

Pessoal lá no LeetCode espinafra que nem na Bastter  

Ou seja, de volta à prancheta 

Usando vetores. Depois quero estudar pra tentar fazer de outras formas. 

class MyCircularQueue {
public:
  
    int rear = -1;
    int count = 0;
    int front = 0;
    vector<int> q {};
  
    MyCircularQueue(int k) {q.resize(k, -1);}
    
    bool enQueue(int value) {
      if (count < q.size()) {
        if (rear != q.size()-1){
          q[rear+1] = value;
          rear++;
        }
        else {
          q[0] = value;
          rear = 0;
        }   
        count++;
        return true;
      }
      return false;
    }
    
    bool deQueue() {
      if (count > 0) {
        q[front] = -1;
        if (front < q.size()-1) front++;
        else front = 0;
        count--;
        return true;
      }
      return false;
    }
    
    int Front() {
      if (count > 0) return q[front];
      return -1;
    }
    
    int Rear() {
      if (count > 0) return q[rear];
      return -1;
    }
    
    bool isEmpty() {
     if (count == 0) return true;
     return false;
    }
    
    bool isFull() {
      if (count == q.size()) return true;
      return false;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */?

 

Agora que estou de férias voltei a ler os tópicos daqui da Bastter, muito legal esses desafios, fiz uma versão também:

class MyCircularQueue {
    int* queue;
    int size;

    int countItems;
    int firstIndex;
    int lastIndex;

public:
    MyCircularQueue(int k) {
        countItems = firstIndex = lastIndex = 0;
        size = k;
        queue = new int[size];
    }

    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }

        if (isEmpty()) {
            queue[firstIndex] = value;
        } else {
            int nextIndex = (lastIndex + 1) % size;
            queue[nextIndex] = value;

            lastIndex = nextIndex;
        }

        ++countItems;

        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }

        firstIndex = (firstIndex + 1) % size;
        --countItems;

        if (isEmpty()) {
            lastIndex = firstIndex;
        }

        return true;
    }
    
    int Front() {
        if (isEmpty()) {
            return -1;
        }

        return queue[firstIndex];
    }
    
    int Rear() {
        if (isEmpty()) {
            return -1;
        }

        return queue[lastIndex];
    }
    
    bool isEmpty() {
        return countItems == 0;
    }
    
    bool isFull() {
        return countItems == size;
    }
};

@Giovanni

O desafio semanal ficou como porto inseguro, não dá pra comentar lá. 

public class MyCircularQueue {

    int head;
    int count;
    int size;
    int [] data;
    
    public MyCircularQueue(int k) {
        this.head = 0;
        this.count = 0;
        this.size = k;
        this.data = new int [k];
    }
    
    public bool EnQueue(int value) {
        if (IsFull()) return false;
              
        int tail = (head + count) % size;
        data[tail] = value;
        count++;
              
        return true;
    }
    
    public bool DeQueue() {
        if (IsEmpty()) return false;
        
        head = (head + 1) % size;
        count--;
        return true;
    }
    
    public int Front() {
        if (IsEmpty()) return -1;
        
        return data[head];
    }
    
    public int Rear() {
        if (IsEmpty()) return -1;
        
        int tail = (head + count - 1) % size;
        return data[tail];
    }
    
    public bool IsEmpty() {
        return count == 0;
    }
    
    public bool IsFull() {
        return count == size;
    }
}

C#

postado por @PMHM em 06/04/2023 19:04

Já achei um comentário para uma submissão parecida com a minha:

"This is not a circular queue. It's a normal queue and it's also very inefficient (q.pop(0) will move all of the elements to the left)"

Pessoal lá no LeetCode espinafra que nem na Bastter  

Ou seja, de volta à prancheta 

"You must solve the problem without using the built-in queue data structure in your programming language. "
Não pode resolver nem mesmo usando uma Queue da linguagem!

Use outra estrutura. Use vetores, arrays ou linked lists. 

Dá pra resolver com array em O(1)

postado por @oxe em 07/04/2023 20:34

Usando vetores. Depois quero estudar pra tentar fazer de outras formas. 

class MyCircularQueue {
public:
  
    int rear = -1;
    int count = 0;
    int front = 0;
    vector<int> q {};
  
    MyCircularQueue(int k) {q.resize(k, -1);}
    
    bool enQueue(int value) {
      if (count < q.size()) {
        if (rear != q.size()-1){
          q[rear+1] = value;
          rear++;
        }
        else {
          q[0] = value;
          rear = 0;
        }   
        count++;
        return true;
      }
      return false;
    }
    
    bool deQueue() {
      if (count > 0) {
        q[front] = -1;
        if (front < q.size()-1) front++;
        else front = 0;
        count--;
        return true;
      }
      return false;
    }
    
    int Front() {
      if (count > 0) return q[front];
      return -1;
    }
    
    int Rear() {
      if (count > 0) return q[rear];
      return -1;
    }
    
    bool isEmpty() {
     if (count == 0) return true;
     return false;
    }
    
    bool isFull() {
      if (count == q.size()) return true;
      return false;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */?

Acho que se você declarar o vector como ponteiro e iniciá-lo como new e destruí-lo no destrutor, dá pra fazer sem o resize.

Não sei o quanto impacta o resize...

@FlyCavok

Foi mal pela demora em responder, eu tava viajando e só tive tempo agora.

Eu fiz uma pesquisa sobre essa questão na época da solução.

O resize tem complexidade linear, na diferença entre o tamanho atual e o tamanho a maior ou a menor.

Pensei se teria alguma forma de fazer com construtores de vetores. Mas fui pesquisar no CPP reference e aparentemente quase todos os construtores também têm complexidade linear.

Aparentemente, só há duas formas de construir vetores em C++ com complexidade constante. A primeira é construindo um vetor nulo, sem elementos. A segunda é usando o move para "transferir" um vetor existente inteiramente para o novo vetor, sem fazer cópia. Mas, nesse segundo caso, o vetor já existente teria sido criado também com complexidade linear, então não faz diferença.

Eu não tive tempo de olhar muito a fundo ainda, mas aparentemente é que a alocação do espaço na memória pro vetor é feita com inserção de elementos e essa inserção é linear em size. Então, se o vetor tiver elementos, a complexidade vai ser linear.

No caso do move, ela só é constante porque na prática o que acontece é que você tá apenas trocando o "nome" do vetor já existente. Não há mudança nos valores e nem no espaço na memória, um vetor que era chamado de X agora é chamado de Y quando você move de X pra Y.

Eu tentei essa abordagem que você falou, declarando como ponteiro. Mas deu os mesmos valores no tempo de execução no leetcode. Como esses tempos não são muito confiáveis, acaba que não dá pra saber se faz diferença na prática.

Eu achei que provavelmente a diferença ou não existe ou é muito pequena, pois o principal gargalo do código é justamente essa construção do vetor. Todas as demais funções têm complexidade constante, pois eu acesso diretamente a posição no vetor cujo valor será lido ou escrito. Então, se houvesse uma diferença significativa, provavelmente ela se mostraria no tempo de execução do leetcode após vários "testes".

Mas a verdade é que eu não tenho certeza, ficou a dúvida mesmo.

Usando linked list:

class MyCircularQueue {
public:
    struct CircularQueue {
        int val;
        CircularQueue *next;
        CircularQueue() : val(0), next(nullptr) {}
        CircularQueue(int x) : val(x), next(nullptr) {}
        CircularQueue(int x, CircularQueue *next) : val(x), next(next) {}
    };
    
    CircularQueue* head = new CircularQueue();
    CircularQueue* tail = head;
    int count;
    int size;
    
    MyCircularQueue(int k) {
        count = 0;
        size = k;
        for (int i = 0; i < k; ++i) {
            tail->val = -2;
            if (i + 1 < k) {
                tail->next = new CircularQueue();
                tail = tail->next;
            }
            else {
                tail->next = head;
            }
        }
    }
    
    bool enQueue(int value) {
        if (count < size) {
            tail = tail->next;
            tail->val = value;
            ++count;
            return true;
        }
        return false;             
    }
    
    bool deQueue() {
        if (count > 0) {
            head->val = -2;
            head = head->next;
            --count;
            return true;
        }
        return false;
    }
    
    int Front() {
        if (count > 0) return head->val;
        return -1;
    }
    
    int Rear() {
        if (count > 0) return tail->val;
        return -1;
    }
    
    bool isEmpty() {
        if (count == 0) return true;
        return false;
    }
    
    bool isFull() {
        if (count == size) return true;
        return false;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */?