文章目錄
- 堆疊
- 基本概念
- STL中的堆疊
- 順序堆疊
- 基本結構
- 初始化
- 入堆疊
- 出堆疊
- 取堆疊頂元素
- 基本遍歷
- 判斷堆疊空
- 鏈堆疊
- 基本結構
- 初始化
- 銷毀
- 入堆疊
- 出堆疊
- 取堆疊頂元素
- 判斷堆疊空
堆疊
基本概念
堆疊是一種特殊的資料存盤結構，采用先進后出的規則，先入堆疊的元素被后入堆疊的元素“擠壓”在下面，出堆疊的時候只能等“壓在它身上”的元素都出去以后，它才能出去，就像把東西放進一個豎桶：
如圖，1是最先進去的，所以只有別的元素都出去了，它才出得去
STL中的堆疊
C++的庫里其實給我們寫好了堆疊這一資料結構，直接呼叫就可以
#include <iostream>
#include <stack> //STL中堆疊的頭檔案
using namespace std;
stack<int> s; //宣告一個int型的堆疊
int main()
{
int n,a[100];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
s.push(a[i]); //a[i]入堆疊
}
while (!s.empty()){ //判斷堆疊是不是空的，如果堆疊空，empty函式回傳1
cout<<s.top()<<" "; //top函式——回傳堆疊頂元素，但不出堆疊
s.pop(); //pop函式——堆疊頂元素出堆疊
}
return 0;
}
輸入：
5
1 2 3 4 5
輸出：
5 4 3 2 1
STL雖好，可不要貪杯哦
老師會查代碼，所以就算你用STL過了，估計也得涼涼
畢竟是初學，為了更好地熟悉堆疊的基本操作，我們還是需要手寫一下的！
順序堆疊
就是用順序表實作堆疊這一資料結構
基本結構
#include <iostream>
#define maxSize 1000 //用來規定堆疊的大小
using namespace std;
struct Stack{
int data[maxSize]; //順序表
int top; //記錄目前的堆疊頂元素下標
};
初始化
top用來記錄目前堆疊頂元素的下標，所以它的取值范圍應該是0~maxSize-1，
初始化時，將top初始化為-1，這樣以后判斷堆疊是不是空的，就可以用if(s.top==-1)來判斷，
void initStack(Stack &s){
s.top=-1;
}
入堆疊
將一個元素入堆疊，需要有兩個步驟：
- 將元素存入順序表
data - 改變
top
void push(Stack &s,int value){
s.top++; //先操作top，便于利用下標修改順序表
s.data[s.top]=value;
}
出堆疊
出堆疊時很簡單，只要top--就可以了，因為順序表完全依賴top進行訪問，所以即使top--后，原來的資料還是存在順序表里，并沒有受到影響，但一旦有新的元素入堆疊，在top的影響下新元素會自動覆寫老元素
void pop(Stack &s){
s.top--;
}
取堆疊頂元素
直接回傳即可
int top(Stack s){
return s.data[s.top];
}
基本遍歷
while (!empty(head)){
cout<<top(head)<<endl;
pop(head);
}
判斷堆疊空
對于判斷堆疊空的函式，一般的設計規則是堆疊空則回傳1（真），堆疊非空則回傳0（假），所以只需要這樣寫：
bool empty(Stack s){
return s.top==-1; //非空：empty=0，類比Matlab里面畫沖激函式的思想
}
ps. bool是一種變數型別，就像int一樣，但不同的是int型別的變數取值范圍很大，可以是任何一個整數（不超存盤范圍的前提下），但bool型的變數只有兩種可能的取值——1或0，即true或false
鏈堆疊
鏈堆疊就是用鏈表實作堆疊的存盤結構，還是鏈表那一套操作，甚至它比鏈表簡單——它白白加了一個先進后出的限制，搞得你不必考慮尾插法/頭插法建表，不必考慮不洗掉情況下的遍歷，只要會一些基本鏈表操作即可
ps. 我寫完才發現，書上給的鏈堆疊沒有頭結點，它第一個結點就開始存盤資料了，而我套用的是鏈表的模版，所以我給的代碼是有頭結點的，大家如果有把兩個結合著看的，注意一下這一點！
pps. 鏈堆疊跟順序堆疊的區別其實就是換了個載體，所以順序堆疊的基本思路講解完全可以搬到下面的鏈堆疊里來，我就不多寫一遍啦！
基本結構
struct LinkStack{
int data;
LinkStack *next;
};
初始化
void initLinkStack(LinkStack *&head){
head=new LinkStack ();
}
銷毀
void destoryLinkStack(LinkStack *&head){
LinkStack *pre=head,*p=head->next;
while (p!=NULL){
delete pre;
pre=p;
p=p->next;
}
delete pre;
}
入堆疊
void push(LinkStack *&head,int value){
LinkStack *p=new LinkStack();
p->data=value;
p->next=head->next;
head->next=p;
}
出堆疊
void pop(LinkStack *&head){
LinkStack *p=new LinkStack();
p=head->next;
head->next=p->next;
delete p;
}
取堆疊頂元素
int top(LinkStack *head){
return head->next->data;
}
判斷堆疊空
bool empty(LinkStack *head){
return head->next==NULL;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/161378.html
標籤：其他
下一篇：Hadoop源代碼分析【1-5】