【数据结构（13）】3.3 栈的表示和操作的实现_线性栈的实现与表示

一、栈的抽象数据类型的类型定义

1. 栈的基本操作

1. 初始化操作（InitStack(&S)）

   • 构造一个空的栈，构造好了之后就可以往这个栈里进行压栈出栈了。
   • 操作结果：构造一个空栈 S 。

2. 销毁栈操作（DestroyStack(&S)）

   • 将栈 S 所占有的内存空间销毁，销毁之后这个栈就不存在了。
   • 初始条件：栈 S 已存在。
   • 操作结果：栈 S 被销毁。

3. 判断 S 是否为空栈（StackEmpty(S)）

   • 初始条件：栈 S 已存在。
   • 操作结果：若 S 为空栈，则返回 TRUE，反之返回 FALSE。

4. 求栈的长度（StackLength(S)）

   • 初始条件：栈 S 已存在。
   • 操作结果：返回栈 S 中的元素个数，即栈的长度。

5. 取栈顶元素（GetTop(S,&e)）

   • 初始条件：栈 S 已存在且里面有元素。
   • 操作结果：得到的 S 的栈顶元素的值用 e 来接收。

6. 清空栈操作（CelarStack(&S)）

   • 初始条件：栈 S 已存在。
   • 操作结果：将 S 清为空栈，清空栈里面的元素，栈本身还在。

7. 入栈操作（Pust(&S,e)）

   • 初始条件：栈 S 已存在。
   • 操作结果：插入元素 e 为新的栈顶元素。

8. 出栈操作（Pop(&S,&e)）

   • 初始条件：栈 S 已存在且非空。
   • 操作结果：删除 S 的栈顶元素 an，并用 e 接收被删除的值。

二、顺序栈的表示和实现

1. 顺序栈的表示

由于栈本身就是线性表，于是栈也有顺序存储和链式存储两种实现方式。

• 栈的顺序存储 —— 顺序栈
• 栈的链式存储 —— 链栈

存储方式：同一般线性表的顺序存储结果完全相同

• 利用一组地址连续的存储单元（如数组）依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。
  • 附设 top 指针，指示栈顶元素在顺序栈中的位置。
  • 另设 base 指针，指示栈底元素在顺序栈中的位置。
• 但是，为了方便操作，通常 top 指针指示的其实是栈顶元素之上的位置。
• 另外，用stacksize表示栈可使用的最大容量。

举个例子

• 空栈：下图的栈最多能存放 4 个元素进去，当栈为空栈的时候，top 指针和 base 指针指向同一个地址。

• 入栈：当入栈的时候，top 指针就向后移动 1 格，指向下标为1的位置，之后插入其他元素就以此类推了。

• 栈满：当 top 指向了数组之外的地址的时候，说明栈空间被装满了，当 top 指针和 base 指针之间的差值等于数组最大容量的时候，则说明栈空间装满了（同个数组之内的指针是可以相减的）。

栈满时的处理方法

1. 报错，返回操作系统。
2. 分配更大的空间作为栈的存储空间，将原来栈的内容移入到新栈。

使用数组作为顺序栈存储方式的特点：简单、方便、但易产生溢出（数组大小固定）

• 上溢：栈已经满，又要压入元素。

• 下溢：栈已经空，还要弹出元素。

  • 注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。

顺序栈的定义

//顺序栈的存储结构
#define MAXSIZE 100//顺序栈存储空间的初始分配量
typedef struct
{
	SElemType* base;//栈底指针
	SElemType* top;//栈顶指针
	int stacksize;//栈可用的最大容量
	
}SqStack;//结构类型叫顺序栈
1
2
3
4
5
6
7
8
9

• 在这里的 top 和 base 可以定义成 int 型，用它们来放数组的下标。
• 当 top 与 base 之间的差值等于栈的最大容量时，表示栈满。

2. 顺序栈的实现

2.1 顺序栈的初始化

• 顺序栈的初始化操作就是为顺序栈动态分配一个预定义大小的数组空间。

算法步骤

1. 为顺序栈动态分配一个最大容量为 MAXSIZE 的数组空间，使 base 指向这段空间的起始地址，即栈底。
2. 将栈顶指针 top 初始化为 base，表示当前栈为空。
3. statcksize 置为栈的最大容量 MAXSIZE。

算法描述

//构造一个空栈
Status InitStack(SqStack &S)
{
	s.base = new SElemType(MAXSIZE);;/为顺序栈动态分配一个最大容量为MAXSIZE的数组空间

	if(!S.base)
	{
		exit(OVERFLOW);//存储分配失败
	}
	
	S.top = S.base;//top初始为base，表示空栈
	S.stacksize = MAXSIZE;//stacksize置为栈的最大容量MAXSIZE

	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2 判断顺序栈是否为空

• 当顺序栈为空的时候，top 和 base 指针指向的位置相同，top == base。

算法描述

//若栈为空，返回TRUE；否则返回FALSE
Status StackEmpty(SqStack S)
{
	if(S.top == S.base)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

2.3 求顺序栈长度

• 求出栈里头放了多少个元素。
• 用 top - base ，就能得出两个指针之间的元素个数。

算法描述

//求当前顺序栈中有多少个元素
int StackLength(SqStack S)
{
	return S.top - S.base;
}
1
2
3
4
5

2.4 清空顺序栈

• 将栈里面的数据元素全部清除，栈本身保留。

• 不管栈里面存着什么东西，只要当 top == base 的时候，就说明栈已经被清空了。

• 请空前提：base 要存在（栈空间存在）+

算法描述

//将顺序栈内的元素全部清除
Status ClearStack(SqStack S)
{
	if(S.base)//栈底指针不为空
	{
		S.top = S.base;
	}
	return OK;
}
1
2
3
4
5
6
7
8
9

2.5 销毁顺序栈

• 不仅栈里头没有元素了，连这块栈空间都被释放了。
  

算法描述

• 如果当前栈空间存在，先释放base指针，将栈最大元素的个数设置为0，然后将 top 和 base 指针置为空。

//销毁顺序栈，释放这块空间
Status DestoryStack(SqStack &S)
{
	if(S.base)//栈空间存在
	{
		delete S.base;
		S.stacksize = 0;
		S.base = S.top = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10

2.6 顺序栈的入栈

• 入栈操作时指在栈顶插入一个新的元素。

算法步骤

1. 判断栈是否满，若满栈则返回 ERROR ；
2. 将新元素压入栈顶；
3. 栈顶指针加1。

算法描述

//插入元素为e为新的栈顶元素
Status push(SqStack &S,SElemType e)
{
	if(S.top-S.base == S.stacksize)//栈满
	{
		return ERROR;
	}

	将元素e压入栈顶，栈顶指针加1
	*S.top = e;//
	S.top++ ;

	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.7 顺序栈的出栈

• 将栈顶元素出栈

算法步骤

1. 判断栈是否为空，若为空则返回 ERROR。
2. 让栈顶指针 top 减1，指向栈顶的元素，然后将栈顶元素出栈。

算法描述

//若栈不空，则删除s的栈顶元素；
//用e返回其值，并返回OK
Status Pop(SqStack &S,SElemType &e)
{
	if(S.top == S.base)//栈空
	{
		return ERROR;
	}
	--S.top;//栈顶指针下移,指向栈顶元素
	e = *S.top;//用e接收栈顶元素

	return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

三、链栈的表示和实现

1. 链栈的表示

• 链栈是运算受限的单链表，只能在链表头部进行操作。

类型定义

• 和普通单链表基本是一致的。

//链栈的存储结构
typedef struct StackNode
{
	ElemType data;
	struct StackNode* next;
	
}StackNode,*LinkStack;
1
2
3
4
5
6
7

栈的存储

• 从 a1 到 an 的每个数据都是由一个结点来存储的，每个结点都包含着一个数据域和一个指针域。
• 由于栈的主要操作是在栈顶进行插入和删除，显然以链表的头部作为栈顶是最方便的，而且没必要像单链表那样为了操作方便而附加一个头结点。
• 上面的每个结点的指针域里存着的实际是他们的前趋的地址。

链栈的特点

• 链表的头指针就是栈顶。
• 链栈不需要头结点。
• 基本不存在栈满的情况。
• 空栈相当于头指针指向空。
• 插入和删除仅在栈顶处执行。

2. 链栈的实现

2.1 链栈的初始化

• 链栈的初始化操作就是构造一个空栈，因为没必要设置头结点，所以直接将栈顶指针（头指针）置空即可。

算法描述

//构造一个空栈S，减栈顶指针置空
void InisStack(LinkStack &S)
{
	S = NULL;
	return OK;
}
1
2
3
4
5
6

2.2 判断链栈是否为空

• 判断头指针是不是空的，如果是则返回 TRUE，反之返回FALSE。
• 头指针为空的时候栈里头就没有元素了。

算法描述

//判断链栈是否为空
Status StackEmpty(LinkStack S)
{
	if(S == NULL)
	{
		return TRUE;
	}
	else
	{
		return FALSE;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

2.3 链栈的入栈

• 和顺序栈的入栈操作不同的是，链栈在 入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间。

算法步骤

1. 为入栈元素 e 分配空间，再用指针指向这块空间。
2. 将新结点的数据域设置为 e 。
3. 将新结点插入栈顶。
4. 修改栈顶指针 S 为 p（p 结点的 next 域就指向原来的栈顶结点，然后让 S 重新指向栈顶）。

算法描述

//在栈顶插入元素e
Status Push(LinkStack &S,SElemType e)
{
	p = new StackNode;//生成新结点p
	p -> data = e;//将新街点数据域置为e
	p -> next = S;//将新结点插入栈顶
	S = p;//修改栈顶指针为p

	return OK;
}
1
2
3
4
5
6
7
8
9
10

2.4 链栈的出栈

• 和顺序栈一样，链栈在出栈之前也需要判断栈是否为空，不同的是，链栈在出栈后需要释放出栈元素的栈顶空间。

算法步骤

1. 判断栈是否为空，若为空则返回 ERROR。
2. 用 e 来接收出栈的元素数据。
3. 临时保存栈顶元素的空间，以备释放。
4. 修改栈顶指针，指向新的栈顶元素。
5. 释放原来栈顶元素的空间。

算法描述

//删除 S 的栈顶元素，用 e 接收其返回值
Status pop(LinkStack &S,SElemType &e)
{
		if(NULL == S)
		{
				return ERROR;//栈空
		}
		e = S->data;//将栈顶元素赋给 e
		p = S;//用 p 临时保存栈顶元素空间，以备释放
		S = S->next;//修改栈顶指针

		delete p;//释放原来栈顶元素的空间

		
		return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.5 取链栈的栈顶元素

• 与顺序栈一样，当栈非空时，此操作返回当前栈顶元素的值，栈顶指针 S 保持不变。

算法描述

//返回S的栈顶元素，不修改栈顶指针
SElemType GetTop(LinkStack S)
{
	if(S != NULL)//栈非空
	{
		return S -> data;
		//返回栈顶元素的值，栈顶指针不变
	}
}
1
2
3
4
5
6
7
8
9

• 是获取栈顶元素的值，不是出栈，直接返回栈顶元素数据域的值，栈顶指针保持不变。