Stack, Queue, and Deque Operations

In competitive programming, it is important to have a strong understanding of data structures and their respective operations. Three widely used data structures are stack, queue, and deque. Let's take a closer look at these data structures and their operations in the context of competitive programming using C++.

Stack

A stack is a Last-In-First-Out (LIFO) data structure. Elements are inserted and removed from the same end, called the "top" of the stack. Some key operations associated with a stack include:

1. push(x): Insert element x at the top of the stack.
2. pop(): Remove the element from the top of the stack.
3. top(): Return the element at the top of the stack without removing it.
4. empty(): Check if the stack is empty.
5. size(): Return the number of elements currently in the stack.

In C++, the stack container from the Standard Template Library (STL) provides a convenient implementation of stacks. Here's an example usage:

#include <stack>
using namespace std;

int main() {
    stack<int> st;
    
    st.push(5);
    st.push(10);
    st.push(15);
    
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    
    return 0;
}

Queue

A queue is a First-In-First-Out (FIFO) data structure. Elements are inserted at one end, called the "rear," and removed from the other end, called the "front" of the queue. The following operations are associated with a queue:

1. push(x): Insert element x at the rear of the queue.
2. pop(): Remove the element from the front of the queue.
3. front(): Return the element at the front of the queue without removing it.
4. empty(): Check if the queue is empty.
5. size(): Return the number of elements currently in the queue.

In C++, the queue container from the STL provides an easy implementation of queues. Here's a sample code snippet:

#include <queue>
using namespace std;

int main() {
    queue<int> q;
    
    q.push(5);
    q.push(10);
    q.push(15);
    
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    
    return 0;
}

Deque

Deque, short for "double-ended queue," supports insertion and removal of elements from both ends. It can be used as both a stack and a queue. Key operations for deques include:

1. push_back(x): Insert element x at the rear of the deque.
2. push_front(x): Insert element x at the front of the deque.
3. pop_back(): Remove the element from the rear of the deque.
4. pop_front(): Remove the element from the front of the deque.
5. back(): Return the element at the rear of the deque without removing it.
6. front(): Return the element at the front of the deque without removing it.
7. empty(): Check if the deque is empty.
8. size(): Return the number of elements currently in the deque.

In C++, the deque container from the STL provides a convenient implementation of deques. Here's an example usage:

#include <deque>
using namespace std;

int main() {
    deque<int> dq;
    
    dq.push_back(5);
    dq.push_front(10);
    dq.push_back(15);
    
    while (!dq.empty()) {
        cout << dq.front() << " ";
        dq.pop_front();
    }
    
    return 0;
}

By mastering the operations of stacks, queues, and deques, you will have a strong foundation in competitive programming. These data structures prove to be incredibly useful in solving a wide range of problems efficiently.