Dynamic Arrays and List - Deque

coding>C++
1.3k 词

题目描述

Deque 

For a dynamic array A={a0,a1,…} of integers, perform a sequence of the following operations: 

0-push(d, x): Add element x at the begining of A, if d=0. Add element x at the end of A, if d=1. 

1-randomAccess(p): Print element ap. 

2-pop(d): Delete the first element of A, if d=0. Delete the last element of A, if d=1. A is a 0-origin array and it is empty in the initial state.

输入

The input is given in the following format.

q

query1

query2

:

query n

Each query queryi is given by 0 d x , or 1 p, or 2 d ,where the first digits 0, 1 and 2 represent push, randomAccess and pop operations respectively.

randomAccess and pop operations will not be given for an empty array.
1≤q≤400,000
0≤p< the size of A
−1,000,000,000≤x≤1,000,000,000

输出

For each randomAccess, print ap in a line.

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
11
0 0 1
0 0 2
0 1 3
1 0
1 1
1 2
2 0
2 1
0 0 4
1 0
1 1

样例输出

1
2
3
4
5
2
1
3
4
1

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int> deque;
    int q;
    cin>>q;
    char d,x;
    int p;
    for(int i = 0; i < q; ++i)
    {
        cin>>d;
        switch(d)
        {
            case '0':
                cin >> x;
                cin>>p;
                if(x == '0')deque.push_front(p);
                else deque.push_back(p);
                break;
            case '1':
                cin >> p;
                cout<<deque[p]<<endl;
                break;
            case '2':
                cin >> x;
                if(x == '0')deque.pop_front();
                else deque.pop_back();
                break;
        }
    }
}