Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <deque>
- using namespace std;
- struct DoubleQueue {
- deque<int> first, second;
- void normalize() {
- int target_first_size = (first.size() + second.size() + 1) / 2;
- if (first.size() < target_first_size) {
- while (first.size() < second.size()) {
- first.push_back(second.front());
- second.pop_front();
- }
- } else {
- while (first.size() > target_first_size) {
- second.push_front(first.back());
- first.pop_back();
- }
- }
- }
- void push_back(int x) {
- second.push_back(x);
- normalize();
- }
- void push_middle(int x) {
- first.push_back(x);
- normalize();
- }
- int pop() {
- int result = first.front();
- first.pop_front();
- normalize();
- return result;
- }
- };
- int main() {
- int n;
- cin >> n;
- DoubleQueue q;
- for (int i = 0; i < n; ++i) {
- string query;
- cin >> query;
- if (query == "+") {
- int x;
- cin >> x;
- q.push_back(x);
- } else if (query == "*") {
- int x;
- cin >> x;
- q.push_middle(x);
- } else {
- cout << q.pop() << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement