Lightoj1212——Double Ended Queue（STL）-白红宇

Lightoj1212——Double Ended Queue（STL）

阅读量：2344 次

发布时间：2019-05-10

本文共 2885 字，大约阅读时间需要 9 分钟。

A queue is a data structure based on the principle of ‘First In First Out’ (FIFO). There are two ends; one end can be used only to insert an item and the other end to remove an item. A Double Ended Queue is a queue where you can insert an item in both sides as well as you can delete an item from either side. There are mainly four operations available to a double ended queue. They are:

pushLeft(): inserts an item to the left end of the queue with the exception that the queue is not full.

pushRight(): inserts an item to the right end of the queue with the exception that the queue is not full.

popLeft(): removes an item from the left end of the queue with the exception that the queue is not empty.

popRight(): removes an item from the right end of the queue with the exception that the queue is not empty.

这里写图片描述

Now you are given a queue and a list of commands, you have to report the behavior of the queue.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with a line containing two integers n, m (1 ≤ n ≤ 10, 1 ≤ m ≤ 100), where n denotes the size of the queue and m denotes the number of commands. Each of the next m lines contains a command which is one of:

pushLeft x pushes x (-100 ≤ x ≤ 100) in the left end of the queue

pushRight x pushes x (-100 ≤ x ≤ 100) in the right end of the queue

popLeft pops an item from the left end of the queue

popRight pops an item from the right end of the queue

Output

For each case, print the case number in a line. Then for each operation, show its corresponding output as shown in the sample. Be careful about spelling.

Sample Input

3 8

pushLeft 1

pushLeft 2

pushRight -1

pushRight 1

popLeft

popRight

popLeft

popRight

Output for Sample Input

Case 1:

Pushed in left: 1

Pushed in left: 2

Pushed in right: -1

The queue is full

Popped from left: 2

Popped from right: -1

Popped from left: 1

The queue is empty

还好标准库中定义了双端队列

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define INF 0x3f3f3f3f#define MAXN 2005#define Mod 10001using namespace std;deque
            
              q;int main(){ int t,cnt=1; scanf("%d",&t); while(t--) { q.clear(); int n,m,num; string op; cin>>n>>m; printf("Case %d:\n",cnt++); while(m--) { cin>>op; if(op[1]=='u'&&op[4]=='L') { cin>>num; if(q.size()==n) printf("The queue is full\n"); else { printf("Pushed in left: %d\n",num); q.push_front(num); } } else if(op[1]=='u'&&op[4]=='R') { cin>>num; if(q.size()==n) printf("The queue is full\n"); else { printf("Pushed in right: %d\n",num); q.push_back(num); } } else if(op[1]=='o'&&op[3]=='L') { if(q.empty()) printf("The queue is empty\n"); else { printf("Popped from left: %d\n",q.front()); q.pop_front(); } } else { if(q.empty()) printf("The queue is empty\n"); else { printf("Popped from right: %d\n",q.back()); q.pop_back(); } } } } return 0;}

转载地址：http://cpcvb.baihongyu.com/

你可能感兴趣的文章