Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

PAT 1057. Stack

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian — return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 105). Then N lines follow, each contains a command in one of the following 3 formats:

Push key
Pop
PeekMedian
where key is a positive integer no more than 105.

Output Specification

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print "Invalid" instead.

Sample Input

17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

Sample Output

Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid

解答

#include <cstdio>
#include <set>
#include <stack>
#include<functional>
using namespace std;

stack<int> stk;
multiset<int> maxs; //大于中位数。maxs和mins长度相同,或mins长度大一,中位数为mins最大值
multiset<int, greater<int> > mins;//小于等于中位数

void push(int x)
{
	stk.push(x);
	if (mins.empty() || x <= *mins.begin()) mins.insert(x);
	else maxs.insert(x);

	if (mins.size() < maxs.size())
		mins.insert(*maxs.begin()), maxs.erase(maxs.begin());
	else if (mins.size() > maxs.size() + 1)
		maxs.insert(*mins.begin()), mins.erase(mins.begin());
}

void pop()
{
	if (stk.empty())
		printf("Invalid\n"); 
	else
	{
		int t = stk.top(); stk.pop(); printf("%d\n", t);
		if (t <= *mins.begin()) mins.erase(mins.find(t)); //mins.erase(t)出错
		else maxs.erase(maxs.find(t));					  //maxs.erase(t)出错

		if (mins.size() < maxs.size())
			mins.insert(*maxs.begin()), maxs.erase(maxs.begin());
		else if (mins.size() > maxs.size() + 1)
			maxs.insert(*mins.begin()), mins.erase(mins.begin());
	}
}

void peek()
{
	if (stk.empty())
		printf("Invalid\n");
	else
		printf("%d\n", *mins.begin());
}

int main()
{
	int n, t; scanf("%d", &n);
	while (n--)
	{
		char op[80]; scanf("%s", op);
		if (op[1] == 'u') scanf("%d", &t), push(t);
		else if (op[1] == 'o') pop();
		else if (op[1] == 'e') peek();
		else printf("Invalid\n");
	}
	return 0;
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论