C語(yǔ)言 淺談棧與隊(duì)列的定義與操作
棧的定義
棧同樣是一種線性表，它的特性是插入元素必須從后面插入，刪除元素也是從后面刪除，進(jìn)行數(shù)據(jù)刪除和插入的一端稱為棧頂，另一端是棧底。
壓棧—就是插入元素
出?！褪莿h除元素
它可以用數(shù)組實(shí)現(xiàn)也可以用鏈表實(shí)現(xiàn)
但是用數(shù)組實(shí)現(xiàn)更好，因?yàn)殒湵淼牟迦牒蛣h除要進(jìn)行遍歷，而數(shù)組可以進(jìn)行隨機(jī)訪問(wèn)，從而時(shí)間復(fù)雜度更低。
棧的實(shí)現(xiàn)
前置
棧的元素需要表明容量，還有棧頂
typedef int SDType;
typedef struct Srack
{
SDType* a;
int top;
int capacity;
}ST;
初始化棧
把元素置為空，棧頂在下標(biāo)為0的位置
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
棧的銷毀
不再贅述
void StackDestrory(ST* ps)
{
assert(ps);
free(ps);
ps=NULL;
ps->capacity = ps->top = 0;
}
棧的插入
先判空，如果容量滿了，進(jìn)行增容，把棧頂元素進(jìn)行賦值，再把棧頂指針加一
void StackPush(ST* ps, SDType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SDType* tmp = (SDType)realloc(ps->capacity, sizeof(SDType) * newCapacity);
if (tmp == NULL)
{
printf("Realloc fail!\n");
}
else
{
ps->a = tmp;
ps->capacity = newCapacity;
}
}
ps->a[ps->top] = x;
ps->top++;
}
出棧的操作
棧頂指針減一即可
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
取棧頂元素
先進(jìn)行判空，不空的話直接取出棧頂指針指向的元素
SDType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps -> a[ps->top - 1];
}
棧的大小
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
判斷棧是否為空
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
隊(duì)列的定義
隊(duì)列只允許在一段進(jìn)行插入操作，一段進(jìn)行刪除操作，在隊(duì)尾進(jìn)行插入，在隊(duì)頭進(jìn)行刪除
隊(duì)列的基本操作
隊(duì)列的初始化
我們?cè)谶M(jìn)行基本操作的時(shí)候要用到頭指針和尾指針
void QueueInit(Queue* pq)
{
assert(pq != NULL);
pq->head = NULL;
pq->tail = NULL;
}
隊(duì)列的銷毀
將臨時(shí)指針cur被賦值為head，保存下一個(gè)，遍歷進(jìn)行刪除，最后把頭指針和尾指針進(jìn)行free
void QueueDestroy(Queue* pq)
{
assert(pq != NULL);
QueueNode* cur = pq->head;
QueueNode* next = cur->next;
while (cur)
{
free(cur);
cur = next;
next = next->next;
}
pq->head = pq->tail = NULL;
}
隊(duì)列的插入
隊(duì)列只能從隊(duì)尾查，如果開始的時(shí)候隊(duì)頭和隊(duì)尾重合，那就直接進(jìn)行插入，
如果不，那就找到尾，在尾后邊進(jìn)行插入
void QueuePush(Queue* pq,QDataType x)
{
assert(pq);
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->data = x;
newNode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
}
隊(duì)列的刪除
很簡(jiǎn)單，刪除隊(duì)尾頭元素，先保存下一個(gè)，再把隊(duì)頭復(fù)制給新的
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* NewHead = pq->head->next;
free(pq->head);
pq->head = NewHead;
if (pq->head == NULL)
{
pq->tail = NULL;
}
}
隊(duì)列的判空
是否隊(duì)頭指向空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
取出隊(duì)頭元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
取出隊(duì)尾元素
先判空
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
隊(duì)列的大小
直接遍歷就行
int QueueSize(Queue* pq)
{
assert(pq);
int n = 0;
QueueNode* cur = pq->head;
while (cur)
{
cur = cur->next;
n++;
}
return n;
}
點(diǎn)個(gè)贊把
到此這篇關(guān)于C語(yǔ)言 淺談棧與隊(duì)列的定義與操作的文章就介紹到這了,更多相關(guān)C語(yǔ)言 棧與隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- C語(yǔ)言示例代碼講解棧與隊(duì)列
- C語(yǔ)言分別實(shí)現(xiàn)棧和隊(duì)列詳解流程
- C語(yǔ)言棧與隊(duì)列相互實(shí)現(xiàn)詳解
- C語(yǔ)言棧與隊(duì)列面試題詳解
- C語(yǔ)言用棧模擬實(shí)現(xiàn)隊(duì)列問(wèn)題詳解
- C語(yǔ)言循環(huán)隊(duì)列與用隊(duì)列實(shí)現(xiàn)棧問(wèn)題解析
- C語(yǔ)言超詳細(xì)講解棧與隊(duì)列實(shí)現(xiàn)實(shí)例
- C語(yǔ)言中用棧+隊(duì)列實(shí)現(xiàn)隊(duì)列中的元素逆置
- C語(yǔ)言近萬(wàn)字為你講透棧和隊(duì)列
相關(guān)文章
win10環(huán)境下vscode Linux C++開發(fā)代碼自動(dòng)提示配置(基于WSL)
這篇文章主要介紹了win10環(huán)境下vscode Linux C++開發(fā)代碼自動(dòng)提示配置(基于WSL),文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05
C++ 賦值構(gòu)造函數(shù)注意點(diǎn)介紹
下面小編就為大家?guī)?lái)一篇C++ 賦值構(gòu)造函數(shù)注意點(diǎn)介紹。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12
C語(yǔ)言實(shí)現(xiàn)快速排序算法實(shí)例
快速排序時(shí)間復(fù)雜度為O(nlogn)，是數(shù)組相關(guān)的題目當(dāng)中經(jīng)常會(huì)用到的算法,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言實(shí)現(xiàn)快速排序算法的相關(guān)資料,需要的朋友可以參考下2022-06-06
C語(yǔ)言實(shí)現(xiàn)校園導(dǎo)游系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)校園導(dǎo)游系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C++使用easyX庫(kù)實(shí)現(xiàn)三星環(huán)繞效果流程詳解
EasyX是針對(duì)C/C++的圖形庫(kù)，可以幫助使用C/C++語(yǔ)言的程序員快速上手圖形和游戲編程。這篇文章主要介紹了C++使用easyX庫(kù)實(shí)現(xiàn)三星環(huán)繞效果，需要的可以參考一下2022-10-10
C語(yǔ)言Easyx實(shí)現(xiàn)貪吃蛇詳解
這篇文章主要為大家詳細(xì)介紹了基于easyx的C++實(shí)現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
類是創(chuàng)建對(duì)象的模板，一個(gè)類可以創(chuàng)建多個(gè)對(duì)象，每個(gè)對(duì)象都是類類型的一個(gè)變量；創(chuàng)建對(duì)象的過(guò)程也叫類的實(shí)例化。每個(gè)對(duì)象都是類的一個(gè)具體實(shí)例（Instance），擁有類的成員變量和成員函數(shù)2021-10-10
這篇文章主要為大家介紹了C語(yǔ)言共用體union作用的使用示例教程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-02-02
C++編程中new運(yùn)算符的使用學(xué)習(xí)教程
這篇文章主要介紹了C++編程中new運(yùn)算符的使用學(xué)習(xí)教程,是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下2016-01-01
做OTA升級(jí)功能時(shí)，我們能直接拿到的往往只是升級(jí)包的鏈接，需要我們自己去下載，這時(shí)候就需要用到http下載器。本文將利用C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的http下載器，感興趣的可以了解一下2022-12-12