淺析順序結(jié)構(gòu)存儲(chǔ)的棧
棧定義：僅限在表尾進(jìn)行插入和刪除的線性表
棧的特點(diǎn)：
1）一般來(lái)說(shuō)能在表尾進(jìn)行進(jìn)棧和出棧的數(shù)據(jù)
2）先進(jìn)后出（last in first out ）
3）棧會(huì)有棧頂，棧底，通常棧底為高地址，棧頂為高地址，如下圖所示
操作系統(tǒng)一般會(huì)在內(nèi)存劃出一塊，專(zhuān)門(mén)用于棧操作，當(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ù)的類(lèi)型定義
#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ì)涉及到初始化棧，銷(xiāo)毀棧，進(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;
}
棧才初始化，里面還沒(méi)有數(shù)據(jù)，這時(shí)候top，base都指向分配空間的基地址，表示?？?BR>銷(xiāo)毀棧：
//銷(xiāo)毀棧
int DestroyStack(SqStack *S)
{
if (S->base)
{
free(S->base);
S->base = NULL;
S->top = NULL;
S->stacksize = 0;
}
return 0;
}
如果棧存在，就銷(xiāo)毀地址空間，將棧尺寸置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;
}
如果棧存在，就銷(xiāo)毀地址空間，將棧尺寸置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)文章
本文給大家介紹了C++中的六個(gè)函數(shù)，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2018-05-05
C++ 使用PrintWindow實(shí)現(xiàn)窗口截圖功能
這篇文章主要介紹了C++ 如何使用PrintWindow實(shí)現(xiàn)窗口截圖功能，文中示例代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-08-08
Linux/C++多線程實(shí)例學(xué)習(xí)十字路口車(chē)輛調(diào)度
這篇文章主要為大家介紹了Linux/C++多線程實(shí)例學(xué)習(xí)十字路口車(chē)輛調(diào)度示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
這篇文章主要介紹了C語(yǔ)言中求解圖形的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
C語(yǔ)言中一些將字符串轉(zhuǎn)換為數(shù)字的函數(shù)小結(jié)
這篇文章主要介紹了C語(yǔ)言中一些將字符串轉(zhuǎn)換為數(shù)字的函數(shù)小結(jié),分別為atoi()函數(shù)和atol()函數(shù)以及atof()函數(shù),需要的朋友可以參考下2015-08-08
C++類(lèi)成員函數(shù)后面加const問(wèn)題
這篇文章主要介紹了C++類(lèi)成員函數(shù)后面加const問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-11-11
深入探索C++中stack和queue的底層實(shí)現(xiàn)
這篇文章主要介紹了C++中的stack和dequeue的底層實(shí)現(xiàn),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-09-09
C++實(shí)現(xiàn)LeetCode(71.簡(jiǎn)化路徑)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(71.簡(jiǎn)化路徑),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
函數(shù)指針是一個(gè)指針變量,它可以存儲(chǔ)函數(shù)的地址,然后使用函數(shù)指針,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言進(jìn)階教程之函數(shù)指針的相關(guān)資料,需要的朋友可以參考下2022-04-04
C++深入探索類(lèi)真正的形態(tài)之struct與class
前邊我們所定義的類(lèi)，均是使用struct關(guān)鍵字來(lái)定義，但是C++中真正用于定義類(lèi)的關(guān)鍵字為class，因?yàn)橐狢++兼容C，所以保留struct關(guān)鍵字，struct與class的用法完全相同2022-04-04