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

包含min方法的栈

题目描述:

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的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;>