# 看数据结构写代码（8）顺序栈的实现

// SqStack.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdlib.h>
#include <cstdio>

//故意将值设置的比较小，以测试 重新分配 存储空间
#define STACK_INIT_SIZE 10

typedef int ElementType;

enum E_State
{
E_State_Error = 0,
E_State_Ok,
};
//顺序栈
struct sqStack
{
ElementType * base;
ElementType * top;
int stackSize;
};

E_State stackInit(sqStack * stack){
ElementType * base = (ElementType *)malloc(sizeof(sqStack) * STACK_INIT_SIZE);
if (base == NULL)
{
return E_State_Error;
}
stack->base = stack->top = base;
stack->stackSize = STACK_INIT_SIZE;
return E_State_Ok;
}

void stackDestory(sqStack * stack){
free(stack->base);
stack->base = stack->top = NULL;
stack->stackSize = 0;
}

void stackClear(sqStack * stack){
stack->top = stack->base;
}

int stackLen(sqStack stack){
return stack.top - stack.base;
}

bool stackEmpty(sqStack stack){
return stack.top == stack.base ? true : false;
}

E_State stackGetTop(sqStack stack,ElementType * e){
if (stackEmpty(stack))
{
return E_State_Error;
}
/*e = *stack.top 错误，注意
没搞清楚 栈顶 指向问题
// 栈顶指针的下一个位置为栈顶元素
*/
*e = *(stack.top-1);
return E_State_Ok;
}
//
E_State stackPush(sqStack * stack,ElementType e){
//首先检查空间是否不足.
int len = stackLen(*stack);
if (len >= stack->stackSize)
{
//粗心啊
//ElementType * base = (ElementType *)realloc(stack->base,stack->stackSize + STACK_ADD_SIZE);
ElementType * base = (ElementType *)realloc(stack->base,(stack->stackSize + STACK_ADD_SIZE)*sizeof(ElementType));
if (base == NULL)
{
return E_State_Error;
}
stack->base = base;
stack->top = stack->base + stack->stackSize;
}
*(stack->top) = e;
stack->top++;
return E_State_Ok;
}

E_State stackPop(sqStack * stack,ElementType * e){
if (stack->top > stack->base)
{
stack->top--;
*e = *stack->top;
return E_State_Ok;
}
else
{
return E_State_Error;
}
}

void stackTraverse(sqStack stack){
printf("----------------遍历开始----------------------\n");
if (stack.top > stack.base)
{
ElementType * top = --stack.top;
while (top != stack.base)
{
printf("-------%d-----------\n",*top--);
}
//最后还要遍历栈底
printf("-------%d-----------\n",*top);
}
printf("----------------遍历结束----------------------\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
sqStack stack;
stackInit(&stack);
//插入 1 ~ 15
for (int i = 1; i < 16; i++)
{
stackPush(&stack,i);
}
ElementType top;
//删除15
stackPop(&stack,&top);
//删除14
stackPop(&stack,&top);
stackTraverse(stack);
stackGetTop(stack,&top);
printf("栈长为：%d,栈顶元素为 ：%d，栈是否为空 %d",stackLen(stack),top,stackEmpty(stack));
stackDestory(&stack);
return 0;
}