栈数据结构

#include <stdio.h>
#include <stdlib.h>

typedef char DataType;


#define StackSize 100

//栈的定义
typedef struct 
{
DataType stack[StackSize];
int top;//指示栈顶指针
}SqStack;

//初始化栈为空栈
void InitStack(SqStack &s)
{
s.top = -1;//设置栈顶指针为-1
}

//判断栈顶为空
bool StackEmpty(SqStack s)
{
if (s.top == -1)
return true;
else
return false;
}

//读取栈顶元素
bool GetTop(SqStack s, DataType &e)
{
if (s.top == -1)
{
return false;//空栈，无法继续操作
}
else
{
e = s.stack[s.top];//读取到栈顶元素
return true;
}

}
//进栈操作
bool PushStack(SqStack &s, DataType e)
{
//先判断元素是否已经满了
if (s.top >= StackSize-1)
{
return false;
}
else
{
s.top += 1;//栈顶指针增加1
s.stack[s.top] = e;//新元素e进栈
return true;
}
}
//出栈操作--将栈顶元素出栈，并将值赋值给e
bool PopStack(SqStack &s, DataType &e)
{
if (s.top == -1)
{
return false;//空栈
}
else
{
e = s.stack[s.top];//将元素赋值给e
s.top -= 1;//栈顶指针减少1
return true;
}
}
//求栈的长度
int StackLength(SqStack s)
{
return s.top+1;
}
//清空栈
void ClearStack(SqStack s)
{
s.top = -1;//函数运行结束后系统会自动回收内存
}


int main()
{
SqStack s;
DataType a[] = { ‘a‘,‘b‘,‘c‘,‘d‘,‘e‘ };
DataType e;

//初始化栈
InitStack(s);

//进栈操作
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) 
{
if (PushStack(s, a[i]) == false) 
{
//栈满无法进栈
return false;
}
}

//出栈操作
printf("出栈的元素是：");
if (PopStack(s, e) == true)
{
printf("%4c", e);
}
if (PopStack(s, e) == true)
{
printf("%4c\n", e);
}
printf("当前栈顶元素是：");
if (GetTop(s, e) == true)
{
printf("%4c\n", e);
}

if (PushStack(s, ‘f‘) == false)
{
//栈已满
return false;
}
if (PushStack(s, ‘g‘) == false)
{
//栈已满
return false;
}

/*
由于用s.top = -1来判断是否为空以及初始化，所以计算长度时要多加一个1
*/
printf("当前栈中的元素个数：%d\n", StackLength(s));

printf("元素出栈的序列是：");
while (!StackEmpty(s))
{
PopStack(s, e);
printf("%4c ", e);
}
printf("\n");
getchar();
return 0;
}