简答题 偏难
#7152

双端队列 定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。 时间限制:1000 内存限制:655…

双端队列

定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。

时间限制:1000

内存限制:65535

输入

第一行输入一个整数t,代表测试数据的组数。 每组数据的第一行输入一个整数n,表示操作的次数。 接着输入n行,每行对应一个操作,首先输入一个整数type。

 当type=1,进队操作,接着输入一个整数x,表示进入队列的元素。

 当type=2,出队操作,接着输入一个整数c,c=0代表从队头出队,c=1代表从队尾出队。

n <= 1000

输出

对于每组测试数据,输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开,按队头到队尾的顺序输出,占一行。如果队列中已经没有任何的元素,输出NULL。

样例输入

2
5
1 2
1 3
1 4
2 0
2 1
6
1 1
1 2
1 3
2 0
2 1
2 0

样例输出

3
NULL
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1 //用deque模拟一下即可 #include &lt;bits/stdc++.h&gt; using namespace std; string s; int main() { int n,m,type,x; cin&gt;&gt;n; for(int i=1;i&lt;=n;i++){ cin&gt;&gt;m; deque&lt;int&gt; q; for(int j=1;j&lt;=m;j++){ cin&gt;&gt;type&gt;&gt;x; if(type==1){ q.push_back(x); }else { if(x==0)q.pop_front(); else q.pop_back(); } } if(q.empty()){ cout&lt;&lt;"NULL";continue; } while(!q.empty()){ cout&lt;&lt;q.front()&lt;&lt;" "; q.pop_front(); } cout&lt;&lt;endl; } return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2 #include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstring&gt; #include &lt;iomanip&gt; #include &lt;iostream&gt; #include &lt;map&gt; #include &lt;queue&gt; #include &lt;set&gt; #include &lt;stack&gt; #include &lt;vector&gt; using namespace std; int n, t, type, c; int a[1005] = {0}; int Top = 0, Back = 0; int main() {   cin &gt;&gt; t;   while (t--) {     Top = 0;     Back = 0;     cin &gt;&gt; n;     while (n--) {       cin &gt;&gt; type &gt;&gt; c;       if (type == 1) {         a[Back++] = c;       } else {         if (c == 0) {           Top++;         } else {           Back--;         }       }     }     if (Top == Back) {       cout &lt;&lt; "NULL" &lt;&lt; endl;     } else {       for (int i = Top; i &lt; Back; ++i) {         cout &lt;&lt; a[i] &lt;&lt; " ";       }       cout &lt;&lt; endl;     }   }   return 0; }</pre><p><br/></p>
这道题暂未补解析。