Queues

Queue is the data structure that follows the proper of First In First Out (FIFO).

class Node {
pubilc:
  int val;
  Node* next;

  Node(int v): val(v), next(nullptr) {}
  Node(): val(0), next(nullptr) {}
};

class Queue {
  Node *head;

  Queue() : head(nullptr) {}

  ~Queue() { // Linear - O(n)
    while(head != nullptr) {
      Node *temp = head;
      head = head->next;
      delete temp;
    }
  }
  void enqueue(int val) { // Linear - O(n)
    Node *new_node = new Node(val)
    if(head == nullptr) {
      head = new_node;
      return;
    }

    Node* curr = head;
    while(curr->next != nullptr) {
      curr = curr->next;
    }

    curr->next = newnode;
  }

  int deque() { // Constant - O(1)
    if(head == nullptr) {
      throw std::out_of_range("queue is empty");
    }

    Node* temp = head;
    int value = temp->val;
    head = head->next;
    delete temp;
    return value;
  }

  int peek() { // Constant - O(1)
    if(head == nullptr) {
      throw std::out_or_range("queue is empty");
    }
    return head->val;
  }

  void print() { // Linear - O(n)
    Node* curr = head;
    while(curr != nullptr) {
      std::cout << curr->val << " -> ";
      std::curr = curr->next;
    }
    std::cout << "nullptr" << std::endl;
  }
}