【数据结构】C语言栈的实现

一种特殊的线性表&＃xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶&＃xff0c;另一端称为栈底。

栈的基本操作

压栈&＃xff1a;栈的插入操作叫做进栈、压栈、入栈&＃xff0c;入栈数据在栈顶。
出栈&＃xff1a;栈的删除操作叫做出栈。出栈数据也在栈顶。
所以我们可以用链表&＃xff0c;顺序表实现栈&＃xff0c;但考虑到栈的结构&＃xff0c;我们只有尾删和尾插操作&＃xff0c;所以用顺序表实现更为方便。

c语言顺序表实现&＃xff1a;

栈的定义

typedef int Data;
typedef struct stack{Data* _data;int _size;int _capacity;
}stack;


栈的初始化

void init(stack* stack){if (stack &＃61;&＃61; NULL){return;}stack->_data &＃61; NULL;stack->_capacity &＃61; stack->_size &＃61; 0;
}


判空&＃xff08;增容&＃xff09;

void checkcapacity(stack* stack){if (stack->_capacity&＃61;&＃61;stack->_size){int newcapacity &＃61; stack->_capacity &＃61;&＃61; 0 ? 1 : stack->_capacity * 2;stack->_data &＃61; (Data*)realloc(stack->_data,sizeof(Data)*newcapacity);stack->_capacity &＃61; newcapacity;}
}


出栈和入栈

//入栈(先进后出)(相当于尾插)
void push(stack* stack, Data data){if (stack &＃61;&＃61; NULL){return;}checkcapacity(stack);stack->_data[stack->_size] &＃61; data;stack->_size&＃43;&＃43;;
}//出栈(相当于尾删)
void pop(stack* stack){if (stack &＃61;&＃61; NULL){return;}if (stack->_size > 0){stack->_size--;}
}


栈顶元素

//得到栈顶元素
void stacktop(stack* stack){//如果为空的话返回空,不用判断return stack->_data[stack->_size - 1];
}


判空栈

//判断是否为空栈
int empty(stack* stack){if (stack->_size &＃61;&＃61; 0){return 1;}else if (stack &＃61; NULL){return 1;}else{return 0;}
}


看元素个数

int size(stack* stack){if (stack &＃61;&＃61; NULL){return 0;}return stack->_size;
}


销毁

void destory(stack* stack)
{if (stack &＃61;&＃61; NULL){printf("非法操作\n");return;}stack->_size &＃61; 0;stack->_capicity &＃61; 0;free(stack->_data);//先释放堆空间stack->_data &＃61; NULL;}