学步园

源于一道面试题：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。

总结学习了栈的基本操作。

代码如下：

#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
#define SIZE 5

typedef struct SqStack
{
	int *top;
	int *base;
	int stackSize;
};

void InitStack(SqStack *s)
{
	s->base=(int*)malloc(SIZE*sizeof(int));
	if(!s->base)
		exit(-1);
	s->top=s->base;
	s->stackSize=SIZE;
}//定义SqStack *对应->,没有*对应.。 

int GetTop(SqStack s)
{
	int e=*(s.top-1);
	return e;
}

void Push(SqStack *s,int e)
{
	if(s->top-s->base>=s->stackSize)
	{
		s->base=(int*)realloc(s->base,(s->stackSize+SIZE)*sizeof(int));
		if(!s->base)
			exit(-1);
		s->top=s->top+s->stackSize;
		s->stackSize+=SIZE;
	}
	*(s->top)++=e;
}

int Pop(SqStack *s)
{
	if(s->base==s->top)
		return 0;
	int e=*(--s->top);
}

void Traverse(SqStack s)
{
	if(s.base==s.top)
		cout<<"空栈";
	while(s.top!=s.base)
	{
		cout<<*(--s.top)<<" ";
	}
}

void main()
{
	SqStack s;
	SqStack smin;
	InitStack(&s);
	InitStack(&smin);
	int a[SIZE],i;
	for(i=0;i<SIZE;i++)
	{
		cin>>a[i];
		Push(&s,a[i]);
	}

	int e1=GetTop(s);
	Push(&smin,e1);
	Pop(&s);
	while(s.top!=s.base)
	{
		int e=GetTop(s);
		if(e<GetTop(smin))
		{
			Push(&smin,e);
		}
		Pop(&s);
	}//求最小值。smin的栈顶永远是最小值

	cout<<"最小值："<<GetTop(smin)<<endl;
}