数据结构第四次pta

培风图楠

446人浏览 · 2025-09-30 01:41:53

培风图楠 · 2025-09-30 01:41:53 发布

1.我们知道平凡的栈有几个操作:

push(value) 将 value 压入栈  
pop() 将栈顶元素弹出, 并返回这个弹出的元素。

现在我们想要在平凡栈的基础上实现以下几个操作:

        push(val) 将 val 压入栈；  
    pop() 将栈顶元素弹出；  
    min() 返回栈中元素的最小值。

输入格式:

第一行输入一个N( 0=<N<=1000000),代表有N行操作。
接下来N行每行有一个操作,题目保证操作不会越界.

输出格式:

输出每次查询min()时的结果,pop()不用输出

输入样例:

6
push 1
min
push 2
min
push 3
min

输出样例:

1
1
1

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

typedef struct
{
    int* base;
    int* top;
    int stacksize;
}Stack;

void initStack(Stack* s)
{
    s->base = (int*)malloc(50*sizeof(int));
    if(!s->base) exit(1);
    s->top = s->base;
    s->stacksize = 50;
}

void push(Stack* s, int value)
{
    if(s->top - s->base >= s->stacksize)
    {
        s->base = (int*)realloc(s->base, (s->stacksize + 50)*sizeof(int));
        if(!s->base) exit(1);
        s->top = s->base + s->stacksize;
        s->stacksize += 50;
    }
    *s->top++ = value;
}

int pop(Stack* s)
{
    if(s->top == s->base) return -1;
    return *--(s->top);
}

int main()
{
    int n;
    scanf("%d", &n);

    char s0[20];
    Stack dataStack, minStack;
    initStack(&dataStack);
    initStack(&minStack);

    while(n--)
    {
        scanf("%s", s0);

        if(strcmp("push", s0) == 0)
        {
            int v;
            scanf("%d", &v);
            push(&dataStack, v);
            if(minStack.top == minStack.base || v <= *(minStack.top - 1))
                push(&minStack, v);
        }
        else if(strcmp("pop", s0) == 0)
        {
            int e = pop(&dataStack);
            if(e != -1 && e == *(minStack.top - 1))
                pop(&minStack);
        }
        else if(strcmp("min", s0) == 0)
        {
            if(minStack.top != minStack.base)
                printf("%d\n", *(minStack.top - 1));
        }
    }

    free(dataStack.base);
    free(minStack.base);
    return 0;
}

2.输入序列为1,2,3,4...,n，判断通过一个栈能否得序列a, 且输出入栈和出栈过程。

输入格式:

每组输入为两行：

第1行是一个正整数n,1<=n<=100;

第2行是序列a，共有n个整数，表示要得到的目标序列。序列为1~n的排列，题目保证序列长度为n, 序列中的整数都不相同，且整数在区间[1,n]之内。

可有多组输入。

输出格式:

对于每组输入，先输出一行，如果能通过栈得到序列a, 则输出YES，并接着输出得到序列a的入栈出栈的操作。
如果无法得到序列a，只需要输出NO。

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

typedef struct
{
    int* base;
    int* top;
    int stacksize;
}Stack;

void initStack(Stack* s)
{
    s->base=(int*)malloc(50*sizeof(int));
    if(!s->base) exit(1);
    s->top=s->base;
    s->stacksize=50;
}

void push(Stack* s,int value)
{
    if(s->top-s->base>=s->stacksize)
    {
        s->base=(int*)realloc(s->base,(s->stacksize+50)*sizeof(int));
        s->top=s->base+s->stacksize;
        s->stacksize+=50;
    }

    *s->top++=value;
}

int pop(Stack* s)
{
    if(s->base==s->top) return -1;
    int e=*--(s->top);
    return e;
}

int getTop(Stack s)
{
    if(s.top==s.base) return -1;
    return *(s.top-1);
}

int hasInvalidPattern(int* target, int n)
{
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(target[j] == target[i] - 2)
            {
                for(int k = j + 1; k < n; k++)
                {
                    if(target[k] == target[i] - 1)
                    {
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}

int main()
{
    int n;

    while(scanf("%d",&n)!=EOF)
    {
        int target[n];
        for(int i=0;i<n;i++)
        {
            int a;
            scanf("%d",&a);
            target[i]=a;
        }

        if(hasInvalidPattern(target, n))
        {
            printf("NO\n");
            continue;
        }
        else printf("YES\n");

        Stack s;
        initStack(&s);
        int cur=1;
        int index=0;
        while(index<n)
        {
            if(getTop(s)==target[index])
            {
                printf("%s %d\n","pop",pop(&s));
                index++;
            }
            else
            {
                push(&s,cur);
                printf("%s %d\n","push",cur);
                cur++;
            }
        }
    }
    return 0;
}

3.请编写程序，将 n+1 个整数顺序压入容量为 n 的栈，随后执行 n+1 次取顶并出栈的操作。

输入格式：

输入首先在第一行给出正整数 n（≤104）；随后一行给出 n+1 个 int 范围内的整数，数字间以空格分隔。

输出格式：

将输入的n+1 个整数顺序压入容量为 n 的栈，随后执行 n+1 次取顶并出栈的操作，输出取出的元素的值，每行一个。
注意：当栈已满时，入栈操作应该不执行，并在一行中输出错误信息 错误：栈已满。；当栈为空时，取顶和出栈操作应该不执行，并在一行中输出错误信息 错误：栈为空。。空栈取顶应返回 -1。

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

typedef struct
{
    int* base;
    int* top;
    int stacksize;
}sqStack;

void initSqStack(sqStack* s,int n)
{
    s->base=(int*)malloc(n*sizeof(int));
    if(!s->base) exit(1);
    s->top=s->base;
    s->stacksize=n;
}

void push(sqStack* s,int value)
{
    if(s->top-s->base>=s->stacksize)
    {
        printf("错误：栈已满。\n");
        return;
    }

    *s->top++=value;
}

int pop(sqStack* s)
{
    if(s->base==s->top)
    {
        printf("错误：栈为空。\n");
        return -1;
    }

    return *--(s->top);
}

int main()
{
    int n;
    scanf("%d",&n);
    sqStack s;
    initSqStack(&s,n);

    for(int i=0;i<=n;i++)
    {
        int a;
        scanf("%d",&a);
        push(&s,a);
    }

    for(int i=0;i<=n;i++)
    {
        int res=pop(&s);
        printf("%d\n",res);
        if(res==-1) printf("错误：栈为空。");
    }

    return 0;
}

4.请编写程序，将 n 个整数顺序压入容量无限制的（链式）栈，随后执行 n+1 次取顶并出栈的操作。

输入格式：

输入首先在第一行给出正整数 n；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔。题目保证有 n 个元素的（链式）栈不会超过题目的空间限制。

输出格式：

将输入的 n 个整数顺序压入栈，随后执行 n+1 次取顶并出栈的操作，输出取出的元素的值，每行一个。
注意：当栈为空时，取顶和出栈操作应该不执行，并在一行中输出错误信息 错误：栈为空。。空栈取顶应返回 -1。

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

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

typedef struct
{
    Node* top;
}listStack;

void initListStack(listStack* s)
{
    s->top=NULL;
}

void push(listStack* s,int value)
{
    Node* newNode=(Node*)malloc(sizeof(Node));
    if(!newNode) exit(1);
    newNode->next=s->top;
    newNode->data=value;
    s->top=newNode;
}

int pop(listStack* s)
{
    if(s->top==NULL)
    {
        printf("错误：栈为空。\n");
        return -1;
    }

    Node* temp=s->top;
    s->top=s->top->next;
    int data=temp->data;
    free(temp);
    return data;
}

int main()
{
    int n;
    scanf("%d",&n);
    listStack s;
    initListStack(&s);

    for(int i=0;i<n;i++)
    {
        int a;
        scanf("%d",&a);
        push(&s,a);
    }

    for(int i=0;i<=n;i++)
    {
        int res=pop(&s);
        printf("%d\n",res);
        if(res==-1) printf("错误：栈为空。");
    }

    return 0;
}