首页 > 试题广场 >

堆栈的使用

[编程题]堆栈的使用

热度指数：19628 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式，push 和 pop。其中 push一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。（注：本题有多组输入，可以参考该网址：https://www.nowcoder.com/discuss/276）

输入描述:

    对于每组测试数据，第一行是一个正整数 n（0 < n <= 10000）。而后的 n 行，每行的第一个字符可能是'P'或者'O'或者'A'；如果是'P'，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是'O'，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是'A'，表示询问当前栈顶的值，如果当时栈为空，则输出'E'。堆栈开始为空。

输出描述:

    对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的'A'操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出'E'。

示例1

输入

3
A
P 5
A
4
P 3
P 6
O
A

输出

E
5
3

算法知识视频讲解

稀有的猪

使用c语言实现链式栈

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

typedef struct sNode
{
    char ch;
    struct sNode *next;
}sNode;

typedef struct 
{
    sNode *top;
}sStack;

void init(sStack *s)
{
    s->top = NULL;
}

int empty(sStack *s)
{
    if(s->top == NULL)
        return 1;
    else return 0;
}
void push(sStack *s, char c)
{
    sNode *p = (sNode*)malloc(sizeof(sNode));
    p->ch = c;
    p->next = s->top;
    s->top = p;
}

void pop(sStack *s)
{
    sNode *p = s->top;
    s->top = s->top->next;
    free(p);
}

int top(sStack *s)
{
    return s->top->ch;
}

int main()
{
    sStack s;
    init(&s);
    int n, num;
    char ch;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0 ; i < n; i++)
        {
            getchar();
            scanf("%c",&ch);
            if (ch =='A')
            {
                if (empty(&s))
                    printf("E\n");
                else
                    printf("%d\n", top(&s));
            }
            else if (ch == 'P')
            {
                scanf("%d", &num);
                push(&s, num);
            }
            else
            {
                if (!empty(&s)) pop(&s);
            }
        }       
        while(!empty(&s)) pop(&s);
    }
    return 0;
}

发表于 2022-03-09 20:38:01 回复(0)

小蒲想变强

简单堆栈的使用。

#include<stdio.h>
int main()
{
	int n;
	while (scanf("%d",&n)!=EOF)
	{
		int i,j=-1,t_;
		int item[100000]={0};
		char t;
		if(n==0) break;
		else
		{
			getchar();
			for(i=0;i<n;i++)
			{
				scanf("%c",&t);
				getchar();
				if(t=='P')
				{
					scanf("%d",&t_);
					item[++j]=t_;
					getchar();
				}
				else if(t=='O')
				{
					if(j!=-1)
					{
						j--;
					}
				}
				else if(t=='A')
				{
					if(j==-1) printf("E\n");
					else printf("%d\n",item[j]);
				}
			}
			printf("\n");
		}
	}
	return 0;
}

发表于 2021-10-02 16:22:43 回复(0)