淺析順序結(jié)構(gòu)存儲(chǔ)的棧
棧定義：僅限在表尾進(jìn)行插入和刪除的線性表
棧的特點(diǎn)：
1）一般來說能在表尾進(jìn)行進(jìn)棧和出棧的數(shù)據(jù)
2）先進(jìn)后出（last in first out ）
3）棧會(huì)有棧頂，棧底，通常棧底為高地址，棧頂為高地址，如下圖所示
操作系統(tǒng)一般會(huì)在內(nèi)存劃出一塊，專門用于棧操作，當(dāng)然這個(gè)跟普通的操作有些區(qū)別：比如存放數(shù)組，地址是增加的；但是在存入數(shù)據(jù)到棧，地址則是不斷減小的
棧的存儲(chǔ)結(jié)構(gòu)：
typedef struct _SQSTACK
{
SElemType* base;
SElemType* top;
int stacksize;
}
SqStack;
數(shù)據(jù)定義：
//默認(rèn)的存儲(chǔ)空間的大小和空間增長(zhǎng)大小
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
//存儲(chǔ)數(shù)據(jù)的類型定義
#ifndef INT_TYPE
#define INT_TYPE
#endif // INT_TYPE
#ifdef INT_TYPE
typedef int SElemType;
#elif defined FLOAT_TYPE
typedef float SElemType;
#elif defined STRING_TYPE
typedef char* SElemType;
#elif defined STRUCT_TYPE
typedef void* SElemType;
#endif
棧的操作，會(huì)涉及到初始化棧，銷毀棧，進(jìn)棧（入棧），出棧，還有判斷?？眨瑮４笮?，以及清空棧，如下：
棧的初始化：
//初始化棧
int InitStack(SqStack *S)
{
S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if (!S->base)
{
return -1;
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return 0;
}
棧才初始化，里面還沒有數(shù)據(jù)，這時(shí)候top，base都指向分配空間的基地址，表示?？?BR>銷毀棧：
//銷毀棧
int DestroyStack(SqStack *S)
{
if (S->base)
{
free(S->base);
S->base = NULL;
S->top = NULL;
S->stacksize = 0;
}
return 0;
}
如果棧存在，就銷毀地址空間，將棧尺寸置0
進(jìn)棧：
int Push(SqStack *S, const SElemType data)
{
assert(S->base != NULL);
if (S->top - S->base >= STACK_INIT_SIZE)
{
S->base = (SElemType*)realloc(S->base,
(STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SElemType));
if (!S->base)
{
return -1;
}
S->top = S->base + S->stacksize;
S->stacksize += STACK_INCREMENT;
}
*S->top++ = data;
return 0;
}
如果棧存在，就銷毀地址空間，將棧尺寸置0
進(jìn)棧：
int Push(SqStack *S, const SElemType data)
{
assert(S->base != NULL);
if (S->top - S->base >= STACK_INIT_SIZE)
{
S->base = (SElemType*)realloc(S->base,
(STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SElemType));
if (!S->base)
{
return -1;
}
S->top = S->base + S->stacksize;
S->stacksize += STACK_INCREMENT;
}
*S->top++ = data;
return 0;
}
如果棧的大小大于已分配長(zhǎng)度，重新分配空間，并使棧頂重新指向新的位置，之后就將數(shù)據(jù)存入當(dāng)前棧頂指向的位置，然后棧頂+1
出棧：
//出棧
int Pop(SqStack *S, SElemType *data)
{
assert(S->base != NULL);
if (S->base == S->top)
{
return -1;
}
*data = *(--S->top);
return 0;
}
首先將棧頂位置-1，然后取得當(dāng)前位置的值
以下為輔助函數(shù)，如下：
//棧是否為空
int IsStackEmpty(const SqStack &S)
{
return ((S.base == S.top) ? true:false);
}
//得到棧的長(zhǎng)度
int GetStackLength(const SqStack &S)
{
assert(S.base != NULL);
return S.stacksize;
}
//清空棧
int ClearStack(SqStack *S)
{
assert(S->base != NULL);
if (S->base != S->top)
{
S->top = S->base;
}
S->stacksize = 0;
return 0;
}
相關(guān)文章
希望本文可以對(duì)初學(xué)C的朋友提供一點(diǎn)幫助，也希望能和其他朋友進(jìn)行交流。其中理解不對(duì)的地方若能得到指正和建議，本人將不勝感激2013-05-05
C++實(shí)現(xiàn)數(shù)組的排序/插入重新排序/以及逆置操作詳解
將新的數(shù)字與已經(jīng)排序好的數(shù)組中的數(shù)字一一比較，直到找到插入點(diǎn)，然后將插入點(diǎn)以后的數(shù)字都向后移動(dòng)一個(gè)單位（a[i+1]=a[i]），然后將數(shù)據(jù)插入即可2013-10-10
利用C++?OpenCV?實(shí)現(xiàn)從投影圖像恢復(fù)仿射特性
我們通過相機(jī)拍攝的圖片存在各種畸變，其中投影畸變使得原本平行的直線不再平行，就會(huì)產(chǎn)生照片中近大遠(yuǎn)小的效果。本文將具體介紹如何利用OPenCV實(shí)現(xiàn)從投影圖像恢復(fù)仿射特性，接下來跟著小編一起學(xué)習(xí)吧2021-11-11
這篇文章主要為大家詳細(xì)介紹了C語言中幾種進(jìn)程間通訊的方式，文中的示例代碼講解詳細(xì)，?對(duì)我們學(xué)習(xí)或工作有一定的借鑒價(jià)值，需要的可以參考一下2022-08-08
C++實(shí)現(xiàn)LeetCode(309.買股票的最佳時(shí)間含冷凍期)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(309.買股票的最佳時(shí)間含冷凍期),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
C語言結(jié)構(gòu)體數(shù)組同時(shí)賦值的另類用法
今天小編就為大家分享一篇關(guān)于C語言結(jié)構(gòu)體數(shù)組同時(shí)賦值的另類用法，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12
函數(shù)重載是C++多態(tài)（靜態(tài)多態(tài)）的特征體現(xiàn)，它可以允許重復(fù)使用同一個(gè)函數(shù)名（籃子）的函數(shù)，但是函數(shù)的參數(shù)列表（籃子裝的東西）是可以不一樣的。下面就簡(jiǎn)單講講C++中函數(shù)重載的相關(guān)應(yīng)用吧2023-04-04
C/C++獲取Windows平臺(tái)CPU占用率的方法
最近在做系統(tǒng)信息相關(guān)的接口,為了實(shí)現(xiàn)跨平臺(tái),故在linux和Windows平臺(tái)獲取占用率信息,文章主要介紹Windows下的方法,文中給出了參考代碼,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了C++ lambda 捕獲模式與右值引用的使用,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
C++11中的時(shí)間庫std::chrono（引發(fā)關(guān)于時(shí)間的思考）
這篇文章主要介紹了C++11中的時(shí)間庫std::chrono（引發(fā)關(guān)于時(shí)間的思考）,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-04-04