pat Stack(1057)

2024-02-11 16:48
文章标签 stack pat 1057

本文主要是介绍pat Stack(1057),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1057. Stack (30)

时间限制
100 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard

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
 
 
//1057 stack
//错误的代码
#include <stdio.h>
#include <string.h>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;int main()
{int n, i, j;char str[15];stack<int> S;vector<int> V;scanf("%d", &n);//while(scanf("%d", &n) != EOF)//{getchar();while(!S.empty())S.pop();V.clear();for(i = 0; i < n; i++){gets(str);if(strcmp(str, "Pop") == 0){if(S.empty()){printf("Invalid\n");}else if(!S.empty()){printf("%d\n", S.top());V.pop_back();//不应该是V.Pop_back(), 而应该是把S.top()从vector中删除,而不是把vector中最后一个元素删除。S.pop();}}else if(strcmp(str, "PeekMedian") == 0){if(S.empty())printf("Invalid\n");else if(!S.empty()){int m;if(S.size() % 2 == 0)m = S.size() / 2;elsem = (S.size() + 1) / 2;sort(V.begin(), V.end());/*用这种方法虽然过了一个测试数据,但是方法本身不对。例如6Push 3Push 2Push 1PeekMedianPopPeekMedian便得不到正确的结果。因为用sort对vector进行了排序,*/printf("%d\n", V[m-1]);}}else if(str[1] == 'u'){int tmp = 0;for(j = 0; j < strlen(str); j++)if(str[j] >= '0' && str[j] <= '9')tmp = tmp * 10 + str[j] - '0';S.push(tmp);V.push_back(tmp);}}//}return 0;
}


这篇关于pat Stack(1057)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/700302

相关文章

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现

Java-数据结构-栈和队列-Stack和Queue (o゚▽゚)o

文本目录: ❄️一、栈(Stack):     ▶ 1、栈的概念:   ▶ 2、栈的使用和自实现:      ☑ 1)、Stack():       ☑ 2)、push(E e):      ☑ 3)、empty():         ☑ 4)、peek(E e):        ☑ 5)、pop(E e):       ☑ 6)、size(E e):  ▶ 3、栈自实现的总代

c++stack和list 介绍

stack介绍 堆栈是一种容器适配器,专门设计用于在 LIFO 上下文(后进先出)中运行,其中元素仅从容器的一端插入和提取。 堆栈作为容器适配器实现,容器适配器是使用特定容器类的封装对象作为其基础容器 的类,提供一组特定的成员函数来访问其元素。元素从特定容器的 “back” 推送或弹出,这称为堆栈的顶部。 stack接口 stack() 构造空的栈 empty() 检测stack是否为

stack,queue, priority_queue

STL 中栈的使用方法(stack) #include <stack> 基本操作: push(x) 将x加入栈中,即入栈操作 pop() 出栈操作(删除栈顶),只是出栈,没有返回值 top() 返回第一个元素(栈顶元素) size() 返回栈中的元素个数 empty() 当栈为空时,返回 true STL 中队列的使用(queue) #i

Elastic Stack--ES集群加密及Kibana的RBAC实战

前言:本博客仅作记录学习使用,部分图片出自网络,如有侵犯您的权益,请联系删除 学习B站博主教程笔记:  最新版适合自学的ElasticStack全套视频(Elk零基础入门到精通教程)Linux运维必备—ElasticSearch+Logstash+Kibana精讲_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1VMW3e6Ezk/?sp

PAT甲级-1044 Shopping in Mars

题目   题目大意 一串项链上有n个钻石,输入给出每个钻石的价格。用m元买一个连续的项链子串(子串长度可为1),如果不能恰好花掉m元,就要找到最小的大于m的子串,如果有重复就输出多个,按递增顺序输出子串的前端和后端索引。 原来的思路 取连续的子串使和恰等于m,没有恰等于就找最小的大于。可以将子串依次累加,使得每个位置都是起始位置到该位置的序列和,整个数组显递增顺序,就可以用右边减左边

C++ STL-Stack容器概念及应用方法详解

1. 再谈栈 栈是一种先进后出的数据结构,而实现方式需要创建多个结构体,通过链式的方式进行实现,这是标准的栈的思路,而在STL中栈可以以更为简单的方式实现。 概念:stack是一种先进后出(First In Last Out,FILO)的数据结构,它只有一个出口。 栈中只有顶端的元素才可以被外界使用,因此栈不允许有遍历行为。 栈中进入数据称为 — 入栈 push 栈中弹出数据称为 — 出

PAT (Advanced Level) Practice——1011,1012

1011:  链接: 1011 World Cup Betting - PAT (Advanced Level) Practice (pintia.cn) 题意及解题思路: 简单来说就是给你3行数字,每一行都是按照W,T,L的顺序给出相应的赔率。我们需要找到每一行的W,T,L当中最大的一个数,累乘的结果再乘以0.65,按照例子写出表达式即可。 同时还需要记录每一次选择的是W,T还是L

Elastic Stack--ES的DSL语句查询

前言:本博客仅作记录学习使用,部分图片出自网络,如有侵犯您的权益,请联系删除 学习B站博主教程笔记:  最新版适合自学的ElasticStack全套视频(Elk零基础入门到精通教程)Linux运维必备—ElasticSearch+Logstash+Kibana精讲_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1VMW3e6Ezk/?spm_

Elastic Stack-ES集群常用的API

前言:本博客仅作记录学习使用,部分图片出自网络,如有侵犯您的权益,请联系删除 学习B站博主教程笔记:  最新版适合自学的ElasticStack全套视频(Elk零基础入门到精通教程)Linux运维必备—ElasticSearch+Logstash+Kibana精讲_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1VMW3e6Ezk/?spm