顺序表实现栈的操作
顺序表实现栈的操作
栈的定义
百度的解释是:
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
自己理解的话,栈就像是砌墙,最先的砖在最下面,最后的砖在最上面。
就想是这样:
数据结构的课程学完顺序表,链表之后,就进入了栈和堆的学习。关于那些建立栈的模板代码相对晦涩难懂。 不如就用最简单的数据结构来完成一个栈的实现。
首先我们需要分析一个栈的构成,栈由存储地址,栈顶,栈底。 栈的数据操作是遵循 先进后出 或者 后进先出 的准则的。
因此搞懂栈的定义之后,我们开始操作~
#define MAXSIZE 10 // 能存储的数据的多少
#define TRUE 1 // 宏定义,将TRUE 定义为1
#define FALSE 0 // 将FALSE 定义为0
typedef struct _stack {
int data[MAXSIZE]; // 存储数据的栈
int top; // 栈的标志,相当于输入或输出数组时,用的for循环中的 计数器 i 。
}Stack,*Pstack; // 一个为结构体类型,一个为指针类型
栈的初始化
Pstack Init_stack(Pstack stack) {
stack = (Pstack)malloc(sizeof(Stack)); // 为栈从堆中开辟内存空间
if (stack == NULL) { // 开辟内存失败的话,返回空内存 NULL
printf("Malloc Error.\n");
return NULL;
}
else {
stack->top = -1; // 开辟成功的话,标志为 -1 ,为什么会定义为 -1 ,后面会讲到
}
return stack;
}
判断栈是否为空
void Is_Empty(Pstack stack) {
if (stack->top == -1) { // 若为空,显示为空
printf("The stack is empty.\n");
}
else { // 不为空,显示不为空
printf("The stack is filled.\n");
}
}
入栈的操作
Pstack Push(Pstack stack) {
if (stack->top == MAXSIZE) { // 西安判断栈是否满,满了之后就不能再向栈中输入元素
printf("Stack is filled up.\n");
return FALSE; // 栈满
}
int num = 0; // 输入要入栈的元素
printf("Input the number you want to push: ");
scanf("%d", &num);
stack->top++; // 每向入栈一个元素,标签的值加一
stack->data[stack->top] = num; // 将输入的元素压入栈中
return stack;
}
出栈的操作
Pstack Pop(Pstack stack) {
if (stack->top == -1) { // 判断栈是否为空,若为空栈,则无法将有效元素出栈
printf("Empty stack.\n");
return stack;
}
stack->data[stack->top]; // 将栈顶的元素压出栈
stack->top--; // 标志减一
return stack;
}
输出栈的元素
void Illustrate(Pstack stack) {
printf("Amount of Valuable elments is: %d\n", stack->top+1); // 输出栈中的有效元素个数
int count = stack->top; // 将栈的标志信息赋给计数器
for (int i = 0; i < count+1; i++) {
printf("The %dth element is %d.\n", i+1, stack->data[i]); // 输出栈中的所有元素
}
}
这时有些人就会被 i+1 或者 上面的 top 的赋值所弄糊涂。
其实理清思路就发现很容易理解,最开始讲 top 赋值为 -1 的原因是,在C语言中数组的计数是从 0 开始,这样如何将 top 设置为0,那么就证明我们栈中有一个元素,而事实栈中还没有有效元素。这样有时候就容易造成逻辑的紊乱。
而若将 top 设置为 -1,这样当向栈中压入第一个元素时,top++ 的值就由 -1 变为了 0 这样就可以使用 stack->data[stack->top] 来表示栈的第一个元素,也就是栈底 stack->data[0] 。
而在输出环节 top 为 0 时代表的是栈的一个元素,因此输出提示信息是,在输出语句时给计数器后面加 1 就好了。
获得栈顶的元素
int Get_top(Pstack stack) {
if (stack->top == -1) { // 若为空栈,则无法输出有效栈顶元素
return FALSE;
}
return stack->data[stack->top]; // 返回栈顶的元素
}
主函数
int main() {
Pstack stack_a = NULL; // 定义一个空栈
stack_a = Init_stack(stack_a); // 将栈初始化
Is_Empty(stack_a); // 判断栈是否为空
printf("Input the amount of elements: "); // 向栈中压入几个元素
int amount = 0;
scanf("%d", &amount);
for (int i = 0; i < amount; i++) {
stack_a = Push(stack_a);
}
Is_Empty(stack_a); // 判断是否为空栈
Illustrate(stack_a); // 输出栈中的元素
printf("Top element: %d\n",Get_top(stack_a));
stack_a = Pop(stack_a); // 出栈操作
Illustrate(stack_a);
system("pause");
return 0;
}
执行效果
这样我们就完成了用顺序表实现栈的基本操作。