【ACM】特殊队列

博主： Fivk
发布时间：2021 年 06 月 01 日
1413 次浏览
暂无评论
968字数
分类：代码笔记

普通的队列仅有 EnQueue 和 DeQueue 两种操作，分别表示在队尾增加元素和取出队首元素。现在给队列增加一种新的操作 DeleteMid，表示删除队列的中间元素。对于有 N 个元素的队列，若 N 为偶数，中间元素定义为**从队首到队尾的第 N/2 个元素**；若 N 为奇数，中间元素定义为**第 (N+1)/2 个元素**。现给出队列的一系列操作，输出相应结果。

### 输入格式:

第一行输入一个不超过 106 的正整数 M 和 N，分别表示指令条数和队列容量。

之后 M 行，每行给出一条指令，为下列3种指令之一：

EnQueue *elem*

DeQueue

DeleteMid

### 输出格式:

对于每个 EnQueue 指令，若未超出队列容量，不输出任何信息，否则在一行中输出`Full Queue`。

对于每个 DeQueue 和 DeleteMid 指令，若队列不为空，则取出相应元素并输出；否则只在一行中输出`Empty Queue`。

最后在一行中按从队首到队尾的顺序依次输出队列中的元素，以空格分隔。行尾不得有多余空格。

### 输入样例:

```in
10 4
DeQueue
EnQueue 2
EnQueue 3
EnQueue 4
EnQueue 5
DeleteMid
DeleteMid
EnQueue 7
EnQueue 8
EnQueue 9
```

### 输出样例:

```out
Empty Queue
3
4
Full Queue
2 5 7 8
```

## 答案：

* 我写的：（答案错误，原因不知）

```cpp
#include<bits/stdc++.h>
using namespace std;

void print(int x)
{
	static int test=0;
	if(test)
	{
		cout<<" ";
	}else{
		test=1;
	}
	cout<<x;
}

int main()
{
	list<int> v;
	list<int>::iterator it;
	string str;
	int m,n,count=0,t,tt;
	cin>>m>>n;
	while(m--)
	{
		t=1;
		cin>>str;
		if(str.compare("DeQueue")==0)
		{
			if(v.size())
			{
				cout<<v.back()<<endl;
				v.pop_back();
			}else{
				cout<<"Empty Queue\n";
			}
		}else if(str.compare("EnQueue")==0)
		{
			cin>>t;
			if(v.size()>=n)
			{
				cout<<"Full Queue\n";
			}else{
				v.push_back(t);
			}
		}else if(str.compare("DeleteMid")==0)
		{
				if(v.size())
			{
				if(v.size()%2==0)
				{
					t=0;
				}
				it=v.begin();
				for(int j=1;j<=tt;j++) it++;
				tt=v.size()/2+t;
				v.erase(it);

}else{
				cout<<"Empty Queue\n";
			}
		}
	}
	for_each(v.begin(),v.end(),print);
	return 0;
}
```

- 又轮到邱靖贤帅帅了

```cpp
#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

int main()
{
    int n, qsize;
    scanf("%d %d", &n, &qsize);
    deque<int> que1, que2;
    char s[20];
    while(n--)
    {
        scanf("%s", &s);
        if(strcmp(s, "DeQueue") == 0)
        {
            if(que1.empty())
                cout << "Empty Queue" << endl;
            else
            {
                printf("%d\n", que1.front());
                que1.pop_front();
                if(que1.size() < que2.size())
                {
                    que1.push_back(que2.front());
                    que2.pop_front();
                }
            }
        }
        else if(strcmp(s, "EnQueue") == 0)
        {
            int x;
            scanf("%d", &x);
            if(que1.size() + que2.size() < qsize)
            {
                que2.push_back(x);
                if(que1.size() < que2.size())
                {
                    que1.push_back(que2.front());
                    que2.pop_front();
                }
            }
            else
                printf("Full Queue\n");
        }
        else
        {
            if(que1.empty())
                printf("Empty Queue\n");
            else
            {
                printf("%d\n", que1.back());
                que1.pop_back();
                if(que1.size() < que2.size())
                {
                    que1.push_back(que2.front());
                    que2.pop_front();
                }
            }
        }
    }
    int flag = 1;
    while(!que1.empty())
    {
        if(flag)
        {
            printf("%d", que1.front());
            que1.pop_front();
            flag = 0;
        }
        else
        {
            printf(" %d", que1.front());
            que1.pop_front();
        }
    }
    while(!que2.empty())
    {
        if(flag)
        {
            printf("%d", que2.front());
            que2.pop_front();
            flag = 0;
        }
        else
        {
            printf(" %d", que2.front());
            que2.pop_front();
        }
    }
    return 0;
}

```

下面是大佬的留言

[album type="photos"]

![](https://blog.fivk.cn/usr/uploads/2021/06/558033568.png)

![](https://blog.fivk.cn/usr/uploads/2021/06/1036287296.png)

![](https://blog.fivk.cn/usr/uploads/2021/06/390820499.png)

[/album] </div>

最后修改：2021 年 11 月 21 日