定义：栈是限定仅在表尾进行插入和删除操作的线性表。特点：先进后出(First in Last out)， 或者叫后进先出表。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
数据结构
typedef int ElemType;
#define MaxSize 50//定义栈中元素的最大个数
typedef struct SqStack {
ElemType data[MaxSize];//存放战中元素
int top;//栈顶元素
}SqStack, *stack;
方案一：
栈空间范围为S[0, MaxSize-1];
栈顶指针指向顶元素所在的位置
stack.png
(a) 非空栈top>=0，顶元素=s[top]；
(b) 进栈，先对top+1，指向下一空位置，将新数据输入top指向的位置，完成进栈操作，结束时top指向新栈顶元素的位置；
(c) 出栈，先根据top指向取出栈顶数据元素，再对top-1完成出栈操作，结束时top指向去掉原栈顶的元素后的新栈顶元素所在位置；
(d) 栈满条件，top= MaxSize-1，若插入元素，将发生溢出，overflow；
(e) 栈空条件，top=-1，若删除元素，将发生“下溢”。
//初始化
void InitStack(stack s) {
s->top = -1;//初始化栈顶指针
}
//判断栈空
int StackEmpty(SqStack s) {
if (s.top == -1) {
printf("空栈...\n");
return 0;
}
else
return 1;
}
//进栈
int Push(stack s, ElemType data) {
if (s->top == MaxSize-1) {
printf("栈满...\n");
return 1;
}
s->data[++s->top] = data;
return 0;
}
//出栈
int PopStack(stack s) {
if (s->top == -1) {
printf("空栈...\n");
return 1;
}
int data = s->data[s->top--];
return data;
}
//读取栈顶元素
int GetTop(stack s) {
if (s->top == -1) {
printf("空栈...\n");
return 1;
}
int data = s->data[s->top];
return data;
}
//销毁栈
void destory(stack s) {
s->top = -1;
memset(s->data, 0, sizeof(s->data));
}
//十进制转换为二进制
void ten_to_two(stack s, int ten) {
int tmp = ten;
if (ten < 0) { //将负数变成正数，同时前面加负号
ten = ~ten + 1;
printf("-");
}
if (ten == 0) {
Push(s, ten);
}
else {
while (ten) {
tmp = ten % 2;
Push(s, tmp);
ten = ten / 2;
}
}
}
//测试
void testStack() {
SqStack S;
stack s = &S;
InitStack(s);
// Push(s, 23);
// printf("%d\n", GetTop(s));
int ret;;
ten_to_two(s, 4);
printf("4=");
while((ret = PopStack(s)) >= 0){
printf("%d", ret);
}
printf("\n");
}
方案二：
栈空间范围为S[0, MaxSize-1];
栈顶指针指向顶元素上一个空的位置
stack.png
(a) 非空栈top>=1，顶元素=s[top-1]；
(b) 进栈，先将新数据输入top指向的位置，再对top+1，指向下一空位置，完成进栈操作，结束时top正好指向新栈顶位置的上一空位置；
(c) 出栈，先对top-1，再根据top指向取出栈顶数据元素，完成出栈操作，结束时top指向去掉原栈顶的元素后的新栈顶元素所在位置的上一空位置；
(d) 栈满条件，top= MaxSize，若插入元素，将发生溢出，overflow；
(e) 栈空条件，top=0，若删除元素，将发生“下溢”。
//初始化，这里吧top=0设置为空栈，栈满的条件为top=maxsize
void init_stack(stack s) {
s->top = 0;
}
//判断栈空
int empty_stack(SqStack s) {
if (s.top == 0) {
printf("空栈...\n");
return 0;
}
else {
printf("非空栈...\n");
return -1;
}
}
//入栈
int push_stack(stack s, ElemType data) {
if (s->top == MaxSize) {
printf("栈满...\n");
return -1;
}
s->data[s->top++] = data;
return 0;
}
//出栈
int pop_stack(stack s) {
if (s->top == 0) {
printf("空栈...\n");
return -1;
}
int data = s->data[--s->top];
return data;
}
//获取栈顶元素
int get_stack(stack s) {
if (s->top == 0) {
printf("空栈...\n");
return -1;
}
int top = s->top-1;
int data = s->data[top];
return data;
}
//销毁栈
void destory_stack(stack s) {
s->top = 0;
memset(s->data, 0, sizeof(s->data));
}
//十进制转换为八进制
void ten_to_eight(stack s, ElemType ten) {
int tmp;
while (ten) {
tmp = ten % 8;
push_stack(s, tmp);
ten = ten / 8;
}
}
//测试
void test_stack() {
SqStack S;
stack s = &S;
init_stack(s);
int ret;
// empty_stack(S);
// push_stack(s, 23);
// push_stack(s, 45);
// push_stack(s, 90);
// printf("%d\n", get_stack(s));
// printf("%d\n", pop_stack(s));
// printf("%d\n", get_stack(s));
// empty_stack(S);
ten_to_eight(s, 16);
printf("4=");
while ((ret=pop_stack(s)) >= 0) {
printf("%d", ret);
}
printf("\n");
}
