棧:一種特殊的線性表,只允許在固定的一端進(jìn)行插入和刪除元素操作。
創(chuàng)新互聯(lián)公司堅持“要么做到,要么別承諾”的工作理念,服務(wù)領(lǐng)域包括:網(wǎng)站制作、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù),滿足客戶于互聯(lián)網(wǎng)時代的莒縣網(wǎng)站設(shè)計、移動媒體設(shè)計的需求,幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴!進(jìn)行數(shù)據(jù)插入和刪除的一端稱為棧頂,另一端稱為棧底。
棧中的元素遵循后進(jìn)先出的原則。
壓棧:棧的插入操作叫做進(jìn)棧/壓棧/入棧,在棧頂進(jìn)行操作。
出棧:棧的刪除操作叫做出棧,出棧操作同樣在棧頂進(jìn)行。
棧的實現(xiàn)一般可以使用數(shù)組或者鏈表,相對而言數(shù)組的結(jié)構(gòu)更優(yōu)一些,因為數(shù)組代價比較小。
從上圖可以看出,相對于單向不帶頭非循環(huán)鏈表而言,數(shù)組在進(jìn)行尾插和尾刪的時候可以直接使用下標(biāo)進(jìn)行操作,所以我們在實現(xiàn)棧的時候使用的是動態(tài)開辟的數(shù)組。
// 支持動態(tài)增長的棧
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 棧頂
int capacity; // 容量
}Stack;
1.2.1初始化棧void StackInit(Stack* ps)
{
assert(ps);
ps->a == NULL;
ps->capacity = ps->top = 0;
}
1.2.2入棧void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
1.2.3判斷棧是否為空?// 檢測棧是否為空,如果為空返回非零結(jié)果,如果不為空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
1.2.4出棧void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
1.2.5獲取棧頂元素STDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
1.2.6獲取棧中數(shù)據(jù)的有效個數(shù)int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
1.2.7銷毀棧void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
2.隊列
2.1隊列的概念及結(jié)構(gòu)隊列:只允許在一端進(jìn)行插入數(shù)據(jù)操作,在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表。
隊列具有先進(jìn)先出的特點,進(jìn)行插入操作的一端稱為隊尾,進(jìn)行刪除操作的一端是隊頭。
隊列也可以使用數(shù)組和鏈表結(jié)構(gòu)實現(xiàn),使用鏈表的結(jié)構(gòu)更優(yōu),因為如果使用數(shù)組的結(jié)構(gòu),出隊列在數(shù)組頭上出數(shù)據(jù),效率降低。
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
//int size;
QNode* head;//指向隊列的頭節(jié)點
QNode* tail;//指向隊列的尾節(jié)點
}Queue;
2.2.1隊列的初始化和銷毀// 初始化隊列
void QueueInit(Queue* q)
{
assert(q);
q->head = NULL;
q->tail = NULL;
}
// 銷毀隊列
void QueueDestroy(Queue* q)
{
assert(q);
QNode* cur = q->head;
while (cur)
{
QNode* next = cur->next;//先保存next 否則釋放后無法訪問后面的空間
free(cur);
cur = next;
}
q->head = q->tail = NULL;
}
2.2.1隊尾入數(shù)據(jù)void QueuePush(Queue* q, QDataType x)
{
assert(q);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (q->head == NULL)//隊列中沒有數(shù)據(jù)
q->head = q->tail = newnode;
else//隊列中有數(shù)據(jù)
{
q->tail->next = newnode;
//更新q->tail
q->tail = newnode;
}
}
2.2.3隊頭出數(shù)據(jù)void QueuePop(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
if (q->head == q->tail)//隊列只有一個數(shù)據(jù)
{
free(q->head);
q->head = q->tail = NULL;
}
else//隊列中不止一個數(shù)據(jù)
{
QNode* next = q->head->next;
free(q->head);
q->head = next;
}
}
2.3.4獲取隊頭和隊尾的數(shù)據(jù)//獲取隊頭數(shù)據(jù)
QDataType QueueFront(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->head->data;
}
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(!QueueEmpty(q));
return q->tail->data;
}
2.3.5獲取隊列中元素個數(shù)int QueueSize(Queue* q)
{
assert(q);
QNode* cur = q->head;
int count = 0;
while (cur)
{
count++;
cur = cur->next;
}
return count;
}
2.3.6判斷隊列是否為空// 檢測隊列是否為空,如果為空返回非零結(jié)果,如果非空返回0
int QueueEmpty(Queue* q)
{
assert(q);
return q->head == NULL;//或者使用q->tail == NULL
}
棧和隊列的實現(xiàn)到這里就結(jié)束了,想要了解更多數(shù)據(jù)結(jié)構(gòu)和C++方向的內(nèi)容,那就點個關(guān)注吧,后面會繼續(xù)更新數(shù)據(jù)結(jié)構(gòu)和C++方向的內(nèi)容。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商?創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源,準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性,企業(yè)級服務(wù)器適合批量采購,新人活動首月15元起,快前往官網(wǎng)查看詳情吧
文章標(biāo)題:【數(shù)據(jù)結(jié)構(gòu)】棧和隊列的實現(xiàn)-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接:http://www.rwnh.cn/article4/cspgie.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站改版、響應(yīng)式網(wǎng)站、標(biāo)簽優(yōu)化、服務(wù)器托管、App設(shè)計、用戶體驗
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)
猜你還喜歡下面的內(nèi)容