C++中棧結(jié)構(gòu)建立與操作詳細(xì)解析
什么是棧結(jié)構(gòu)
棧結(jié)構(gòu)是從數(shù)據(jù)的運(yùn)算來(lái)分類(lèi)的，也就是說(shuō)棧結(jié)構(gòu)具有特殊的運(yùn)算規(guī)則，即：后進(jìn)先出。
我們可以把棧理解成一個(gè)大倉(cāng)庫(kù)，放在倉(cāng)庫(kù)門(mén)口（棧頂）的貨物會(huì)優(yōu)先被取出，然后再取出里面的貨物。
而從數(shù)據(jù)的邏輯結(jié)構(gòu)來(lái)看，棧結(jié)構(gòu)起始就是一種線性結(jié)構(gòu)。
如果從數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)來(lái)進(jìn)一步劃分，棧結(jié)構(gòu)包括兩類(lèi)：
順序棧結(jié)構(gòu)：
即使用一組地址連續(xù)的內(nèi)存單元依次保存棧中的數(shù)據(jù)。在程序中，可以定義一個(gè)指定大小的結(jié)構(gòu)數(shù)組來(lái)作為棧，序號(hào)為0的元素就是棧低，再定義一個(gè)變量top保存棧頂?shù)男蛱?hào)即可。
鏈?zhǔn)綏＝Y(jié)構(gòu)：
即使用鏈表的的形式保存棧中各元素的值。鏈表首部（head指針?biāo)赶蛟兀闂ｍ?，鏈表尾部（指向地址為NULL）為棧底。
在棧結(jié)構(gòu)中只能在一端進(jìn)行操作，該操作端稱(chēng)為棧頂，另一端稱(chēng)為棧底。也就是說(shuō)，保存和取出的數(shù)據(jù)都只能從棧結(jié)構(gòu)的一端進(jìn)行。從數(shù)據(jù)的運(yùn)算角度來(lái)分析，棧結(jié)構(gòu)是按照“后進(jìn)先出”的原則處理結(jié)點(diǎn)數(shù)據(jù)的。
在棧結(jié)構(gòu)中，只有棧頂元素是可以訪問(wèn)的，棧結(jié)構(gòu)的數(shù)據(jù)運(yùn)算也是非常簡(jiǎn)單。一般棧結(jié)構(gòu)的基本操作只有兩個(gè)：
入棧（Push）：將數(shù)據(jù)保存到棧頂?shù)牟僮?。進(jìn)行入棧操作前，先修改棧頂指針，使其向上移一個(gè)元素位置，然后將數(shù)據(jù)保存到棧頂指針?biāo)傅奈恢谩?/P>
出棧（Pop）：將棧頂數(shù)據(jù)彈出的操作。通過(guò)修改棧頂指針，使其指向棧中的下一個(gè)元素。
接下來(lái)，我們使用C++語(yǔ)言建立順序棧，并完成順序棧結(jié)構(gòu)的基本運(yùn)算
準(zhǔn)備數(shù)據(jù)
準(zhǔn)備在棧操作中需要用到的變量及數(shù)據(jù)結(jié)構(gòu)等。
#define MAXLEN 50
struct DATA
{
string name;
int age;
};
struct StackType
{
DATA data[MAXLEN+1];
int top;
};
定義棧結(jié)構(gòu)的長(zhǎng)度MAXLEN，棧結(jié)構(gòu)的數(shù)據(jù)元素類(lèi)型DATA，以及棧結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)StackType。在數(shù)據(jù)結(jié)構(gòu)StackType中，data為數(shù)據(jù)元素，top為棧頂?shù)男蛱?hào)。當(dāng)top=0時(shí)，表示棧為空，當(dāng)top=MAXLEN時(shí)表示棧滿(mǎn)。
數(shù)組元素都是充下標(biāo)0開(kāi)始的，這里為了講述和理解方便，我們從下標(biāo)1開(kāi)始記錄數(shù)據(jù)結(jié)點(diǎn)，下標(biāo)0的位置不用。
初始化棧結(jié)構(gòu)
在使用棧結(jié)構(gòu)之前，首先需要?jiǎng)?chuàng)建一個(gè)空的順序棧，也就是初始化順序棧。順序棧的初始化操作如下：
（1）按照符號(hào)常量MAXLEN指定大小申請(qǐng)一片內(nèi)存空間，用來(lái)保存棧中的數(shù)據(jù)
（2）設(shè)置棧頂指針的值為0，表示一個(gè)空棧。
示例代碼如下：
StackType *STInit()
{
StackType *p;
if(p=new StackType) //申請(qǐng)?？臻g
{
p->top=0; //設(shè)置棧頂為0
return p; //返回棧頂指針
}
return NULL;
}
首先用new申請(qǐng)內(nèi)存，然后設(shè)置棧頂為0，然后返回申請(qǐng)內(nèi)存的首地址，申請(qǐng)失敗返回NULL;
判斷空棧
判斷棧結(jié)構(gòu)是否為空，如果是空棧，則表示該棧結(jié)構(gòu)中沒(méi)有數(shù)據(jù)，此時(shí)可以進(jìn)行入棧操作，但是不可以進(jìn)行出棧操作。
示例代碼如下：
int STIsEmpty(StackType *s)
{
int t;
t=(s->top==0); //通過(guò)棧頂?shù)闹颠M(jìn)行判斷
return t;
}
輸入?yún)?shù)s為一個(gè)指向操作的棧的指針。根據(jù)棧頂指針top判斷是否為0，判斷棧是否為空。
判斷滿(mǎn)棧
判斷棧結(jié)構(gòu)是否為滿(mǎn)。如果是滿(mǎn)棧，則表示該棧結(jié)構(gòu)中沒(méi)有多余的空間來(lái)保存額外數(shù)據(jù)。此時(shí)不可以進(jìn)行入棧操作，但是可以進(jìn)行進(jìn)棧操作。
示例代碼如下：
int STIsFull(StackType *s)
{
int t;
t=(s->top==MAXLEN);
return t;
}
輸入?yún)?shù)s為一個(gè)指向操作的棧的指針。根據(jù)棧頂指針top判斷是否和MAXLEN相等，判斷棧是否已滿(mǎn)。
清空棧
清空棧就是棧中所有的數(shù)據(jù)被清除。 示例代碼如下：
void STClear(StackType *s)
{
s->top=0;
}
將棧頂指針top設(shè)置為0，表示執(zhí)行清空棧操作。（這里只是邏輯上將棧中數(shù)據(jù)清空，實(shí)際上只是將top設(shè)置為0，以后再添加數(shù)據(jù)會(huì)覆蓋原來(lái)的數(shù)據(jù)）
釋放空間
釋放空間是釋放棧結(jié)構(gòu)所占用的內(nèi)存單元，使用delete釋放用new運(yùn)算符申請(qǐng)的內(nèi)存空間。
示例代碼如下：
void STFree(StackType *s)
{
delete s;
}
在程序中直接調(diào)用delete運(yùn)算符釋放已分配的內(nèi)存空間。一般在不需要使用棧結(jié)構(gòu)時(shí)調(diào)用該函數(shù)，特別是在程序結(jié)束的時(shí)候。
入棧
入棧（Push）是棧結(jié)構(gòu)的基本操作，主要操作是將數(shù)據(jù)元素保存到棧結(jié)構(gòu)。入棧操作的具體步驟如下：
（1）首先判斷棧頂top，如果top大于等于MAXLEN，則表示溢出，進(jìn)行出錯(cuò)處理。否則執(zhí)行以下操作。
（2）設(shè)置top=top+1(棧頂指針加1，指向入棧地址)
（3）將入棧呀U尿素保存到top指向的位置。
示例代碼如下:
int PushST(StackType *s,DATA data)
{
if((s->top+1)>MAXLEN)
{
cout<<"棧溢出"<<endl;
return 0;
}
s->data[++s->top]=data; //將元素壓入棧
return 1;
}
輸入?yún)?shù)s為一個(gè)指向操作的棧的指針，輸入?yún)?shù)data是需要入棧的數(shù)據(jù)元素。程序首先判斷棧是否溢出，如果溢出就給出警告，不進(jìn)行入棧操作，否則修改棧頂指針，即top先加1，然后將data放到top現(xiàn)在指向的數(shù)據(jù)單元。
出棧
出棧（Pop）是占據(jù)誒狗的基本操作，主要操作與入棧相反，它是從棧頂彈出一個(gè)數(shù)據(jù)元素，出棧操作的具體步驟如下：
（1）首先判斷棧頂top，如果top等于0，則表示為恐慌在哪，進(jìn)行出錯(cuò)處理。否則執(zhí)行下面的操作。
（2）將棧頂指針top所指向的位置的元素返回（實(shí)際是返回的指針）
（3）將top的減1，指向棧的下一個(gè)元素，原來(lái)?xiàng)ｍ數(shù)脑乇粡棾觥?BR>
DATA * PopST(StackType *s)
{
if(s->top==0)
{
cout<<"棧為空，不能再輸出！"<<endl;
exit(0);
}
return &(s->data[s->top--]);
}
當(dāng)棧中有數(shù)據(jù)時(shí)，該函數(shù)返回值是一個(gè)指向DATA類(lèi)型數(shù)據(jù)的指針。
讀取點(diǎn)結(jié)構(gòu)
讀取點(diǎn)結(jié)構(gòu)也就是讀取棧結(jié)構(gòu)中結(jié)點(diǎn)的數(shù)據(jù)。由于棧結(jié)構(gòu)只能在一端進(jìn)行操作，因此這里的讀操作其實(shí)就是讀站點(diǎn)的數(shù)據(jù)。
需要注意的是，讀節(jié)點(diǎn)數(shù)據(jù)的操作和出棧操作不同。讀結(jié)點(diǎn)操作僅僅是顯示棧頂結(jié)點(diǎn)數(shù)據(jù)的內(nèi)容，而出棧操作則將棧頂數(shù)據(jù)彈出。
示例代碼如下：
DATA *PeekST(StackType *s)
{
if(s->top==0)
{
cout<<"棧已空"<<endl;
exit(0);
}
return &(s->data[s->top]);
}
對(duì)比出棧的示例代碼，不難發(fā)現(xiàn)讀取點(diǎn)結(jié)構(gòu)同樣返回了棧頂結(jié)點(diǎn)的地址，但是卻沒(méi)有使top減1.
完整示例
下面是棧的基本操作的完整示例：
程序代碼：
#include<iostream>
#include<string>
using namespace std;
#define MAXLEN 50
struct DATA
{
string name;
int age;
};
struct StackType
{
DATA data[MAXLEN+1];
int top;
};
/******************初始化棧結(jié)構(gòu)****************/
StackType *STInit()
{
StackType *p;
if(p=new StackType) //申請(qǐng)?？臻g
{
p->top=0; //設(shè)置棧頂為0
return p; //返回棧頂指針
}
return NULL;
}
/****************判斷空棧**********************/
int STIsEmpty(StackType *s)
{
int t;
t=(s->top==0); //通過(guò)棧頂?shù)闹颠M(jìn)行判斷
return t;
}
/**********************判斷滿(mǎn)棧****************/
int STIsFull(StackType *s)
{
int t;
t=(s->top==MAXLEN);
return t;
}
/**********************清空棧**********************/
void STClear(StackType *s)
{
s->top=0;
}
/********************釋放空間********************/
void STFree(StackType *s)
{
delete s;
}
/**********************入棧***********************/
int PushST(StackType *s,DATA data)
{
if((s->top+1)>MAXLEN)
{
cout<<"棧溢出"<<endl;
return 0;
}
s->data[++s->top]=data; //將元素壓入棧
return 1;
}
/************************出棧***********************/
DATA * PopST(StackType *s)
{
if(s->top==0)
{
cout<<"棧為空，不能再輸出！"<<endl;
exit(0);
}
return &(s->data[s->top--]);
}
/**********************讀取點(diǎn)結(jié)構(gòu)*******************/
DATA *PeekST(StackType *s)
{
if(s->top==0)
{
cout<<"棧已空"<<endl;
exit(0);
}
return &(s->data[s->top]);
}
/*****************進(jìn)入主函數(shù)**********************/
int main()
{
StackType *stack;
DATA data,*p_data;
stack=STInit();
cout<<"===============入棧操作：============="<<endl;
cout<<"輸入姓名 ，年齡進(jìn)行入棧操作："<<endl;
//執(zhí)行入棧操作
while(1)
{
cin>>data.name>>data.age;
if(data.name=="0")
{
break; //當(dāng)姓名和年齡都是0的時(shí)候退出輸入
}else
{
PushST(stack,data);
}
}
p_data=PopST(stack);
cout<<"彈出棧頂元素"<<endl;
cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
p_data=PeekST(stack);
cout<<"輸出棧頂元素"<<endl;
cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
cout<<"================將所有的的數(shù)據(jù)出棧：============="<<endl;
while(1)
{
p_data=PopST(stack);
cout<<"name:"<<p_data->name<<",age:"<<p_data->age<<endl;
}
STFree(stack);
return 0;
}
程序運(yùn)行界面：
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言中指針的使用，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-02-02
C++計(jì)算整數(shù)序列的最長(zhǎng)遞增子序列的長(zhǎng)度操作
這篇文章主要介紹了C++計(jì)算整數(shù)序列的最長(zhǎng)遞增子序列的長(zhǎng)度操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-12-12
大家好，本篇文章主要講的是C語(yǔ)言打印各種圖案實(shí)例代碼，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話(huà)記得收藏一下，方便下次瀏覽2021-12-12
探討C++中不能聲明為虛函數(shù)的有哪些函數(shù)
下面小編就為大家?guī)?lái)一篇探討C++中不能聲明為虛函數(shù)的有哪些函數(shù)。希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧，祝大家游戲愉快哦2017-01-01
C++ Boost Lockfree超詳細(xì)講解使用方法
Boost是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱(chēng)。Boost庫(kù)是一個(gè)可移植、提供源代碼的C++庫(kù)，作為標(biāo)準(zhǔn)庫(kù)的后備，是C++標(biāo)準(zhǔn)化進(jìn)程的開(kāi)發(fā)引擎之一，是為C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)提供擴(kuò)展的一些C++程序庫(kù)的總稱(chēng)2022-11-11
C++vector的insert函數(shù)用法小結(jié)
std::vector::insert是C++中用于在指定位置插入元素的函數(shù),支持插入單個(gè)元素、多個(gè)相同元素、一個(gè)范圍的元素或初始化列表中的元素,插入操作可能會(huì)使插入點(diǎn)之后的迭代器失效,并且時(shí)間復(fù)雜度為O(n),本文介紹C++vector的insert函數(shù)用法小結(jié),感興趣的朋友一起看看吧2025-03-03
這篇文章主要介紹了C++迭代器失效的幾種情況總結(jié)，文中代碼非常詳細(xì)，幫助大家更好的了解學(xué)習(xí)，感興趣的朋友可以參考下2020-06-06
C/C++實(shí)現(xiàn)數(shù)字與字符串互相轉(zhuǎn)換的多種方法
在C/C++程序中,會(huì)需要把數(shù)字與字符串做出互相轉(zhuǎn)換的操作,用于實(shí)現(xiàn)程序想要的效果,下面將介紹多種方法實(shí)現(xiàn)數(shù)字與字符串互相轉(zhuǎn)換,文中有詳細(xì)的代碼示例供大家參考,需要的朋友可以參考下2024-08-08
list是順序容器的一種,list是一個(gè)雙向鏈表,使用list需要包含頭文件list,這篇文章主要給大家介紹了關(guān)于C++中l(wèi)ist的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2021-11-11
這篇文章主要介紹了C++中的數(shù)據(jù)內(nèi)存分布，主要從動(dòng)態(tài)內(nèi)存管理方式，內(nèi)存泄漏等方面介紹的，文中也有相關(guān)的示例代碼,需要的朋友可以參考下2023-05-05