Sharing Common Knowledge about C++ Queues

A queue is a commonly used data structure that follows the First In First Out (FIFO) principle.Practical tips for competitions:1. Use arrays to simulate queues (better performance)2. Prefer using the STL queue (clearer code)STL Library

#include<queue>queue<int>Q;empty();// Returns true if the queue is emptypop();// Removes the front elementpush();// Adds an element to the backsize();// Returns the number of elements in the queuefront();// Returns the front element

Pair array — replaces structures, binding two elements

pair<int,double>p1;pair<int,double>p2(1,2.0);Access the two elements in the pair using first and second:pair<int,double>p1;p1.first=1;p2.second=2;printf("%d %lf\n",p1.first,p2.second);Assign values using make_pairp1=make_pair(1,2)

Priority Queue — elements in the queue have priorities: max heap and min heap

#include<queue>priority_queue<int>Q;// The priority queue implemented with a max heap is sorted from largest to smallestpriority_queue<int,vector<int>,greater<int> > q;// Min heap: In a min heap, the value of the parent node is always less than or equal to that of its child nodes. In other words, in a min heap, the root node is the smallest node. The priority queue implemented with a min heap is sorted from smallest to largestQ.top();// Returns the top element of the max heap (does not delete it)// If using a min heap, you can take the negative value, -Q.top()Q.pop();Q.size();Q.empty();// Returns 1 when the queue is empty// Note: The complexity of inserting and deleting in a priority queue is O(log2n), and the internal implementation is a binary heap

One difference between a priority queue and a regular queue is that if the inserted node is of a structure type, the comparison operator function must be overloaded in the structure.

struct Node{int key;char ch;// Only < overloaded operator function, if < is changed to > why it doesn't work, error C2784friend bool operator <(Node node1,Node node2) {// < arranges from largest to smallest, > arranges from smallest to largestreturn node1.key<node2.key;}friend bool operator >(Node node1,Node node2){return node1.key<node2.key;}}

Deque — allows enqueue and dequeue operations from both ends

deque<int>Q;Q.push_back();// Inserts an element at the backQ.pop_back();Q.push_front();// Inserts an element at the frontQ.pop_front();Q.back();// Returns the back elementQ.front();// Returns the front elementQ.clear();// Clears all elements in the queueQ.empty();// Checks if the queue is emptyQ.size();

Example Problem

Simulating a Queue

#include<iostream>#include<queue>using namespace std;queue<int>Q;int n,x;string s;int main(){    cin>>n;    for(int i=0;i<n;i++){        cin>>s;        if(s=="push"){            cin>>x;            Q.push(x);        }else if(s=="pop"){            Q.pop();        }else if(s=="empty"){            if(Q.empty()){                cout<<"YES"<<endl;            }else{                cout<<"NO"<<endl;            }        }else if(s=="query"){            cout<<Q.front()<<endl;        }    }    return 0;}

Weekend Dance Party

#include<iostream>#include<queue>using namespace std;queue<pair<int,int>>Q;int x,y,z;int main(){    cin>>x>>y>>z;    Q.push(make_pair(1,1));    for(int i=0;i<z;i++){        int m=Q.front().first;        int n=Q.front().second;        cout<<m<<" "<<n<<endl;        Q.pop();        m=1+m%x;        n=1+n%y;        Q.push(make_pair(m,n));    }    return 0;}

Circle Counting

#include<iostream>#include<queue>using namespace std;queue<int>Q;int n,m,cnt,x;int main(){    cin>>n>>m;    for(int i=1;i<=n;i++){        Q.push(i);    }    while(n!=0){        cnt++;        x=Q.front();        Q.pop();        if(cnt!=m){            Q.push(x);        }else{            cout<<x<<" ";            cnt=0;            n--;        }    }    return 0;}

Knowledge · Exploration · Growth