目錄
- 資料結構（二）—堆疊
- 一、堆疊的概念及特點
- 概念
- 特點
- 基本操作
- 分類
- 二、順序堆疊實作
- 存盤結構
- 初始化
- 入堆疊
- 出堆疊
- 取堆疊頂元素
- 驗證
- 三、鏈堆疊實作
- 存盤結構
- 初始化
- 入堆疊
- 出堆疊
- 取堆疊頂元素
- 驗證
- 四、總結
- 一、堆疊的概念及特點
資料結構（二）—堆疊
一、堆疊的概念及特點
概念
堆疊（stack）是限定僅在表尾進行插入或洗掉操作的線性表，其表尾端稱為堆疊頂（top），表頭端稱為堆疊底（bottom），不含元素的空表稱為空堆疊，
特點
后進先出（LIFO，Last In First Out）
基本操作
- 初始化
- 入堆疊
- 出堆疊
- 取堆疊頂元素
分類
根據存盤結構不同，我們又可以把堆疊分為順序堆疊和鏈堆疊
下面我們分別來實作這兩種存盤結構的堆疊，
二、順序堆疊實作
順序堆疊一般是用陣列來實作，存在兩個指標，堆疊頂、堆疊底指標，分別指向陣列的尾部和頭部，如下圖：
堆疊空的條件即是top==base，比較好理解，下面直接上代碼：
存盤結構
//堆疊-順序堆疊實作
#include<iostream>
using namespace std;
int const N=100;
//順序堆疊的存盤結構
typedef int SElemType;
typedef struct
{
SElemType *base;//堆疊底指標
SElemType *top;//堆疊頂指標
int stackSize;//堆疊可用的最大容量
}SqStack;
初始化
//堆疊初始化
void InitStack(SqStack &s)
{
s.base=new int[N];//為順序堆疊動態分配一個最大容量為N的陣列空間
s.top=s.base;//top初始為base，表示空堆疊
s.stackSize=N;//stacksize置為堆疊的最大容量N
}
入堆疊
//入堆疊，插入元素data為新的堆疊頂元素
void Push(SqStack &s, SElemType data)
{
if(s.top-s.base==s.stackSize)
{//堆疊滿
cout<<"堆疊已滿！"<<endl;
return;
}
*s.top=data;//將元素data入堆疊
*s.top++;//堆疊頂指標加1
}
出堆疊
//出堆疊，洗掉堆疊頂元素，用data回傳其值
void Pop(SqStack &s,SElemType &data)
{
if(s.base==s.top)
{
cout<<"堆疊為空！"<<endl;
return;
}
data=https://www.cnblogs.com/gentlesunshine/p/*s.top;
*s.top--;//堆疊頂指標減1
}
取堆疊頂元素
//回傳s的堆疊頂元素，不修改堆疊頂指標
int GetTop(SqStack &s)
{
if(s.base!=s.top)//堆疊非空
return *(s.top-1);
}
驗證
int main()
{
SqStack myStack;
InitStack(myStack);
Push(myStack,1);
Push(myStack,2);
Push(myStack,3);//將1，2，3依次入堆疊
cout<<"堆疊頂元素："<<GetTop(myStack)<<endl;//獲取當前堆疊頂元素
int a;
Pop(myStack,a);//出堆疊
cout<<"彈出堆疊頂元素后，現堆疊頂元素為"<<GetTop(myStack)<<endl;//獲取當前堆疊頂元素
return 0;
}
運行以上代碼后，運行結果如下：
三、鏈堆疊實作
鏈堆疊一般采用單鏈來表示：
存盤結構
//鏈堆疊實作
#include<iostream>
using namespace std;
//鏈堆疊的存盤結構
typedef char ElemType;
typedef struct StackNode
{
ElemType Data;//資料域
StackNode *Next;//指標域
}StackNode,*LinkStack;
初始化
//初始化，構造一個空堆疊S，堆疊頂指標置空
void InitStack(LinkStack &S)
{
S=NULL;
}
入堆疊
與順序站不同的是，鏈堆疊在入堆疊前不需要判斷堆疊是否滿，只需要為入堆疊元素動態分配一個結點空間，如下圖：
//入堆疊，在堆疊頂插入元素data
void Push(LinkStack &S,ElemType data)
{
StackNode *p=new StackNode();//生成新結點
p->Data=https://www.cnblogs.com/gentlesunshine/p/data;//將新節點資料域置為data
p->Next=S;//將新節點插入堆疊頂
S=p;//修改堆疊頂指標為p
}
出堆疊
和順序堆疊一樣，出堆疊是需要判斷堆疊是否為空，不同的是，鏈堆疊在出堆疊后需要釋放出堆疊元素的堆疊頂空間，如下圖：
//出堆疊，洗掉S的堆疊頂元素，并用data回傳其值
void Pop(LinkStack &S,ElemType &data)
{
if(S==NULL)
{//堆疊為空
cout<<"堆疊為空！"<<endl;
return;
}
data=https://www.cnblogs.com/gentlesunshine/p/S->Data;//將堆疊頂元素賦給data
StackNode *p=S;//用p臨時保存堆疊頂元素空間，以備釋放
S=S->Next;//修改堆疊頂元素
delete p;//釋放原堆疊頂元素的空間
}
取堆疊頂元素
//回傳S堆疊頂元素，不修改堆疊頂指標
ElemType GetTop(LinkStack &S)
{
if(S!=NULL)//堆疊非空
return S->Data;
}
驗證
//列印堆疊
void PrintStack(LinkStack &S)
{
if(S!=NULL)
{
StackNode *p=S;
while(p!=NULL)
{
cout<<p->Data<<"\t";
p=p->Next;
}
cout<<"\n";
}
}
int main()
{
LinkStack LS;
InitStack(LS);//初始化堆疊
Push(LS,'a');
Push(LS,'b');
Push(LS,'C');//將a b C依次入堆疊
PrintStack(LS);//列印當前堆疊
ElemType a;
Pop(LS,a);//將C出堆疊
PrintStack(LS);//列印當前堆疊
cout<<"堆疊頂元素為："<<GetTop(LS);//當前堆疊頂元素元素
return 0;
}
運行結果如下：
四、總結
堆疊的實作相對來說比較簡單，主要掌握順序堆疊和鏈堆疊的實作即可~
參考資料：《資料結構（C語言）（第2版）》 嚴蔚敏等著
寫文不易~因此做以下申明：
1.博客中標注原創的文章，著作權歸原作者 煦陽（本博博主） 所有；
2.未經原作者允許不得轉載本文內容，否則將視為侵權；
3.轉載或者參考本文內容請注明來源及原作者；
4.對于不遵守此宣告或者其他違法使用本文內容者，本人依法保留追究權等，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/63633.html
標籤：其他