首页 > 代码库 > 包含min方法的栈

包含min方法的栈

2024-07-15 10:56:57   225人阅读

题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

输入：

输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为一个整数n(1<=n<=1000000)， n代表将要输入的操作的步骤数。
接下来有n行，每行开始有一个字母Ci。
Ci=’s’时，接下有一个数字k，代表将k压入栈。
Ci=’o’时，弹出栈顶元素。

输出：

对应每个测试案例中的每个操作，
若栈不为空，输出相应的栈中最小元素。否则，输出NULL。

样例输入：
7
s 3
s 4
s 2
s 1
o
o
s 0
样例输出：
3
3
2
1
2
3
0
思路：
使用辅助栈一枚。用于记录当前数据栈中最小值。详见代码。

代码：

/*
包含min函数的栈
by Rowandjj
2014/8/2
*/
#include<stdio.h>
#include<stdlib.h>
//-------------栈基本定义及实现--------------------
typedef struct _SNODE_
{
	int data;
	struct _SNODE_ *next;
}Node,*pNode;
typedef struct _STACK_
{
	pNode pHead;
	int size;
}Stack,*pStack;
void InitStack(pStack ps)
{
	ps->pHead = (pNode)malloc(sizeof(Node));
	if(ps->pHead == NULL)
	{
		exit(-1);
	}
	ps->pHead->next = NULL;
	ps->size = 0;
}
void Push(pStack ps,int data)
{
	if(ps == NULL)
	{
		return;
	}
	pNode pNew = (pNode)malloc(sizeof(Node));
	if(!pNew)
	{
		exit(-1);
	}
	pNew->data = http://www.mamicode.com/data;>


联系
我们