1.
Introduction
2.
Queue
2.1.
Functions of Queue
2.2.
Time Complexity Analysis
3.
Deque
3.1.
Functions of Deque
3.2.
Time Complexity Analysis
4.
4.1.
How can we implement a Deque?
4.2.
What is the time complexity of operations in Deque implemented using Doubly Linked List?
4.3.
How a Queue can be implemented?
5.
Conclusion
Last Updated: Mar 27, 2024

# Difference Between Queue and Deque in C++

Rhythm Jain
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## Introduction

Design and Implementation based questions are increasingly becoming common in technical interviews. So here we are back again with a question based on the design and functioning of two kinds of data structures called Queue and Deque and what the difference is between them.

## Queue

A Queue is a linear data structure that performs operations in a First In, First Out (FIFO) fashion. It is a container adapter in which elements are inserted at one end of the container and removed from the other.

To use Queue in C++ Standard Template Library, we can use #include<queue> header.

### Functions of Queue

The common queue operations are:

• queue<T> () :creates a new empty queue. It returns an empty queue and does take the data type T as parameter input.
• empty(): Returns true if the queue is empty else return 0.
• size(): Returns the size of the queue.
• push(X): push() function adds the element ‘X’ at the end of the queue.
• pop(): pop() function removes the element from the beginning of the queue and decrements its size by 1.

Source: Wikipedia

### Time Complexity Analysis

queue() : O(1)

empty() : O(1)

size(): O(1)

push(): O(1)

pop(): O(1)

Read More - Time Complexity of Sorting Algorithms

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Deque

Double Ended or Deque Queue is an extended version of the Queue data structure that supports insert and delete operations at both ends. Deque is the short term for "Double-Ended Queue".

To use Deque in C++ Standard Template Library, we can use #include<deque> header.

### Functions of Deque

The common deque operations are:

• deque<T> () :creates a new empty deque. It returns an empty deque and does take the data type T as parameter input.
• empty(): Returns true if the deque is empty else return 0.
• size(): Returns the size of the deque.
• push_front(X): Adds the element ‘X’ at the front of the deque.
• pop_front(): Removes the element from the front of the deque and decrements its size by 1.
• push_back(X): Adds the element ‘X’ at the end of the deque.
• pop_back(): Removes the element from the end of the deque and decrements its size by 1.

You can practice by yourself with the help of Online C++ Compiler for better understanding

### Time Complexity Analysis

deque() : O(1)

empty() : O(1)

size(): O(1)

push_front(): O(1)

pop_front(): O(1)

push_back(): O(1)

pop_back(): O(1)

### How can we implement a Deque?

Deque can be implemented either by a doubly-linked list or by a dynamic array. Each has different time complexities and implementation.

### What is the time complexity of operations in Deque implemented using Doubly Linked List?

The time complexity of all deque operations in a Doubly-linked list implementation of Deque is O(1). Furthermore, given an iterator, the time complexity of insertion or deletion in the middle is O(1). Random access by index, on the other hand, has an O(N) time complexity.

### How a Queue can be implemented?

The queue can be implemented using an Array, stack, or Linked List.

## Conclusion

The design and application of various data structures are the most critical technical and coding interview concepts.

STL includes a number of data structures that are useful in a variety of situations. Real-world applications inspire many data structures. It's a container library with algorithms, iterators, and container classes. It is a parameterized library since it is a generic library.