C語(yǔ)言棧順序結(jié)構(gòu)實(shí)現(xiàn)代碼
/**
* @brief C語(yǔ)言實(shí)現(xiàn)的順序結(jié)構(gòu)類(lèi)型的棧
* @author wid
* @date 2013-10-29
*
* @note 若代碼存在 bug 或程序缺陷, 請(qǐng)留言反饋, 謝謝!
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
typedef struct Point2D
{
int x;
int y;
}ElemType; //棧元素結(jié)構(gòu)
typedef struct
{
ElemType *btm; //棧底
ElemType *top; //棧頂
int height; //棧高
int size; //?？偞笮?BR>}ArrStack; //棧結(jié)構(gòu)
//棧方法聲明
ArrStack *CreateStack( int nSize ); ///創(chuàng)建一個(gè)大小為nSize的棧
void DestroyStack( ArrStack *pStack ); ///銷(xiāo)毀棧 pStack
void ClearStack( ArrStack *pStack ); ///清空棧 pStack 內(nèi)的元素
int GetHeight( ArrStack *pStack ); ///獲取棧 pStack 的高度
int GetSize( ArrStack *pStack ); ///獲取棧 pStack 的總?cè)萘?BR>int IsEmpty( ArrStack *pStack ); ///檢測(cè)棧 pStack 是否為空棧
int Push( ArrStack *pStack, ElemType *pt ); ///將元素 pt 壓入棧 pStack
int Pop( ArrStack *pStack, ElemType *pt ); ///將棧頂元素出棧到 pt
int GetTop( ArrStack *pStack, ElemType *pt ); ///獲取棧頂元素到 pt
void ForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) ); ///從棧底到棧頂?shù)拿總€(gè)元素依次執(zhí)行 func 函數(shù)
void ReForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) ); ///從棧頂?shù)綏５椎拿總€(gè)元素依次執(zhí)行 func 函數(shù)
//棧方法實(shí)現(xiàn)
/**
* @brief 創(chuàng)建一個(gè)大小為 nSize 的棧
*
* @param nSize 棧的初始大小
*
* @return 返回指向創(chuàng)建的棧的指針
*
* @note nSize 初始大小需大于0
*/
ArrStack *CreateStack( int nSize )
{
//根據(jù)棧結(jié)構(gòu)創(chuàng)建一個(gè)棧
ArrStack *pStack = (ArrStack *)malloc( sizeof(ArrStack) );
//申請(qǐng)棧初始空間
pStack->btm = (ElemType *)calloc( nSize, sizeof(ElemType) );
//令棧頂指向棧底元素
pStack->top = &pStack->btm[0];
//初始化棧高度為 0
pStack->height = 0;
//初始化棧大小為初始大小
pStack->size = nSize;
return pStack;
}
/**
* @brief 銷(xiāo)毀棧 pStack
*
* @param pStack 指向待銷(xiāo)毀的棧的指針
*
* @return void
*/
void DestroyStack( ArrStack *pStack )
{
//釋放棧內(nèi)元素
free( pStack->btm );
//釋放棧
free( pStack );
}
/**
* @brief 清空棧內(nèi)元素
*
* @param pStack 指向待清空元素的棧的指針
*
* @return void
*/
void ClearStack( ArrStack *pStack )
{
//令棧頂指向棧底
pStack->top = &pStack->btm[0];
//將棧高度置為 0
pStack->height = 0;
}
/**
* @brief 獲取棧 pStack 的高度
*
* @param pStack 指向待獲取高度的棧的指針
*
* @param 返回當(dāng)前棧的高度
*/
int GetHeight( ArrStack *pStack )
{
return pStack->height;
}
/**
* @brief 獲取棧 pStack 的總?cè)萘?BR>*
* @param pStack 指向待獲取總?cè)萘康臈５闹羔?BR>*
* @return 返回棧的當(dāng)前總?cè)萘?BR>*/
int GetSize( ArrStack *pStack )
{
return pStack->size;
}
/**
* @brief 檢測(cè)棧 pStack 是否為空棧
*
* @param pStack 指向待檢測(cè)的棧的指針
*
* @return 若棧為空, 則返回 TRUE, 否則返回 FALSE
*/
int IsEmpty( ArrStack *pStack )
{
return pStack->height == 0 ? TRUE : FALSE;
}
/**
* @brief 將元素 pt 壓入棧 pStack
*
* @param pStack 指向待壓入元素的棧的指針
* @param pt 指向待壓入元素的指針
*
* @return 返回成功壓入后棧的高度
*/
int Push( ArrStack *pStack, ElemType *pt )
{
///檢測(cè)是否需要擴(kuò)容
if( pStack->height == pStack->size )
{ //需要擴(kuò)容
//重新申請(qǐng)于原棧大小2倍大小的?？臻g
ElemType *pe = (ElemType *)calloc( pStack->size * 2, sizeof(ElemType) );
//將舊棧內(nèi)容拷貝到新棧內(nèi)容
memcpy( pe, pStack->btm, pStack->size * sizeof(ElemType) );
//重置?？?cè)萘看笮?BR> pStack->size = pStack->size * 2;
//釋放舊?？臻g
free( pStack->btm );
//將棧底指向新開(kāi)辟的?？臻g
pStack->btm = pe;
//棧頂指向新棧最后一個(gè)元素
pStack->top = &pe[pStack->height-1];
}
//將新元素壓入棧
pStack->btm[pStack->height].x = pt->x;
pStack->btm[pStack->height].y = pt->y;
//棧高度自增一
++pStack->height;
//棧頂指向最新棧元素
pStack->top = &pStack->btm[pStack->height-1];
return pStack->height;
}
/**
* @brief 將棧頂元素出棧 到 pt
*
* @param pStack 指向待彈出元素的棧的指針
* @param pt 指向接收彈出的元素的指針
*
* @return 出棧成功則返回出棧后棧的高度, 否則返回 -1
*/
int Pop( ArrStack *pStack, ElemType *pt )
{
///是否為空棧
if( pStack->height == 0 )
return -1;
//將棧頂元素賦值到 pt
pt->x = pStack->top->x;
pt->y = pStack->top->y;
//棧高度減一
--pStack->height;
//棧頂指向棧頂元素的上一個(gè)元素
pStack->top = &pStack->btm[pStack->height-1];
return pStack->height;
}
/**
* @brief 獲取棧頂元素到 pt
*
* @param pStack 指向待彈出元素的棧的指針
* @param pt 指向接收彈出的元素的指針
*
* @return 獲取成功則返回棧頂元素的位置, 否則返回 -1
*
* @note 元素位置由 0 計(jì)起
*/
int GetTop( ArrStack *pStack, ElemType *pt )
{
pt->x = pStack->top->x;
pt->y = pStack->top->y;
return pStack->height;
}
/**
* @brief 從棧底到棧頂?shù)拿總€(gè)元素依次執(zhí)行 func 函數(shù)
*
* @param pStack 指向待處理的棧的指針
* @param func 需要執(zhí)行的函數(shù)的指針
*
* @return void
*/
void ForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) )
{
int i = 0;
for( i = 0; i < pStack->height; ++i )
{
func( &pStack->btm[i] );
}
}
/**
* @brief 從棧頂?shù)綏５椎拿總€(gè)元素依次執(zhí)行 func 函數(shù)
*
* @param pStack 指向待處理的棧的指針
* @param func 需要執(zhí)行的函數(shù)的指針
*
* @return void
*/
void ReForEachStack( ArrStack *pStack, void (*func)(ElemType *pt) )
{
int i = pStack->height - 1;
for( i; i >= 0; --i )
{
func( &pStack->btm[i] );
}
}
//測(cè)試
void display( ElemType *pt )
{
printf( "(%d,%d) ", pt->x, pt->y );
}
int main()
{
///測(cè)試創(chuàng)建初始大小為 5 的棧
ArrStack *psk = CreateStack( 5 );
///測(cè)試 IsEmpty、GetSize、GetHeight
if( IsEmpty(psk) == TRUE )
printf( "Stack Size=%d, Stack Height=%d\n", GetSize(psk), GetHeight(psk) );
ElemType pt;
int i = 0;
///測(cè)試Push, 向棧內(nèi)壓入8個(gè)元素
printf( "\n向棧內(nèi)壓入8個(gè)元素后:\n" );
for( i = 0; i < 8; ++i )
{
pt.x = pt.y = i;
Push( psk, &pt );
}
//輸出壓入8個(gè)元素后的棧狀態(tài)
printf( "Is empty = %d\n", IsEmpty(psk) );
printf( "Stack size = %d\n", GetSize(psk) );
printf( "Stack height = %d\n", GetHeight(psk) );
///測(cè)試 ForEachStack、ReForEachStack
printf( "\n測(cè)試 ForEachStack、ReForEachStack:\n" );
ForEachStack( psk, display );
putchar('\n');
ReForEachStack( psk, display );
putchar('\n');
///測(cè)試getTop
GetTop( psk, &pt );
printf( "\n棧頂元素為: (%d,%d)\n", pt.x, pt.y );
///測(cè)試 Pop
Pop( psk, &pt );
printf( "\nPop彈出的元素為(%d,%d), 彈出后棧高:%d\n", pt.x, pt.y, GetHeight(psk) );
Pop( psk, &pt );
printf( "\nPop彈出的元素為(%d,%d), 彈出后棧高:%d\n", pt.x, pt.y, GetHeight(psk) );
///測(cè)試Push
pt.x = pt.y = 100;
Push( psk, &pt );
printf( "\nPop壓入的元素為(%d,%d), 壓入后棧高:%d\n", pt.x, pt.y, GetHeight(psk) );
///執(zhí)行全面出棧操作
printf( "\n執(zhí)行全面出棧:\n" );
int n = GetHeight(psk);
for( i = 0; i < n; ++i )
{
Pop( psk, &pt );
printf( "Pop彈出的元素為(%d,%d), 彈出后棧高:%d\n", pt.x, pt.y, GetHeight(psk) );
}
///銷(xiāo)毀棧
DestroyStack( psk );
return 0;
}
測(cè)試結(jié)果:
相關(guān)文章
樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因 為它看起來(lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。本文將帶你深入探究C語(yǔ)言中的二叉樹(shù)，感興趣的同學(xué)跟著小編一起學(xué)習(xí)吧2023-05-05
函數(shù)指針與指針函數(shù)的學(xué)習(xí)總結(jié)
函數(shù)指針是指向函數(shù)的指針，指針函數(shù)是指一個(gè)函數(shù)的返回值是一個(gè)指針。以下就是對(duì)函數(shù)指針與指針函數(shù)的應(yīng)用進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以參考下2013-07-07
這篇文章主要介紹了C語(yǔ)言中的直接插入排序(帶圖詳細(xì))，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-12-12
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)哈希表詳解
哈希表是一種根據(jù)關(guān)鍵碼去尋找值的數(shù)據(jù)映射結(jié)構(gòu)，該結(jié)構(gòu)通過(guò)把關(guān)鍵碼映射的位置去尋找存放值的地方，說(shuō)起來(lái)可能感覺(jué)有點(diǎn)復(fù)雜，我想我舉個(gè)例子你就會(huì)明白了，最典型的的例子就是字典2022-02-02
這篇文章主要為大家詳細(xì)介紹了C++中關(guān)于特殊類(lèi)設(shè)計(jì)的相關(guān)知識(shí)，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C++有一定的幫助，感興趣的可以了解一下2023-07-07
如何判斷一個(gè)整數(shù)的二進(jìn)制中有多少個(gè)1
本篇文章是對(duì)如何判斷一個(gè)整數(shù)的二進(jìn)制中有多少個(gè)1的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C++實(shí)現(xiàn)LeetCode(309.買(mǎi)股票的最佳時(shí)間含冷凍期)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(309.買(mǎi)股票的最佳時(shí)間含冷凍期),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
C++分步實(shí)現(xiàn)職工管理系統(tǒng)詳解
這篇文章主要為大家詳細(xì)介紹了基于C++實(shí)現(xiàn)職工管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-10-10
常用Hash算法(C語(yǔ)言的簡(jiǎn)單實(shí)現(xiàn))
下面小編就為大家?guī)?lái)一篇常用Hash算法(C語(yǔ)言的簡(jiǎn)單實(shí)現(xiàn))。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-09-09
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易停車(chē)場(chǎng)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)易停車(chē)場(chǎng)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03