3.3、堆疊的表示和操作的實作
3.3.1、堆疊的型別定義
堆疊的基本操作的抽象資料型別定義：
ADT Stack {
資料物件； D = {ai | ai 屬于 ElementSet, i = 1, 2, ... , n, n >= 0}
資料關系： R1 = {<ai - 1, ai> | ai - 1, ai 屬于 D, i = 2, ... , n }
約定an端為堆疊頂，a1端為堆疊底
基本操作：
InitStack(&S)
操作結果：構造一個空堆疊
DestroyStack(&S)
初始條件：堆疊S已存在
操作結果：堆疊S被銷毀
ClearStack(&S)
初始條件：堆疊S已存在
操作結果：將堆疊S清空為空堆疊
StackEmpty(S)
初始條件：堆疊S已存在
操作結果：若堆疊S為空堆疊，則回傳true，否則則回傳false
StackLength(S)
初始條件：堆疊S已存在
操作結果：回傳S的元素個數，即堆疊的長度
GetTop(S, e)
初始條件：堆疊S已存在
操作結果：回傳S的堆疊頂元素，不修改堆疊頂的指標
Push(&S, e)
初始條件：堆疊S已存在
操作結果：插入元素e為新的堆疊頂元素
Pop(S)
初始條件：堆疊S已存在
操作結果：洗掉S的堆疊頂元素，并用e回傳其值
StackTraverse(S)
初始條件：堆疊S已存在且非空
操作結果：從堆疊底到堆疊頂依次對S的每個資料元素進行訪問
}ADT Stack
3.3.2、順序堆疊的表示和實作
-
堆疊的存盤方式有兩種：順序存盤和鏈式存盤
- 堆疊的順序存盤——順序堆疊
- 堆疊的鏈式存盤——鏈堆疊
-
存盤方式：同一般的線性表的順序存盤結構完全相同，
-
利用一組地址連續的存盤單元依次存放自堆疊底到堆疊頂的資料元素，堆疊底一般在低地址端
- 附設top，指示堆疊頂元素在順序堆疊中的位置
- 另設base指標，指示堆疊底元素在順序堆疊中的位置
為了方便操作，通常top指示真正的堆疊頂元素之上的下標地址
順序堆疊的定義：
#define MAXSIZE 100 // 順序堆疊存盤空間的初始分配量
typedef struct
{
SElemType *base; // 堆疊底指標
SElemType *top; // 堆疊頂指標
int stacksize; // 堆疊可用的最大容量
}SqStack;
說明：
- base為堆疊底指標，初始化完成之后，堆疊底指標始終指向堆疊底的位置，若base為NULL，則表明堆疊的結構不存在，top為堆疊頂指標，其初值指向堆疊底，每插入新的堆疊頂元素時，指標top增1；洗掉堆疊頂元素時，指標top減1.因此堆疊空時top和base的值相等，即空堆疊：base == top；堆疊非空時，top始終指向堆疊頂元素的上一個位置，堆疊滿的標志：top - base == stacksize
- stacksize指示堆疊可使用的最大容量，后面的演算法將stacksize置為MAXSIZE
- 上溢：堆疊已經滿，又要壓入元素
- 下溢：堆疊已經空，還要彈出元素
順序堆疊的表示：
1、順序堆疊的初始化
【演算法步驟】
- 為順序堆疊動態分配一個最大容量為MAXSIZE的陣列空間，使base指向這段空間的基地址，即堆疊底
- 堆疊頂指標top初始為base，表示堆疊為空
- stacksize置為堆疊的最大容量MAXSIZE
【演算法描述】
Status InitStack(SqStack &S)
{ // 構造一個空堆疊
S.base = new SElemType[MASIZE]; // 或S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));
if (!S.base) exit (OVERFLOW); // 存盤分配失敗
S.top = S.base; // 堆疊頂指標等于堆疊底指標
S.stacksize = MAXSIZE; // stacksize置為堆疊的最大容量MAXSIZE
return OK;
}
2、判斷順序堆疊是否為空
判斷條件：是否滿足top == base
Status StackEmpty(SqStack S)
{ // 若堆疊為空，回傳TRUE；否則回傳FALSE
if (S.top == S.base)
return TRUE;
else
return FALSE;
}
3、求順序堆疊長度
int StackLength(SqStack S)
{
return S.top - S.base;
}
4、清空順序堆疊
Status ClearStack(SqStack S)
{
if (S.base) S.top = S.base;
return OK;
}
5、銷毀順序堆疊
Status DestroyStack(SqStack &S)
{
if (S.base)
{
delete S.base;
S.stacksize = 0;
S.base = S.top =NULL;
}
return OK;
}
6、順序堆疊的入堆疊
- 判斷堆疊是否滿，若滿則回傳ERROR
- 將新元素壓入堆疊頂，堆疊頂指標加1
Status Push(SqStack &S, SElemType e)
{ // 插入元素e為新的堆疊頂元素
if (S.top - S.base == S.stacksize) return ERROR; // 堆疊滿
*S.top++ = e;
// 或 *S.top = e; S.top++;
return OK;
}
7、順序堆疊的出堆疊
【演算法步驟】
- 判斷堆疊是否為空，若為空則回傳ERROR
- 堆疊頂指標減1，堆疊頂元素出堆疊
【演算法描述】
Status Pop(SqStack &S, SElemType &e)
{ // 洗掉S的堆疊頂元素，用e回傳其值
if (S.top == S.base) return ERROR; // 堆疊空
e = *--S.top; // 堆疊頂指標減1，將堆疊頂元素賦給e
// 或 e = S.top; S.top--;
return OK;
}
8、取堆疊頂元素
- 當堆疊非空時，此操作回傳當前堆疊頂的元素值，堆疊頂指標保持不變，
【演算法描述】
SElemType GetTop(SqStack S)
{ // 回傳S的堆疊頂元素，不修改堆疊頂指標
if(S.top != S.base) // 堆疊非空
return *(S.top - 1); // 回傳堆疊頂元素的值，堆疊頂指標不變
}
3.3.3、鏈堆疊的表示和實作
- 鏈堆疊是運算受限的單鏈表，只能在鏈表頭部進行操作
- 鏈堆疊的指標指向的元素是資料域的前驅
- 鏈表的頭指標就是堆疊頂、不需要頭結點，基本不存在堆疊滿的情況
- 空堆疊相當于頭指標指向空
- 插入和洗掉僅在堆疊頂處執行
鏈堆疊的定義：
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStack;
LinkStack S;
1、鏈堆疊的初始化
void InitStack(LinkStack &S)
{ // 構造一個空堆疊，堆疊頂指標置為空
S = NULL;
return OK;
}
2、判斷鏈堆疊是否為空
Status StackEmpty(LinkStack S)
{
if (S == NULL) return NULL;
elese return FALSE;
}
3、鏈堆疊的入堆疊
【演算法步驟】
- 為入堆疊元素e分配空間，用指標p指向
- 將新結點資料域置為e
- 將新結點插入堆疊頂
- 修改堆疊頂指標為p
【演算法描述】
Status Push(LinkList &S, SElemType e)
{ // 在堆疊頂插入元素e
p = new StackNode; // 生成新的結點
p -> data = https://www.cnblogs.com/javaxiaohao/archive/2022/10/13/e; // 將新結點的資料域置為e
p -> next = S; // 將新結點插入堆疊頂
S = p; // 修改堆疊頂指標為p
return OK;
}
4、鏈堆疊的出堆疊
【演算法步驟】
- 判斷堆疊是否為空，若為空則回傳ERROR
- 將堆疊頂元素賦給e
- 臨時保存堆疊頂指標，指向新的堆疊頂元素
- 釋放原堆疊頂元素的空間
【演算法描述】
Status Pop(LinkStack &S, SElemType &e)
{ // 洗掉S的堆疊頂元素，用e回傳其值
if (S == NULL)
return ERROR; // 堆疊空
e = S -> data; // 將堆疊頂元素賦給e
p = S; // 用p臨時保存堆疊頂元素空間，以備釋放
S = S -> next; // 修改堆疊頂指標
delete p; // 釋放原堆疊頂元素的空間
return OK;
}
5、取堆疊頂元素
與順序堆疊一樣，當堆疊非空時，此操作回傳當前堆疊頂元素的值，堆疊頂指標S保持不變，
【演算法描述】
SElemType GetTop(LinkList S)
{ // 回傳S的堆疊頂元素，不修改堆疊頂元素
if (S != NULL) // 堆疊非空
{
return S -> data; // 回傳堆疊頂元素的值，堆疊頂指標不變
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/514194.html
標籤：其他
上一篇：leet Code [34. Find First and Last Position of Element in Sorted Array]
下一篇：學習筆記-命令執行漏洞