数据结构之——栈_数据结构栈

数据结构之——栈

一：栈的定义：

栈是限定仅在表尾进行插入和删除操作的线性表，栈又称为先进后出（Last In First Out）的线性表，简称LIFO结构。（栈就像一个杯子，我们只能在杯口（栈顶）向这个杯子里倒入水（进栈）或使其倒出水（出栈），而不能在杯底（栈底）进行这些操作，而且我们喝水的时候不能直接喝底下的水，只能先喝上面的水（出栈），才能去喝下面的水）

栈顶：允许插入和删除的一端称为栈顶。
栈底：不可以进行插入和删除操作。
空栈：不含任何数据元素的栈称为空栈。

	理解栈的定义需要注意几点：
1：它是一个线性表，即说明栈元素具有  线性关系，即  前驱后继  关系。只不
      过它是一种特殊的线性表而已。
2：定义中说在线性表的表的表尾进行插入和删除操作，注意这里表尾指的是
      栈顶 ，不是栈底。
3：栈的特殊之处就在于其限制了这个线性表的插入和删除始终在栈顶进行。这使得
      栈底是固定的，最先进栈的只能在栈底。
4： 栈的插入操作：叫进栈，也叫压栈、入栈。
	  栈的删除操作：叫出栈，也叫弹栈。
1
2
3
4
5
6
7
8
9

二：栈的抽象数据类型：

	ADT 栈（stack）
	Date  和线性表相同。元素有相同的数据类型，相邻元素有前驱和后继的关系
	Operation
		InitStack (*S): 初始化操作，建立一个空栈S。
		DestoryStack（*S）:如果栈存在则销毁它。
		ClearStack (*S) : 将栈清空。
		StackEmpty（*S）:如果栈为空则返回true,否则返回false。
		GetTop（*S，*e）:如果栈存在且非空，用e返回S的栈顶储存的值。
		Push (*S, e) :若栈S存在，插入新的元素e到栈S中并成为栈顶元素。 
		Pop (*S，*e) :删除S中栈顶元素，并用e返回其值。
		StackLength (S) :返回栈S的元素个数。
	endADT
1
2
3
4
5
6
7
8
9
10
11
12

三：栈的顺序存储结构及其实现：

1: 预说明：

	1：在栈中我们我们把空栈的top值设为 -1
	2：把满栈的top值设为 maxsize - 1
	3：把下标为0的一端作为栈底
	
	‘1、2’的解释：top 值的位置都是其数组所对应的下标位置，数组的
	下标范围是0 ~ n - 1，且每个top所在的位置都是已经存储了数据
	的，每次我们新存储数据之前都要先要top++来运动到下一个结点，
	所以top 的最大值为maxsize - 1, 空栈时的top 值为 -1 ，因为
	移动了maxsize次后top = maxsizeof - 1
	‘3’ 的解释：因为我们的首元素都存在栈底（因为它们是最先进栈的），
	变化最小。
1
2
3
4
5
6
7
8
9
10
11

2：栈的顺序存储结构——结构定义：

#define maxsize 在此处输入自定义的一个数
typedef int ElemType		//ElemType 的类型根据实际情况而定 
 
typedef struct {
   
	
	ElemType date[maxsize]; //这个maxsize 通过我们事先的预定义
	来改变改栈的长度大小 
	
	int top;  				//这个  top  用于栈顶的指针，即
	目前栈顶所在数组中的位置
	 
}SqStack;
1
2
3
4
5
6
7
8
9
10
11
12
13

3:栈的顺序存储结构——进栈操作

// 进行一次进栈操作
int sqstack_insert(sqstack *p, ElemType e) {
   
	//这个指针 P 接收的是包含我们要进行操作的那个栈的结构体的地址
	//这个 e 接受的是我们想向这个栈中放入的数据
	
	if (p->top >= maxsize - 1) {
   
		printf("当前您的栈已满，不可进行此操作");
		system("pause");	/*该行代码是程序的停顿操作，按任意键
		可继续向下执行*/
		return ERROR;  /* 程序进行到这一步说明我们的栈已经满了，
		不可再进行进栈操作，返回 Error*/
	}
	else {
   
		p->top++;</
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16