lightoj1212

27 8月 2015

1212 - Double Ended Queue

pushLeft(): inserts an item to the left end of the queue with the exception that the queue is not full.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:

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 mlines 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

Output for Sample Input

13 8pushLeft 1pushLeft 2pushRight -1pushRight 1

popLeft

popRight

popLeft

popRight

Case 1:Pushed in left: 1Pushed in left: 2Pushed in right: -1The queue is fullPopped from left: 2

Popped from right: -1

Popped from left: 1

The queue is empty

题目类型：双端队列

算法分析：直接使用STL中的deque模拟即可，只不过还要动态维护一个队列中元素个数cnt

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <list>
#include <ctime>
using namespace std;

int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {
        int n, m;

        cin >> n >> m;
        string input;

        int i, cnt = 0;
        deque <int> dq;

        cout << "Case " << flag++ << ":" << endl;

        for (i = 0; i < m; i++)
        {
            cin >> input;

            if (input == "pushLeft")
            {
                int temp;
                cin >> temp;
                if (cnt < n)
                {
                    cout << "Pushed in left: " << temp << endl;
                    dq.push_front (temp);
                    cnt++;
                }

                else
                    cout << "The queue is full" << endl;
            }

            else if (input == "pushRight")
            {
                int temp;
                cin >> temp;
                if (cnt < n)
                {
                    cout << "Pushed in right: " << temp << endl;
                    dq.push_back (temp);
                    cnt++;
                }

                else
                    cout << "The queue is full" << endl;
            }

            else if (input == "popLeft")
            {
                if (cnt > 0)
                {
                    cout << "Popped from left: " << dq.front () << endl;
                    dq.pop_front ();
                    cnt--;
                }

                else
                    cout << "The queue is empty" << endl;
            }

            else if (input == "popRight")
            {
                if (cnt > 0)
                {
                    cout << "Popped from right: " << dq.back () << endl;
                    dq.pop_back ();
                    cnt--;
                }

                else
                    cout << "The queue is empty" << endl;
            }
        }
    }

return 0;
}

100

#include <iostream>

#include <fstream>

#include <algorithm>

#include <iomanip>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <map>

#include <string>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <list>

#include <ctime>

using namespace std;

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

int n, m;

cin >> n >> m;

string input;

int i, cnt = 0;

deque <int> dq;

cout << "Case " << flag++ << ":" << endl;

for (i = 0; i < m; i++)

{

cin >> input;

if (input == "pushLeft")

{

int temp;

cin >> temp;

if (cnt < n)

{

cout << "Pushed in left: " << temp << endl;

dq.push_front (temp);

cnt++;

}

else

cout << "The queue is full" << endl;

}

else if (input == "pushRight")

{

int temp;

cin >> temp;

if (cnt < n)

{

cout << "Pushed in right: " << temp << endl;

dq.push_back (temp);

cnt++;

}

else

cout << "The queue is full" << endl;

}

else if (input == "popLeft")

{

if (cnt > 0)

{

cout << "Popped from left: " << dq.front () << endl;

dq.pop_front ();

cnt--;

}

else

cout << "The queue is empty" << endl;

}

else if (input == "popRight")

{

if (cnt > 0)

{

cout << "Popped from right: " << dq.back () << endl;

dq.pop_back ();

cnt--;

}

else

cout << "The queue is empty" << endl;

}

return 0;

}

lightoj1202

lightoj1213

一	二	三	四	五	六	日
« 6月
						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

超客的水墨烟雨

lightoj1212

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论