数据结构复习之顺序栈的实现
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//常量定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//自定义类型
typedef int Status; //函数返回值类型为int
typedef int ElemType; //栈元素类型为int
//栈的存储结构定义
typedef struct {
ElemType *elem;
int top;
int size;
int increment;
} SqStack;
//栈的初始化函数
Status init(SqStack &S, int size, int inc) {
//分配存储空间
S.elem = (ElemType*)malloc(size * sizeof(ElemType));
//分配失败
if(S.elem == NULL) {
return OVERFLOW;
}
S.top = 0; //设置栈顶为0,因为当前是空栈
S.size = size; //栈的长度
S.increment = inc; //每次增加的长度
return OK;
}
//入栈函数
Status push(SqStack &S, ElemType e) {
//如果栈已经满了,则开辟新的空间
ElemType *newbase;
if(S.top >= S.size) {
newbase = (ElemType*)realloc(S.elem, (S.size + S.increment) * sizeof(ElemType));
if(newbase == NULL) {
return OVERFLOW;
}
S.elem = newbase;
S.size = S.size + S.increment;
}
//将e赋值给S.elem[top],并且是top加1
S.elem[S.top++] = e;
return OK;
}
//出栈函数
Status pop(SqStack &S,ElemType &e) {
if(S.top == 0) {
return ERROR;
}
S.top--;
e = S.elem[S.top];
return OK;
}
//取栈顶元素
Status getTop(SqStack &S, ElemType &e) {
if(S.top == 0) {
return ERROR;
}
e = S.elem[S.top-1];
}
//清空栈
Status clear(SqStack &S) {
int i;
ElemType e;
for(i = S.top; i > 0; i--) {
pop(S, e);
printf("%d\n", e);
}
}
//判断栈是否为空
Status isEmpty(SqStack &S) {
return (S.top == 0 ? TRUE : FALSE);
}
int main() {
//声明一个栈类型的变量stack
SqStack stack;
//声明一个栈元素类型的变量e
ElemType e;
//初始化栈
init(stack, 5, 1); //初始化栈
//判空
printf("%s\n", isEmpty(stack) == 1 ? "stack is empty" : "stack isn't empty");
//入栈
push(stack, 1);
push(stack, 2);
//判空
printf("%s\n", isEmpty(stack) == 1 ? "stack is empty" : "stack isn't empty");
//取栈顶元素
getTop(stack, e);
printf("%d\n", e); //2
//出栈
pop(stack, e);
printf("%d\n", e); //2
//清空栈
clear(stack);
//判空
printf("%s\n", isEmpty(stack) == 1 ? "stack is empty" : "stack isn't empty");
}