首页 > 其他 > 详细

栈——数组实现

时间:2014-07-10 17:19:31      阅读:388      评论:0      收藏:0      [点我收藏+]

引言:

     

       使用链表实现栈存在“对malloc和free的调用开销昂贵”的缺点,特别是与指针操作的例程相比尤其如此。利用数组实现栈可以避免了指针。但它的缺点是可能存在空间的浪费。


分析描述:


       数组栈的结点元素。

#ifndef ERROR
#define ERROR (0)
#endif
#ifndef OK
#define OK	(!ERROR)
#endif

#define STACK_INIT_SIZE 100
#define STACKINCREMENT  10

typedef	int SElemType;
typedef struct SqStack{
	SElemType	*base;	
	SElemType	*top;	
	int			stacksize;
}SqStack, *pStack;
pStack S;

           栈的初始化。

pStack InitStack(pStack S)
{
	S = (pStack)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if(S == NULL){
		return ERROR;
	}
	S->base = (SElemType *)S;
	S->top = S->base;
	S->stacksize = STACK_INIT_SIZE;

	return S;
}

        入栈操作。

pStack Push(pStack S, SElemType e)
{
	if((S->top - S->base) >= S->stacksize){
		S->base = (SElemType *)realloc(S, (S->stacksize + STACKINCREMENT)*sizeof(SElemType));
		if(S->base == NULL)	
				return ERROR;
		S->top = S->base + S->stacksize;
		S->stacksize += STACKINCREMENT;
	}
	*S->top++ = e;
	return S;
}

         出栈操作。

SElemType Pop(pStack S)
{
	if(S->top == S->base)
			return 0;
	return *(--S->top);
}

          取栈顶元素。

SElemType GetTop(pStack S)
{
	if(S->top == S->base)
			return ERROR;
	return *(S->top - 1);
}

         求栈的长度。

int GetLength(pStack S)
{
	int length = 0;
	if(S->top == S->base)
			return 0;
        pStack Tmp = S;
	while(Tmp->top-- != Tmp->base)
			length++;
	return length;
}


栈——数组实现,布布扣,bubuko.com

栈——数组实现

原文:http://blog.csdn.net/to_be_it_1/article/details/37593157

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!