Original Queue

Description

Doggie will run following operations on an original queue containing numbers from 1 to n inclusively:

1
2
3
4
5
6
int n = Q.front();
Q.pop();
Q.push(n);
n = Q.front();
print(n);
Q.pop();

The funniest thing is that the printed numbers are 1, 2, 3, …., n in ascending order, then find out the original queue.

Solution

There are two methods to handle this problem:

  • reverse the whole process using deque from the last to the first;
  • re-run the whole operations and meantime recording the positions and then set numbers by the positions accordingly.

Reverse

According to the operations, we can easily reverse the whole operations and retrieve the original.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
int n, k;
cin >> k;
while(k > 0) {
deque<int> q;
k--;
cin >> n;
for(int i = n; i > 0; i--) {
q.push_front(i);
int t = q.back();
q.pop_back();
q.push_front(t);
}
for(int i = 0; i < q.size(); i++)
cout << q[i] << " ";
cout << endl;
}
}

Record

By recording the positions of the numbers and repeating the operations above, we then can set the corresponding elements to retrieve the original queue, which is more compatible but less efficient taking up extra O(n) space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void refactor(vector<int>& arr){
int size = arr.size();
queue<vector<int>::iterator> v_queue;
for(auto iter = arr.begin(); iter != arr.end(); ++iter) v_queue.push(iter);
vector<vector<int>::iterator> v;
while(v.size() < size){
vector<int>::iterator x = v_queue.front();
v_queue.pop();
v_queue.push(x);
v.push_back(v_queue.front());
v_queue.pop();
}
for(int i = 0; i < size; ++i) *v[i] = i+1;
}

Always welcome new ideas and practical tricks, just leave them in the comments!