柚子快報邀請碼778899分享：學(xué)習(xí) c語言 數(shù)據(jù)結(jié)構(gòu)之《棧》
柚子快報邀請碼778899分享：學(xué)習(xí) c語言 數(shù)據(jù)結(jié)構(gòu)之《?！?/p>
在之前我們已經(jīng)學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)中線性表里面的順序表與鏈表，了解了如何實現(xiàn)順序表與鏈表增、刪、查、該等功能。其實在線性表中除了順序表和鏈表還有其他的類別，在本篇中我們就將學(xué)習(xí)另外一種線性表——棧，在通過本篇的學(xué)習(xí)后，你將會對棧的結(jié)構(gòu)有充足的了解，在了解完結(jié)構(gòu)后我們還將進行棧的實現(xiàn)。一起加油吧?。?！
1.棧的概念與結(jié)構(gòu)
棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據(jù)插入和刪除操作的?端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進先出（先進后出）LIFO（Last In First Out的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。 出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
那么棧的底層結(jié)構(gòu)是基于什么的呢？其實基于數(shù)組還是基于單鏈表或者是雙鏈表都是可以的，那么哪一種是最優(yōu)解呢？接下來我們就來分析基于不同底層結(jié)構(gòu)的利與弊
若底層結(jié)構(gòu)基于數(shù)組，則可以讓數(shù)組的低地址處表示棧底，數(shù)組的高地址處表示棧頂，使用一個size變量來表示數(shù)組有效數(shù)據(jù)個數(shù)，這樣就可以要入棧時直接在size位置插入數(shù)據(jù)，之后size加一；出棧時就可以直接讓size減一，這樣就可以讓數(shù)組的有效個數(shù)減一。以上使用數(shù)組來作為棧的底層結(jié)構(gòu)時間復(fù)雜度為O(1)
在數(shù)組當(dāng)中雖然每次在空間不足時都會以之前二倍的方式申請新空間，這時可能會存在內(nèi)存的浪費，當(dāng)時由于數(shù)組在內(nèi)存中是連續(xù)存放的，這就使得在入棧和出棧不需要再每次都申請空間，而且數(shù)組在取數(shù)據(jù)的時候可能緩存中就有不一定要在主存中取。
若棧的底層結(jié)構(gòu)為單鏈表，如果是在單鏈表尾部表示棧頂，頭部表示棧底這樣在無論是在入棧還是在出棧時因為都需要通過遍歷來找到單鏈表的尾節(jié)點，所以時間復(fù)雜度都為O(N)。所以這時就要改變棧頂為單鏈表的頭部，棧底為單鏈表的尾部，這時在入棧和出棧時就不需要遍歷單鏈表，時間復(fù)雜度就都為O(1)。
但是單鏈表每次在入棧和出棧時都要申請節(jié)點和銷毀節(jié)點，并且由于單鏈表每個節(jié)點空間在內(nèi)存當(dāng)中不一定是連續(xù)的，所以每次訪問數(shù)據(jù)都需要區(qū)主存取。
而在雙鏈表中無論是讓頭部作為棧頂，尾部作為棧底還是讓尾部作為棧頂，頭部作為棧底，由于雙鏈表每個節(jié)點內(nèi)部都有指向前一個節(jié)點和下一個節(jié)點的指針，所以在入棧和出棧時都不需要遍歷鏈表，所以入棧和出棧時的時間復(fù)雜度都為O(1)。
但是雙鏈表在每個節(jié)點內(nèi)部相比單鏈表都多一個指針變量，在32位環(huán)境下每個節(jié)點大小就會多4個字節(jié)；在64位環(huán)境下每個節(jié)點大小就會多8字節(jié)。因此使用雙鏈表就會造成更多的內(nèi)存損耗。
通過以上的分析可以發(fā)現(xiàn)無論棧的底層結(jié)構(gòu)是基于數(shù)組還是單鏈表還是雙鏈表在入棧和出棧時的時間復(fù)雜度都為O(1)，但是綜合其他因素使用數(shù)組是最優(yōu)解?
?
2.棧的實現(xiàn)
在實現(xiàn)棧的代碼內(nèi)在Stack.h頭文件內(nèi)定義棧的結(jié)構(gòu)以及對各種功能函數(shù)進行聲明，在Stack.c文件內(nèi)實現(xiàn)各個函數(shù)，在test.c文件內(nèi)對實現(xiàn)的各函數(shù)進行測試
2.1棧結(jié)構(gòu)的定義
在Stack.h中創(chuàng)建一個結(jié)構(gòu)體來定義棧的結(jié)構(gòu)，在該結(jié)構(gòu)體中的成員變量和順序表中基本是相同的，只不過將順序表中表示有效元素個數(shù)的size改名位top，讓top來表示棧頂
//定義棧的結(jié)構(gòu)
typedef int STDataType;
typedef struct stack
{
STDataType* a;
int capacity;//?？臻g大小
int top;//棧頂
}stack;
2.2棧的初始化
要完成棧的初始化函數(shù)首先要在Stack.h完成初始化函數(shù)的聲明
//初始化棧
void stackInit(stack* ps);
將該函數(shù)命名為stackInit,函數(shù)的參數(shù)就為指向結(jié)構(gòu)體的指針
接下來就是在stack.c內(nèi)完成初始化函數(shù)的實現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對ps進行assert斷言
//初始化棧
void stackInit(stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
2.3檢測棧是否為空
要完成檢測棧是否為空函數(shù)首先要在Stack.h完成該函數(shù)函數(shù)的聲明
//檢測棧是否為空
bool stackEmpty(stack* ps);
將該函數(shù)命名為stackEmpty,函數(shù)的參數(shù)就為指向結(jié)構(gòu)體的指針，函數(shù)的返回類型為布爾類型
接下來就是在stack.c內(nèi)完成檢測棧是否為空函數(shù)的實現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對ps進行assert斷言 在該函數(shù)中若數(shù)組內(nèi)的有效個數(shù)top為0函數(shù)就會返回true，不為0就返回false
//檢測棧是否為空
bool stackEmpty(stack* ps)
{
assert(ps);
return ps->top==0;
}
2.4入棧
要完成入棧函數(shù)首先要在Stack.h完成初始化函數(shù)的聲明
void stackPush(stack* ps,STDataType x);
將該函數(shù)命名為stackPush,函數(shù)的參數(shù)有兩個，第一個為指向結(jié)構(gòu)體的指針，第二個為要進入棧的數(shù)據(jù)
接下來就是在stack.c內(nèi)完成入棧函數(shù)的實現(xiàn) 由于在入棧時數(shù)組的空間可以已經(jīng)滿了，因此在進行插入數(shù)據(jù)之前要判斷數(shù)組的有效個數(shù)是否與數(shù)組的空間大小相同，如果相同就需要進行增容。增容的代碼就和之前的順序表檢測數(shù)組空間大小函數(shù)一樣。 在調(diào)整完空間大小之后的入棧就和順序表中得尾插一樣，ps->a[ps->top++] = x一句代碼就可以實現(xiàn)
//入棧
void stackPush(stack* ps,STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->a=tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
2.5出棧?
要完成出棧函數(shù)首先要在Stack.h完成出棧函數(shù)的聲明
//出棧
void stackPop(stack* ps);
將該函數(shù)命名為stackPop,函數(shù)的參數(shù)為指向結(jié)構(gòu)體的指針
接下來就是在stack.c內(nèi)完成出棧函數(shù)的實現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對ps進行assert斷言 同時在出棧時棧不能為空，所以要對satckEmpt(ps)進行assert斷言在出棧就和順序表中得尾刪一樣將top減一就可
//出棧
void stackPop(stack* ps)
{
assert(ps);
assert(!stackEmpty(ps));
--ps->top;
}
2.6取棧頂元素
要完成取棧頂元素函數(shù)首先要在Stack.h完成取棧頂元素函數(shù)的聲明
//獲取棧頂元素
STDataType stackTop(stack* ps);
將該函數(shù)命名為stackTop,函數(shù)的參數(shù)為指向結(jié)構(gòu)體的指針，函數(shù)的返回值就為棧頂?shù)脑?/p>
接下來就是在stack.c內(nèi)完成取棧頂原始函數(shù)的實現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對ps進行assert斷言 同時在出棧時棧不能為空，所以要對satckEmpt(ps)進行assert斷言 由于top指向數(shù)組的尾元素的后一位，所以只要將size-1就可以得到棧頂元素
//獲取棧頂元素
STDataType stackTop(stack* ps)
{
assert(ps);
assert(!stackEmpty(ps));
return ps->a[ps->top - 1];
}
2.7獲取棧中有效元素個數(shù)
要完成獲取棧中有效元素個數(shù)函數(shù)首先要在Stack.h完成獲取棧中有效元素個數(shù)函數(shù)的聲明
//獲取棧中有效元素個數(shù)
int stackSize(stack* ps);
將該函數(shù)命名為stackSize,函數(shù)的參數(shù)為指向結(jié)構(gòu)體的指針，函數(shù)的返回值就為棧的元素個數(shù)
接下來就是在stack.c內(nèi)完成獲取棧中有效元素個數(shù)函數(shù)的實現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對ps進行assert斷言 因為在結(jié)構(gòu)體中的top就為數(shù)組的有效元素個數(shù)，所以在該函數(shù)中返回ps->top即可
//獲取棧中有效元素個數(shù)
int stackSize(stack* ps)
{
assert(ps);
return ps->top;
}
2.8銷毀棧
要完成銷毀棧函數(shù)首先要在Stack.h完成銷毀棧函數(shù)的聲明
//銷毀棧
void stackDestory(stack* ps);
將該函數(shù)命名為stackDestory,函數(shù)的參數(shù)為指向結(jié)構(gòu)體的指針
接下來就是在stack.c內(nèi)完成銷毀棧函數(shù)的實現(xiàn) 由于ps指針是指向結(jié)構(gòu)體的指針，所以該指針不能為空，所以要對ps進行assert斷言 在銷毀時，由于棧的空間是由realloc申請來的，所以在使用完后要用free來釋放內(nèi)存空間，并且在釋放后將指針ps->a置為NULL，且將top和capacity都賦值為0
//銷毀棧
void stackDestory(stack* ps)
{
assert(ps);
if (ps->a)
{
free(ps->a);
}
ps->a = NULL;
ps->top = ps->capacity = 0;
}
2.9棧的打印
因為在棧和順序表以及鏈表不同，由于棧只能在一端進和出所以棧是不能遍歷，所以我們不能通過創(chuàng)建一個函數(shù)來遍歷棧
所以要打印棧就只能在test.c內(nèi)調(diào)用相關(guān)函數(shù)來實現(xiàn)例如以下棧先依次入棧1，2，3，4，之后要打印就通過以下循環(huán)來實現(xiàn)
#include"stack.h"
void test()
{
stack ps;
stackInit(&ps);
stackPush(&ps, 1);
stackPush(&ps, 2);
stackPush(&ps, 3);
stackPush(&ps, 4);
while (!stackEmpty(&ps))
{
STDataType p = stackTop(&ps);
printf("%d ", p);
stackPop(&ps);
}
stackDestory(&ps);
}
int main()
{
test();
return 0;
}
3.棧的實現(xiàn)完整代碼?
stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
//定義棧的結(jié)構(gòu)
typedef int STDataType;
typedef struct stack
{
STDataType* a;
int capacity;//?？臻g大小
int top;//棧頂
}stack;
//初始化棧
void stackInit(stack* ps);
//銷毀棧
void stackDestory(stack* ps);
//檢測棧是否為空
bool stackEmpty(stack* ps);
//入棧
void stackPush(stack* ps,STDataType x);
//出棧
void stackPop(stack* ps);
//獲取棧頂元素
STDataType stackTop(stack* ps);
//獲取棧中有效元素個數(shù)
int stackSize(stack* ps);
stack.c
#include"stack.h"
//初始化棧
void stackInit(stack* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//銷毀棧
void stackDestory(stack* ps)
{
assert(ps);
if (ps->a)
{
free(ps->a);
}
ps->a = NULL;
ps->top = ps->capacity = 0;
}
//檢測棧是否為空
bool stackEmpty(stack* ps)
{
assert(ps);
return ps->top==0;
}
//入棧
void stackPush(stack* ps,STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->a=tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
//出棧
void stackPop(stack* ps)
{
assert(ps);
assert(!stackEmpty(ps));
--ps->top;
}
//獲取棧頂元素
STDataType stackTop(stack* ps)
{
assert(ps);
assert(!stackEmpty(ps));
return ps->a[ps->top - 1];
}
//獲取棧中有效元素個數(shù)
int stackSize(stack* ps)
{
assert(ps);
return ps->top;
}
柚子快報邀請碼778899分享：學(xué)習(xí) c語言 數(shù)據(jù)結(jié)構(gòu)之《?！?/p>
精彩文章
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉(zhuǎn)載請注明，如有侵權(quán)，聯(lián)系刪除。
OnBuy樂買網(wǎng)隨便看看
換一換
最新留言
- 珠海職業(yè)培訓(xùn)指導(dǎo)服務(wù)官網(wǎng)為http://zhrsj.zhuhai.gov.cn/，成立于2012年，現(xiàn)更名為珠海市職業(yè)訓(xùn)練指導(dǎo)服務(wù)中心。
- 小紅書商家入駐后臺有哪些主要優(yōu)勢？
- 商品售價的制定是一個復(fù)雜的過程，需要考慮哪些因素？
- 9月份的電商節(jié)日包括教師節(jié)、中秋節(jié)和秋分等，各大電商平臺會推出相應(yīng)的促銷活動。
- 神經(jīng)網(wǎng)絡(luò)優(yōu)化中常見的問題包括梯度消失或爆炸、過擬合、計算資源消耗大等。
- Kodi 插件包為 Kodi 用戶提供了廣泛的功能和豐富的體驗，無論是想要觀看 Netflix 大片、收聽 Spotify 音樂，還是觀看直播電視節(jié)目，都可以通過安裝相應(yīng)的插件來實現(xiàn)，考慮到不同用戶的需求和場景，中文語言插件和其他中文插件倉庫也為中文用戶提供了便利。
- 分銷渠道的建立和管理對企業(yè)銷售策略的成功至關(guān)重要。
- 處理網(wǎng)上收款不封的收錢碼，需確認需求、了解規(guī)則、解決無法使用問題及注意賬戶安全。
- 彈幕數(shù)據(jù)分析在B站平臺上的應(yīng)用有助于豐富用戶的互動體驗，但也存在一些挑戰(zhàn)和問題，彈幕數(shù)據(jù)的采集和處理需要開發(fā)者具備一定的技術(shù)知識，而情感分析和內(nèi)容分析則需要專業(yè)的算法支持，用戶行為分析和可視化展示也需要大量的數(shù)據(jù)資源和技術(shù)支持，彈幕數(shù)據(jù)的采集和使用需要遵守相關(guān)的法律法規(guī)，確保不侵犯他人的合法權(quán)益。
- 外貿(mào)稅率計算中，如何確保所有交易都有有效的發(fā)票和合同支持？
