堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定 N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2 小元。
输入格式：
输入的第一行是正整数 N（≤10
5
）。随后 N 行，每行给出一句指令，为以下 3 种之一：
Push key
Pop
PeekMedian
其中 key 是不超过 10
5
的正整数；Push 表示“入栈”；Pop 表示“出栈”；PeekMedian 表示“取中值”。
输出格式：
对每个 Push 操作，将 key 插入堆栈，无需输出；对每个 Pop 或 PeekMedian 操作，在一行中输出相应的返回值。若操作非法，则对应输出 Invalid。
输入样例：
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop
输出样例：
Invalid
Invalid
3
2
2
1
2
4
4
5
3
Invalid
作者初始解法：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxsize 1000
int pop(int s[], int *top, int *x) {
if (*top == -1)
return 0;
else {
*x = s[(*top)--];
return 1;
}
}
void push(int s[], int *top, int x) {
if (*top == Maxsize - 1)
printf("PUSH FALSE\n");
else
s[++(*top)] = x;
}
int peekmedian(int s[], int top) {
if (top == -1)
return 0;
return 1;
}
int cmp(const void* a, const void* b) {
return *(int *)a <= *(int *)b ? -1 : 1;
}
int finddata(int s[],int top)
{
int data[top+1];
int i;
for(i=0;i<=top;i++)
{
data[i]=s[i];
}
qsort(data,(top+1),sizeof(data[0]),cmp);
return data[top/2];
}
int main() {
int stack[Maxsize];
int data[Maxsize];
int top = -1;
int n, i, pushnum, popnum, midnum;
scanf("%d", &n);
for (i = 0; i < n; i++) {
char s[Maxsize];
scanf("%s", s);
if (!strcmp(s, "Pop")) {
if (pop(stack,&top,&popnum))
printf("%d\n", popnum);
else
printf("Invalid\n");
}
if (!strcmp(s, "Push")) {
scanf("%d", &pushnum);
push(stack, &top, pushnum);
}
if (!strcmp(s, "PeekMedian")) {
if (peekmedian(stack, top)) {
midnum =finddata(stack,top);
printf("%d\n", midnum);
} else {
printf("Invalid\n");
}
}
}
return 0;
}因为包含push和pop两种操作，
1.在每次PeekMidnumber时用data函数来存储栈中元素，再用qsort函数进行快排，直接返回对应data[top/2]即是我们所要求的中值，这种方法就是上述代码的思路；但是提交后会T掉；
2.如果用hash表存储每个数出现的次数，增添或者删除对应数字出现的次数，具体操作还没试，
用前缀和来储存数字个数，（若top表示栈顶元素下标则所求中值下标无论偶数或者奇数都可以用top/2表示）与top/2进行对比。会不会T不知道还没试过；
3.第三种方法利用树状数组来存储每个数字及之前的数字出现的次数，并利用二分查找。代码如下：
#include <stdio.h>
#include <string.h>
#define N 100010
int t[N];
int s[N];#用t数组作为树状数组存储每个数字及之前的数字（至对应节点起始位置的数字）出现的所有次数，s数组用来作为顺序栈；
int top = -1;#令top初始化为-1，即数组空时的元素下标；
int lowbit(int x)
{
return x & (-x);
}
#定义lowbit函数去找到i对应的结点长度；
void updataforest(int x,int num)
{
int i;
for(i=x;i<N;i+=lowbit(i))
{
t[i]+=num;
}
}
#更新树状数组，更新数字出现次数；
int getforestsum(int x)
{
int sum=0;
for(int i = x;i;i-=lowbit(i))
{
sum+=t[i];
}
return sum;
}
#获得1~x所有数字出现的数字的总次数，以便于和top/2作比较；
int find(int x)
{
x+=1;
if(x%2==1)
x++;
x/=2;
int l=1,r=N-1,mid;
while(l!=r)
{
mid=(l+r)/2;
if(getforestsum(mid)>=x)
{
r=mid;
}
else l=mid+1;
}
return l;
}
#简单的二分查找；
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char str[10];
scanf("%s",str);
if(!strcmp(str,"Pop"))
{
if(top==-1)
printf("Invalid\n");
else{
printf("%d\n",s[top]);
updataforest(s[top],-1);
top--;
}
}
else if(!strcmp(str,"Push"))
{
top+=1;
scanf("%d",&s[top]);
updataforest(s[top],1);
}
else{
if(top==-1)
printf("Invalid\n");
else{
printf("%d\n",find(top));
}
}
}
#顺序栈的基本操作；
}