queue

Time and Space Complexity of Queue

This article is about the analysis of time and space complexity of queue operations. With this, we will also learn what the time and space complexity are and how we can calculate the time and space complexity of an algorithm.

Algorithms

Delete middle element of Queue

In this article, we discuss how to delete the middle element of a queue without using other data structures. We have explained both iterative and recursive approach.

Algorithms

Invert / Reverse a Binary Tree [3 methods]

Inverting a binary tree is one of the most common questions asked in the interviews of many companies. In this article, we will see in detail as to how one can understand and tackle this task of inverting a binary tree using recursion, stack and queue.

Algorithms

Shortest Subarray with at least K as sum

In this problem, we find the length of the Shortest Subarray with at least K as sum. This can be solved in O(N) time complexity. This brings in the ideas of Monotonic Queue and Sliding Window.

Algorithms

132 Pattern Problem [Solved]

In this article, we have explained what is 132 pattern problem and have discussed 3 different approaches to solve it in linear time O(N) where brute force approach takes O(N^3) time.

Algorithms

Different ways to sort a Queue

We will be discussing 4 different ways to sort a queue. This involves sorting a Queue using auxiliary array, O(1) space, using recursion and using a stack.

Algorithms

Reverse first K elements of Queue using Stack

To reverse the first K elements of a queue, we can use an auxiliary stack. We push the first k elements in the stack and pop() them out so and add them at the end of the queue.

Algorithms

Next Larger / Smaller element in Array (using Monotonic Queue)

In this problem, we are given an array and our task is to find the next larger/ smaller element for each element in the array. We have covered brute force approach and Monotonic Queue.

Algorithms

Implementing Priority Queue using Linked List

We demonstrated the approach to Implement a Priority Queue using Linked List and support all operations like push and pop efficiently.

Algorithms

Maximal Rectangle problem (using Monotonic queue)

We have solved the maximal rectangle problem using Monotonic queue. In this problem we are given a matrix consisting of only 0's and 1's, we need to find the largest rectangle consisting of only 1's and return its area.

Algorithms

Monotonic Queue (with Daily Temperatures & Largest Rectangle in Histogram)

Monotonic queue is a data structure where the data is entirely in non-decreasing order or entirely in non-increasing order. It is generally used for optimizing dynamic programming techniques.

Data Structures

Applications of Queue

We have covered all applications of queue. Some of the algorithms were it is used are CPU Scheduling (First-Come-First-Serve), Breadth First Search Traversal, Level Order Traversal of a tree, Edmonds Karp Algorithm, Dinic's Algorithm and Fibonacci Heap. We have explored some of the problems as well.

Data Structures

Types of Queue and their implementations

Queue is a FIFO (first in first out) data structure. The different types of queues are linear queue, circular queue, priority queue and deque. We have explored the types along with implementations.

Algorithms

Queue using Array

In this article, we have explored how to implement queue using array and explored various operations such as enqueue, dequeue, display, front and size. We have provided implementation in C and Python as well.

Software Engineering

Learn to use Queue in Java Collections Framework

In this article, we will take a look at how to use the Queue class in Java Collections library. This is useful as one can directly use queue without natively implementing it

Data Structures

Priority Queue

Priority queue is an abstract data type which is like a queue or stack data structure with each element having a priority assigned to it. In priority queue, an element with highest priority assigned is served first, if two elements have same priority then they are served according to enqueue order

Data Structures

Implementing Stack using queues in two ways

A stack is based on the principle of Last-in-First-Out(LIFO). It is commonly used abstract data type with two major operations, namely pop and push. Push() and pop() are carried out in the topmost element, which is the item most recently added to the stack. Push operation adds an element to stack

C++

Queue in C++ STL

Queue in the STL of C++ is a dynamically resizing container to implement the queue data structure. It is a sequential linear container which follows the First In First Out(FIFO) arrangement. We explore the various functions like empty, size, swap, emplace, front, back, push and pop operations

Data Structures

Circular Queue / Ring Buffer / Circular Buffer

Circular Queue (Ring Buffer) is also a linear data structure, which follows the principle of FIFO(First In First Out), but instead of ending the queue at the last position, it again starts from the first position after the last, hence making the queue behave like a circular data structure.

Data Structures

Implementing Queue using Stack in two ways

Queue is an abstract data structure similar to Stacks. Queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). For implementing queue using stack, one method is to make dequeue costly and other is to make enqueue costly

Algorithms

Cartesian tree sorting

Cartesian tree sorting, also called Levcopoulos Petersson algorithm is an adaptive sorting algorithm, i.e. it performs much better on a partially sorted data. It needs two data structures a Cartesian tree and a priority queue. The algorithm here uses min-heap Cartesian tree to give a sorted sequence

Data Structures

Implementing Queue using Linked list

A queue (First in First out) is an ordered collection of items where the addition of new items happens at one end, called the rear, and removal of existing items occurs at the other end called front. It can be implemented using Linked Lists which brings many advantages over array implementation

Data Structures

Queue is a linear data structure that can be used to store data in order by imposing rules on data insertion and deletion. It has found immense use and can be implemented using arrays and linked lists. The operations include enqueue and dequeue which are of O(1) time complexity with space of O(N)

double ended queue

Double Ended Queue (Deque)

A double ended queue also called as deque (pronounced as ‘deck’ or ‘dequeue’) is a list in which the elements can be inserted or deleted at either end in constant time.