7-1 特殊堆栈_牛客博客

7-1 特殊堆栈

思路：

C做法：创建一个栈S和一个链表L(用于存储栈S中存在的元素并保证有序,这样当用peek函数时遍历寻找所需位置的元素并输出即可，同时在遇到push和pop的操作时,使用链表会便于进行插入和删除操作，便于实现，只是都需要遍历,所以时间复杂度大)。

纯C做法：

#include <stdio.h>
#include <stdlib.h>

struct SNode{
    int data;
    struct SNode* next;
};
typedef struct SNode* St;

int N=0;//记录元素个数
//返回一个头结点
St Makeempty(){
    St S;
    S=(St)malloc(sizeof(struct SNode));
    S->next=NULL;
    return S;
}

void push_k(St S,int key){
    St p;
    p=(St)malloc(sizeof(struct SNode));
    p->data=key;
    p->next=S->next;
    S->next=p;
    N++;
}

void pop_k(St S,St L){
    if(S->next==NULL){
        printf("Invalid\n");
        return;
    }
    else{
        int e;
        e=S->next->data;//记录要被出栈的元素值
        printf("%d\n",e);
        //遍历链表寻找要被删除的e
        St q=L->next,r=L;
        while(e!=q->data){
            q=q->next;
            r=r->next;
        }
        r->next=q->next;//找到了，删除
        St p=S->next;//出栈
        S->next=p->next;
        N--;//栈内元素数量--
        return;
    }
}

void PeekMedian(St S,St L){
    St p=L;
    int ci;
    //如果链表空，说明还没有元素，返回
    if(L->next==NULL){
        printf("Invalid\n");
        return;
    }
    //计算第几小元
    if(N%2==0) ci=N/2;
    else ci=(N+1)/2;
    //遍历寻找第几小
    while(ci--){
        p=p->next;
    }
    printf("%d\n",p->data);
}
//新元素入栈的同时加入到链表中，同时保证有序
void insertxu(St L,int key){
    St p=L->next,q;
    q=(St)malloc(sizeof(struct SNode));
    q->data=key;
    //如果表空
    if(p==NULL){
        q->next=L->next;
        L->next=q;
    }
    else{
        St r=L;
        //遍历寻找合适位置
        while(p){
            if(p->data<key){
                p=p->next;
                r=r->next;
            }
            else break;
        }
        //插入
        r->next=q;
        q->next=p;
    }
}

int main(){
    St S;
    S=Makeempty();

    St L=(St)malloc(sizeof(struct SNode));
    L->next=NULL;

    int n,x;
    char s[10];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        getchar();
        scanf("%s",s);
        if(s[1]=='u'){
            scanf("%d",&x);
            push_k(S,x);
            insertxu(L,x);
        }
        else if(s[1]=='o'){
            pop_k(S, L);
        }
        else if(s[1]=='e'){
            PeekMedian( S, L);
        }
    }
}

以上写法只适用于数据范围较小的时候，否则会超时。

使用二分+vector数组可以有效降低时间复杂度，处理数据范围较大的情况。

AC代码：

#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;

vector<int> vi;//元素在此容器中有序

struct SNode{
    int data;
    struct SNode* next;
};
typedef struct SNode* St;

int N=0;//记录栈（同时也是vi数组）中元素个数

St Makeempty(){
    St S;
    S=(St)malloc(sizeof(struct SNode));
    S->next=NULL;
    return S;
}
//二分查找第一个大于等于key的元素的位置，把key插入到该位置
void vi_insert(int key){
    int mid=-1,l=0,r=N-1;
    while(l<r){
        mid=(l+r)/2;
        if(vi[mid]>=key) r=mid;
        else l=mid+1;
    }
    vi.insert(vi.begin()+l,key);
}
//二分查找x所在的位置，并删除
void vi_erase(int x){
    int mid=-1,l=0,r=N-1;
    while(l<=r){
        mid=(l+r)/2;
        if(vi[mid]==x) break;
        else if(vi[mid]>x) r=mid-1;
        else l=mid+1;
    }
    vi.erase(vi.begin()+mid);
    return;
}
//入栈
void push_k(St S,int key){
    St p;
    p=(St)malloc(sizeof(struct SNode));
    p->data=key;
    p->next=S->next;
    S->next=p;
    N++;
}
//出栈
void pop_k(St S){
    if(S->next==NULL){
        printf("Invalid\n");
        return;
    }
    St p=S->next;
    printf("%d\n",p->data);
    S->next=p->next;
    vi_erase(p->data);
    N--;//要在vi数组中删除栈顶元素后才能令N--
    return;
}

void PeekMedian(){
    int op;
    if(vi.size()==0){
        printf("Invalid\n");
        return;
    }
    if(N%2==0) op=N/2;
    else op=(N+1)/2;
    printf("%d\n",vi[op-1]);//存储下标是从0~N-1,所以要让op-1
}

int main(){
    St S;
    S=Makeempty();

    int n,x;
    char s[10];
    
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        getchar();
        scanf("%s",s);
        if(s[1]=='u'){
            scanf("%d",&x);
            push_k(S,x);
            if(N==1) vi.push_back(x);//N=1时，vi数组中还没有数，所以直接加入
            else vi_insert(x);
        }
        else if(s[1]=='o'){
            pop_k(S);
        }
        else if(s[1]=='e'){
            PeekMedian();
        }
    }
}