DEQUE IN C++
- deque is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end.
The complexity (efficiency) of common operations on deques is as follows: - Random access - constant O(1)
- Insertion or removal of elements at the end or beginning - constant O(1)
- Insertion or removal of elements - linear O(n)
Formally Deque supports all the functions that vector supports
The Difference b/w deque & vector : Deques do not guarantee that their elements are contiguous in memory so that accessing may not be as efficient.
Ways to declare a deque
Syntax
deque<int> dq; /* Empty */
deque<int> dq( size ); /* deque with size 'size' */
deque<int> dq( size, value ); /* deque with size 'size' and all elements with value 'value' */
deque<int> dq = { value1, value2, value3,...,valueN}; /* deque with N values */Note : Similar syntax for char long long int float double long double and some other data types include user defined data types.
Important Functions :
dq.push_back( ele ); /* adds an element 'ele' at the end and size of deque increases by 1 TC - 𝓞(1)*/
dq.pop_back(); /* Remove element at end TC - 𝓞(1)*/
dq.push_front( ele ); /* adds an element 'ele' at the front and size of deque increases by 1 TC - 𝓞(1)*/
dq.pop_front(); /* Remove element at front TC - 𝓞(1)*/
dq.size(); /* returns the size of deque TC - 𝓞(1)*/
dq.empty(); /* returns true if deque is empty TC - 𝓞(1)*/
dq.front(); or dq[0]; /* Accessing first element TC - 𝓞(1)*/
dq.back(); or dq[dq.size()-1]; /* Accessing last element TC - 𝓞(1) */
dq[i]; /* Accessing element at i'th index (0-based) TC - 𝓞(1)*/
dq.at(i); /* Accessing element at i'th index (0-based) TC - 𝓞(1)*/Note : For more functions refer to vector methods writtten here.
Comments (0)
