software development, devops, and other drivel
Tree lined path

Queue Data Structure

A Queue is a linear data struture that is open at both ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). In can be thought of as a queue of poeple waiting to get tickets, the first person in line will be the first one called to purchase their ticket.

Waiting in Queue
Waiting in Queue

Basic Operations

  • enqueue() − add (store) an item to the queue.

  • dequeue() − remove (access) an item from the queue.

  • peek() − Gets the element at the front of the queue without removing it.

  • isEmpty() − Checks if the queue is empty.


List (Array) Implementation

Linked List Implementation

type DataType interface{}

type node struct {
	data DataType
	next *node

type Queue struct {
	head *node
	tail *node
	length int

func (q *Queue) IsEmpty() bool {
	return q.length == 0

func (q *Queue) Size() int {
	return q.length

func (q *Queue) Enqueue(d DataType) {
	if q.head == nil {
		q.head = &node{d, nil}
		q.tail = q.head
	} else {
		temp := &node{d, nil}
		q.tail.next = temp
		q.tail = temp

func (q *Queue) Peek() DataType {
	return q.head.data

func (q *Queue) Dequeue() DataType {
	if q.IsEmpty() {
		return nil
	} else {
		temp := q.head.data
		q.head = q.head.next
		return temp

Time Complexity

In the list based implemention shown above the enqueue operation would have an average time complexity of O(1) unless the list needed to be resized in which case the time complexity would become O(n). The dequeue operation however would always be O(n) since all the elements in the list would need to be shifted each time.