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 (-th smallest element if N is even, or (-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 (≤). 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 1.

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           

题意：

　　模拟一个stack，并且新增一个返回中值的功能。

思路：

1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int main() {
 6     int n;
 7     cin >> n;
 8     getchar();
 9     string str;
10     stack<int> stk;
11     int prt = -1;
12     int bucket_count[100] = {0};
13     int bucket[100][1000] = {0};
14     for (int i = 0; i < n; ++i) {
15         getline(cin, str);
16         if (str[1] == 'u') {
17             int num = stoi(str.substr(5));
18             bucket_count[num / 1000]++;
19             bucket[num / 1000][num % 1000]++;
20             stk.push(num);
21         } else if (str[1] == 'o') {
22             if (stk.empty())
23                 cout << "Invalid" << endl;
24             else {
25                 int num = stk.top();
26                 cout << num << endl;
27                 bucket_count[num / 1000]--;
28                 bucket[num / 1000][num % 1000]--;
29                 stk.pop();
30             }
31         } else {
32             if (stk.empty()) {
33                 cout << "Invalid" << endl;
34             } else {
35                 int target = (stk.size() + 1) / 2;
36                 int count = 0;
37                 for (int i = 0; i < 100; ++i) {
38                     if (count + bucket_count[i] >= target) {
39                         for (int j = 0; j < 1000; ++j) {
40                             if (count + bucket[i][j] >= target) {
41                                 cout << i * 1000 + j << endl;
42                                 break;
43                             }
44                             count += bucket[i][j];
45                         }
46                         break;
47                     }
48                     count += bucket_count[i];
49                 }
50             }
51         }
52     }
53 
54     return 0;
55 }      

永远渴望，大智若愚（stay hungry, stay foolish）