首页 › 题库 › C/C++编程考级 › C/C++编程六级 › 简答题
简答题 偏难
#7389

双端队列 定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。 时间限制: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 #include&lt;bits/stdc++.h&gt; using namespace std; int main() {   int t;   cin&gt;&gt;t;   while(t--)   {     int n;     cin&gt;&gt;n;     int a,b,i;     int l[100001],head=1,tail=0;     for(i=1;i&lt;=n;i++)     {       cin&gt;&gt;a&gt;&gt;b;       if(a==1)       {         tail++;         l[tail]=b;       }       else       {         if(b==0) head++;         else tail--;       }     }     if(tail-head&lt;0 || head&gt;tail) cout&lt;&lt;"NULL";     else       for(i=head;i&lt;=tail;i++)         cout&lt;&lt;l[i]&lt;&lt;" ";     cout&lt;&lt;endl;   }   return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2 //用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>
这道题暂未补解析。