隨感而發

雜七雜八

隨筆分類(62)

隨筆檔案(67)

統計

隨筆 - 67
文章 - 0
評論 - 132
引用 - 0

留言簿(13)

閱讀排行榜

評論排行榜

棧學習---數組實現

今天學習了棧，據說棧是一個很重要的數據結構。其主要的思想為：
1. 棧是一個后進先出的數據結構(last-in, first-out LIFO)。
2. 他的主要操作有“IsEmpty() 判斷棧空。Push()插入數據。Pop彈出數據。
3. 他的核心數據為棧頂，棧數據區域。棧頂表示最后一個數據的位置，也表示了棧中數據的個數。我這里是有一個int來表示。棧空的時候，棧頂位置為0。要得到棧頂元素，只需要用nData[nTop]就可以了。nData是他的數據區域。
4. 實現的一些細節，我棧頂的初始值為0，他代表什么數據也沒有，壓入數據的時候，先把棧頂加1，然后使nData[nTop] = 數據。這樣在出棧和得到棧頂元素都很方便。也很方便的得到棧的數據個數。下標為0的空間沒有用，浪費了這個空間得到了操作的方便。還有就是注意判斷棧是否滿了，如果滿了還添加的話，棧溢出。也要判斷棧如果已經為空了，就不能在彈出(pop)數據了。
也就這么多了，奉上源代碼：我這個是用數組寫的：

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

//定義一個棧的結構體

struct MyStack

{

int nTop; //棧頂位置

int nData[11]; //棧的數據區域

};

MyStack g_stack;

//判斷棧是否為空,空返回true

bool IsEmpty()

{

return !g_stack.nTop;

}

//設置棧為空

int SetEmpty()

{

g_stack.nTop = 0;

return 0;

}

//壓數據入棧

int Push(int nData)

{

assert(g_stack.nTop < 10);

++g_stack.nTop;

g_stack.nData[g_stack.nTop] = nData;

return g_stack.nTop;

}

//得到棧頂的引用

int& GetTop()

{

assert(g_stack.nTop);

return g_stack.nData[g_stack.nTop];

}

//彈出棧頂元素，返回彈出的元素。

int Pop(void)

{

assert(g_stack.nTop);

--g_stack.nTop;

return g_stack.nData[g_stack.nTop + 1];

}

int main()

{

SetEmpty();

//測試棧

if (IsEmpty())

{

printf("MyStack Is Empty!\n");

}

for (int i = 0; i < 10; ++i)

{

Push(i);

printf("%d ", GetTop());

}

printf("\n");

while (!IsEmpty())

{

printf("%d ", Pop());

}