Queue

Space	Time
	Access	Lookup	Insertion	Deletion
O(n)	O(n)	O(n)	O(1)	O(1)

Definition

Short

Queue is a data structure that follows the First-In-First-Out (FIFO) principle, where elements are added at the end and removed from the front.

Simplified

You're in a candy store with your friends, and you all want to buy your favorite candies. But there's a rule: you can't all rush to the counter at once; you have to form a line. The first one in the line gets their candy first, then the second, and so on until everyone has their candy.

This is just like a queue in a shop.

Detailed

Queue is a data structure where elements are kept in order. It operates on a First-In-First-Out (FIFO) principle, meaning the first element added will be the first to be removed. The main operations are 'enqueue' (adding elements to the end) and 'dequeue' (removing elements from the front). Often, there's also a 'peek' operation that lets you see the front element without removing it. In essence, a queue is a linear, sequential collection.

Practice

Practice

Aspect	Pseudo Code
Enqueue	enqueue(item): queue.add_to_end(item)
Peak	peek(): queue.show_first()
Dequeue	dequeue(): queue.remove_first()

Solution

package main

import (
	"sync"
)

type Queue struct {
	queue []interface{}
	lock  sync.RWMutex
}

func NewQueue() *Queue {
	return &Queue{queue: make([]interface{}, 0)}
}

func (q *Queue) Enqueue(item interface{}) {
	q.lock.Lock()
	defer q.lock.Unlock()

	q.queue = append(q.queue, item)
}

func (q *Queue) Peek() (interface{}, bool) {
	q.lock.RLock()
	defer q.lock.RUnlock()

	if len(q.queue) == 0 {
		return nil, false
	}
	return q.queue[0], true
}

func (q *Queue) Dequeue() (interface{}, bool) {
	q.lock.Lock()
	defer q.lock.Unlock()

	if len(q.queue) == 0 {
		return nil, false
	}
	item := q.queue[0]
	q.queue = q.queue[1:]
	return item, true
}

import java.util.LinkedList;
import java.util.NoSuchElementException;

public class Queue<T> {

  private LinkedList<T> queue = new LinkedList<>();

  public void enqueue(T item) {
    queue.addLast(item);
  }

  public T peek() {
    try {
      return queue.getFirst();
    } catch (NoSuchElementException e) {
      return null;
    }
  }

  public T dequeue() {
    try {
      return queue.removeFirst();
    } catch (NoSuchElementException e) {
      return null;
    }
  }
}

class Queue {
  constructor() {
    this.queue = [];
  }

  enqueue(item) {
    this.queue.push(item);
  }

  peek() {
    return this.queue.length > 0 ? this.queue[0] : null;
  }

  dequeue() {
    return this.queue.length > 0 ? this.queue.shift() : null;
  }
}

class Queue<T> {
    private val queue: MutableList<T> = mutableListOf()

    fun enqueue(item: T) {
        queue.add(item)
    }

    fun peek(): T? {
        return elements.firstOrNull()
    }

    fun dequeue(): T? {
        return elements.removeFirstOrNull()
    }
}

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def peek(self):
        return self.queue[0] if self.queue else None

    def dequeue(self):
        return self.queue.pop(0) if self.queue else None

use std::collections::VecDeque;

pub struct Queue<T> {
    queue: VecDeque<T>,
}

impl<T> Queue<T> {
    pub fn new() -> Self {
        Queue {
            queue: VecDeque::new(),
        }
    }

    pub fn enqueue(&mut self, item: T) {
        self.queue.push_back(item);
    }

    pub fn peek(&self) -> Option<&T> {
        self.queue.front()
    }

    pub fn dequeue(&mut self) -> Option<T> {
        self.queue.pop_front()
    }
}

class Queue<T> {
  private queue: T[] = [];

  enqueue(item: T): void {
    this.queue.push(item);
  }

  peek(): T | undefined {
    return this.queue[0];
  }

  dequeue(): T | undefined {
    return this.queue.shift();
  }
}