数据结构-----栈（栈的初始化、建立、入栈、出栈、遍历、清空等操作）

目录

前言

栈

1.定义

2.栈的特点

3.栈的储存方式

3.1数组栈

3.2链栈

 4.栈的基本操作（C语言）

4.1初始化 

 4.2判断是否满栈

4.3判断空栈

 4.4 入栈

4.5 出栈

4.6获取栈顶元素

 4.7遍历栈

 4.8清空栈

 完整代码示例

---

前言

        大家好呀！今天我们开始学习新的线性表结构----栈，前面我们学习了链表以及链表的相关操作，那么栈跟链表有什么区别呢，操作如何呢？下面就一起来看看吧！

栈

1.定义

        栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

2.栈的特点

        栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

        栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为出栈/退栈（POP）。栈也称为先进后出表。

 

3.栈的储存方式

栈的存储方式有两种：数组栈和链栈，即栈的数组存储和链式存储。

 数组栈：数组栈是通过数组的形式去存放数据的，然后定义一个栈顶top指针指向当前栈顶的位置，这个位置也就是数组最后一个位置

链表栈：链表栈就是去通过链表节点的形式去储存数据，然后建立链式结构，对这个链表进行栈的相关操作，以达到栈的特点。二者的节点写法分别如下所示：

3.1数组栈

//01 数组栈
typedef struct sqstack {
	ElemType date[Maxsize];//数据
	int top;//数组栈的栈顶指针
}SqStack;

3.2链栈

//02链表栈
typedef struct linknode {
	ElemType date[Maxsize];//数据
	struct linknode* next;//指向下一个节点的指针
}* LiStack;

（本文主要讲解数组栈） 

 4.栈的基本操作（C语言）

 栈的操作方法有以下方法：

#include<stdio.h>
#include<string.h>
#define Maxsize 10//最大空间容量
 
//数据类型
typedef struct datatype {
	int age;
	char name[10];
}ElemType;
 
//数组栈
typedef struct sqstack {
	ElemType date[Maxsize];//数据
	int top;//数组栈的栈顶指针
}Stack;
 
initStack(Stack *L);//初始化栈
 
isFull(Stack *L);//判断是否满栈
 
isEmpty(Stack *L);//判断是否空栈
 
push(Stack *L,ElemType date);//入栈
 
pop(Stack *L);//出栈
 
top_date(Stack* L);//获取栈顶元素
 
show_stack(Stack *L);//遍历栈
 
clear_stack(Stack *L);//清空栈元素

【注：以上均是数组栈的操作方法】

4.1初始化 

让栈顶元素初始化为-1，即 L->top=-1;

//初始化
void initStack(Stack *L) {
	L->top = -1;
}

 4.2判断是否满栈

判断满栈的方法就是看栈顶元素位置是否达到最大容量

//判断是否满了
int isfull(Stack *L) {
	if (L->top == Maxsize - 1) {//此时栈已满
		printf("The stack is full\n");
		return 1;
	}
	return 0;
}

4.3判断空栈

同样的判断是否空栈，只需要看栈顶top的位置是否为初始化的时候，即L->top==-1

//判断是否为空栈
int isEmpty(Stack *L) {
	if (L->top == -1) {
		printf("The stack is empty\n");
		return 1;
	}
	return 0;
}

 4.4 入栈

进行入栈操作的时候，每次放入一个数据后，栈顶指针依次向上移动一位即可，如图所示：

//入栈
void push(Stack *L,ElemType date){
	if (isfull(L)) {  //判断栈是否满了
		printf("failed to push\n");
		return;
	}
	else {
        L->top+=1;
		L->date[L->top].age = date.age;
		strcpy(L->date[L->top].name, date.name);
	}
}

4.5 出栈

进行出栈操作时，取出栈顶元素后，栈顶指针依次向下移动一位，如下所示：

//出栈
ElemType pop(Stack *L) {
	ElemType pop_date = { 0 };
	//先判断是不是空栈
	if (isEmpty(L)) {
		return pop_date;
	}
	pop_date = L->date[L->top];
	L->top--;
	return pop_date;
}

4.6获取栈顶元素

获取栈顶元素就不进行出栈操作，直接返回栈顶元素即可。

//获取栈顶元素（不出栈）
ElemType get_topdate(Stack* L) {
	return L->date[L->top];
}

 4.7遍历栈

遍历栈，即当栈不为空的时候，从栈顶开始往下依次输出数据即可。

//遍历栈,输出数据
void show_stack(Stack *L) {
	if (!isEmpty(L)) {
		for (int i = L->top; i >= 0; i--) {
			printf("%d %s\n", L->date[i].age, L->date[i].name);
		}
	}
}

 4.8清空栈

清空栈，只需要让栈顶指针回归到初始化即可，L->top=-1;

//清空栈
void clear_stack(Stack *L) {
	L->top = -1;//直接让栈顶回归就行了
	//之前的那些数据不会被删除，但是引索找不到了，下次入栈就会把这些数据给覆盖掉
}

 完整代码示例

#include<stdio.h>
#include<string.h>
#define Maxsize 10//设置最大空间容量
 
typedef struct datatype {
	int age;
	char name[10];
}ElemType;
// 数组栈
typedef struct sqstack {
	ElemType date[Maxsize];//数据
	int top;//数组栈的栈顶指针
}Stack;
 
//初始化
void initStack(Stack *L) {
	L->top = -1;
}
 
//判断是否满了
int isfull(Stack *L) {
	if (L->top == Maxsize - 1) {//此时栈已满
		printf("The stack is full\,");
		return 1;
	}
	return 0;
}
 
//入栈
void push(Stack *L,ElemType date){
	if (isfull(L)) {
		printf("failed to push\n");
		return;
	}
	else {
		L->top+=1;
		L->date[L->top].age = date.age;
		strcpy(L->date[L->top].name, date.name);
	}
}
 
//判断是否为空栈
int isEmpty(Stack *L) {
	if (L->top == -1) {
		printf("The stack is empty\n");
		return 1;
	}
	return 0;
}
 
//出栈
ElemType pop(Stack *L) {
	ElemType pop_date = { 0 };
	//先判断是不是空栈
	if (isEmpty(L)) {
		return pop_date;
	}
	pop_date = L->date[L->top];
	L->top--;
	return pop_date;
}
 
//获取栈顶元素（不出栈）
ElemType get_topdate(Stack* L) {
	return L->date[L->top];
}
 
//清空栈
void clear_stack(Stack *L) {
	L->top = -1;//直接让栈顶回归就行了
	//之前的那些数据不会被删除，但是引索找不到了，下次入栈就会把这些数据给覆盖掉
}
 
//遍历栈,输出数据
void show_stack(Stack *L) {
	if (!isEmpty(L)) {
		for (int i = L->top; i >= 0; i--) {
			printf("%d %s\n", L->date[i].age, L->date[i].name);
		}
	}
}
 
int main() {
	Stack stack ;
	ElemType date[4] = { {15,"Jack"},{16,"Amy"} ,{15,"John"},{17,"Tom"}};
	initStack(&stack);
	for(int i=0;i<4;i++)
		push(&stack, date[i]);//依次入栈
	show_stack(&stack);	//遍历栈
	ElemType pop_date= pop(&stack);//出栈
	printf("出栈元素为：%d %s\n", pop_date.age, pop_date.name);
	ElemType top_date = get_topdate(&stack);//获取栈顶元素
	printf("栈顶元素为：%d %s\n", top_date.age, top_date.name);
	clear_stack(&stack);//清空栈
}
//测试结果
/*17 Tom
15 John
16 Amy
15 Jack
出栈元素为：17 Tom
栈顶元素为：15 John*/

好啦，以上就是本期的全部内容了，我们下一期再见！see you!

分享一张壁纸：