首页 > 试题广场 >

栈和排序

[编程题]栈和排序

热度指数：1779 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个从 $1$ 到 $n$ 的排列 $P$ ，以及一个空栈。你按顺序将排列中的元素依次入栈，可以在任意时刻选择将栈顶元素出栈并将其加入输出序列。入栈顺序不可改变。

$\hspace{15pt}$ 理想情况下，你想得到一个严格从大到小排序的输出序列 $n, n-1, \dots,1$ ，但受栈操作限制可能无法实现。当无法完全排序时，请输出**字典序**最大的合法出栈序列。

输入描述:

在一行中输入一个整数  。 
第二行输入  个整数，表示排列  中的元素，用空格分隔。保证给出的是一个从  到  的排列。

输出描述:

输出一行，包含若干整数，表示最终的出栈序列，用空格分隔，结尾不输出多余空格。

示例1

输入

5
2 1 5 3 4

输出

5 4 3 1 2

说明

入栈顺序和操作示例如下： 
2 入栈； 
1 入栈； 
5 入栈； 
5 出栈； 
3 入栈； 
4 入栈； 
4 出栈； 
3 出栈； 
1 出栈； 
2 出栈。

备注:

算法知识视频讲解

查看答案及解析

123456789201803221944171

include <stdio.h>

include <stdlib.h>

typedef struct Stack {
int* base;
int top;
} Stack;
void initstack(Stack* p, int capacity) {
int* s = (int)malloc(sizeof(int) * capacity);
if (!s) exit(1);
p->base = s;
p->top = 0;
}
void push_stack (Stack p, int v) {
p->base[p->top++] = v;

}
void pop_stack(Stack* p) {
p->top--;
}
int top(Stack* p) {
return p->base[p->top - 1];
}

int main() {
int a = 0;
scanf("%d", &a);
int* P = (int*)malloc(sizeof(a) * a) ;
if (!P) exit(1);
for (int i = 0; i < a; i++) {
scanf("%d ", &P[i]);
}
Stack mystack;
int j = 0;
initstack(&mystack, a);
for (int i = 0; i < a; i++) {
while (j < a) {
push_stack(&mystack, P[j++]);
if (top(&mystack) == a - i) {
break;
}
}

    if (i < a) {
        printf("%d ", top(&mystack));
    } else {
        printf("%d\n", top(&mystack));
    }
    pop_stack(&mystack);
}
free(P);
free(mystack.base);
P = mystack.base = NULL;
return 0;

}

int* base;

int top;

} Stack;

void initstack(Stack* p, int capacity) {

int* s = (int*)malloc(sizeof(int) * capacity);

if (!s) exit(1);

p->base = s;

p->top = 0;

}

void push_stack (Stack* p, int v) {

p->base[p->top++] = v;

}

void pop_stack(Stack* p) {

p->top--;

}

int top(Stack* p) {

return p->base[p->top - 1];

}

int main() {

int a = 0;

scanf("%d", &a);

int* P = (int*)malloc(sizeof(a) * a) ;

if (!P) exit(1);

for (int i = 0; i a; i++) {

    scanf("%d ", &P[i]);

}

Stack mystack;

int j = 0;

initstack(&mystack, a);

for (int i = 0; i a; i++) {

    while (j a) {

        push_stack(&mystack, P[j++]);

        if (top(&mystack) == a - i) {

            break;

        }

    }

    if (i a) {

        printf("%d ", top(&mystack));

    } else {

        printf("%d\n", top(&mystack));

    }

    pop_stack(&mystack);

}

free(P);

free(mystack.base);

P = mystack.base = NULL;

return 0;

}

发表于 2025-08-14 11:01:48 回复(0)