前言
一、棧
1、棧的基本概念
棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂
2、棧的實(shí)現(xiàn)（數(shù)組實(shí)現(xiàn)）
棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)比較小
3、棧的基本操作
壓棧：棧的插入操作，也叫進(jìn)棧/入棧/壓棧，在棧頂進(jìn)行數(shù)據(jù)操作。
出棧：棧的刪除操作，也是在棧頂進(jìn)行數(shù)據(jù)刪除的。
3.1 棧的結(jié)構(gòu)設(shè)計(jì)
typedef int STDataType;//方便修改類型
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
3.2 棧常見的基本函數(shù)接口
//初始化
void STInit(ST* pst);
//銷毀棧
void STDestroy(ST* pst);
//入棧
void STPush(ST* pst, STDataType x);
//出棧
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//長度
int STSize(ST* pst);
//棧頂
STDataType STTop(ST* pst);
4、棧的實(shí)現(xiàn)
4.1 初始化棧
//初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;//指向棧頂下一個(gè)元素,若等于-1則指向棧頂元素，兩種任選
pst->capacity = 0;
}
4.2 棧的銷毀
//銷毀棧
void STDestroy(ST* pst)
{
assert(pst);
tree(pst->a);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
4.3 入棧
代碼：
void STPush(ST* pst, STDataType x)
{
assert(pst);
//判斷棧是否已滿，滿了就擴(kuò)容
if (pst->top == pst->capacity)
{
//使用三目運(yùn)算符進(jìn)行第一次開辟空間和后續(xù)擴(kuò)容空間
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
//判斷realloc是否開辟成功
if (tmp == NULL)
{
perror("realloc fail");
return;
}
//賦新值
pst->a = tmp;
pst->capacity = newcapacity;
}
//插入
pst->a[pst->top] = x;
pst->top++;
}
4.4 出棧
代碼：
//出棧
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
4.5 判空
//判空
bool STEmpty(ST* pst)
{
assert(pst);
//返回值為0為假，非零為真
return pst->top == 0;
}
4.6 長度
//長度
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
4.7 獲取棧頂元素
注意：若棧頂指針初始化為pst->top = 0，即棧頂指針指向棧頂元素的下一個(gè)位置，則入棧操作變?yōu)閜st->a[pst->top++]，出棧操作為pst->a[- -pst->top]。因?yàn)闂ｍ斨羔樔舫跏蓟癁?0 時(shí)，則棧頂指針始終指向順序棧將要入棧的位置，也就是棧頂指針的下標(biāo)就是入棧元素的下標(biāo)。
//棧頂
STDataType STTop(ST* pst)
{
assert(pst);
return pst->a[pst->top - 1];
}
完整代碼
Stack.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;
int capacity;
}ST;
//初始化
void STInit(ST* pst);
//銷毀棧
void STDestroy(ST* pst);
//入棧
void STPush(ST* pst, STDataType x);
//出棧
void STPop(ST* pst);
//判空
bool STEmpty(ST* pst);
//長度
int STSize(ST* pst);
//棧頂
STDataType STTop(ST* pst);
Stack.c
#include"Stack.h"
//初始化
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;
pst->top = 0;//指向棧頂下一個(gè)元素
pst->capacity = 0;
}
//銷毀棧
void STDestroy(ST* pst)
{
assert(pst);
tree(pst->a);
pst->a = NULL;
pst->top = 0;
pst->capacity = 0;
}
//入棧
void STPush(ST* pst, STDataType x)
{
assert(pst);
if (pst->top == pst->capacity)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->capacity = newcapacity;
pst->a = tmp;
}
pst->a[pst->top] = x;
pst->top++;
}
//出棧
void STPop(ST* pst)
{
assert(pst);
assert(pst->top > 0);
pst->top--;
}
//判空
bool STEmpty(ST* pst)
{
assert(pst);
return pst->top == 0;
}
//長度
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
//棧頂
STDataType STTop(ST* pst)
{
assert(pst);
return pst->a[pst->top - 1];
}
Test.c
#include"Stack.h"
int main()
{
ST st;
//初始化
STInit(&st);
//插入+刪除
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
STPush(&st, 5);
STPop(&st);
STPop(&st);
//長度
STSize(&st);
//棧頂
STTop(&st);
//銷毀
STDestroy(&st);
return 0;
}
二、隊(duì)列
1、隊(duì)列的結(jié)構(gòu)及概念
隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表，隊(duì)列具有先進(jìn)先出FIFO(First In First Out) 入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾 出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭
2、隊(duì)列的實(shí)現(xiàn)（單鏈表實(shí)現(xiàn)）
隊(duì)列也可以數(shù)組和鏈表的結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會(huì)比較低。
下面話不多說，直接開始代碼實(shí)現(xiàn)
1、隊(duì)列的鏈?zhǔn)浇Y(jié)構(gòu)設(shè)計(jì)
//鏈?zhǔn)浇Y(jié)構(gòu) 表示隊(duì)列
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
//隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
2、常用的功能接口
//初始化
void QueueInit(Queue* pq);
//銷毀隊(duì)列
void QueueDeatroy(Queue* pq);
//隊(duì)尾入列
void QueuePush(Queue* pq, QDataType x);
//隊(duì)頭出列
void QueuePop(Queue* pq);
//獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq);
//獲取隊(duì)列尾部元素
QDataType QueueBack(Queue* pq);
//檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* pq);
//獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq);
2.1、初始化隊(duì)列
只需要將頭尾指針都指向空即可，元素個(gè)數(shù)為零
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
2.2、銷毀隊(duì)列
遍歷鏈表，從頭到尾依次刪除結(jié)點(diǎn)，最后將頭尾指針指向空，元素個(gè)數(shù)為0。
//銷毀隊(duì)列
void QueueDeatroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
2.3、入隊(duì)列
創(chuàng)建新節(jié)點(diǎn)，若隊(duì)列為空，則將頭指針和尾指針都指向新創(chuàng)建的節(jié)點(diǎn)，若不為空，則尾插，因?yàn)槭擎準(zhǔn)酱鎯?chǔ)，所以和單鏈表的尾插一樣，將尾指針的next指向該節(jié)點(diǎn)，再把該節(jié)點(diǎn)設(shè)為新的尾節(jié)點(diǎn)
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->val = x;
newnode->next = NULL;
if (pq->ptail == NULL)
{
pq->ptail = pq->phead = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
2.4、出隊(duì)列
注意：出列要考慮隊(duì)列是空還是只有一個(gè)結(jié)點(diǎn)又或者有多個(gè)結(jié)點(diǎn)，為空則在代碼第一步就報(bào)錯(cuò)，若只有一個(gè)結(jié)點(diǎn)，則直接刪除該結(jié)點(diǎn)，并將頭尾倆指針指向空，若不止一個(gè)結(jié)點(diǎn)，可以創(chuàng)建一個(gè)臨時(shí)指針來記錄當(dāng)前頭指針，然后尾指針往后遍歷，再free掉創(chuàng)建的臨時(shí)指針，并置空
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->phead);
QNode* del = pq->phead;
pq->phead = pq->phead->next;
free(del);
del = NULL;
if (pq->phead == NULL)
pq->ptail = NULL;
pq->size--;
}
2.5、獲取隊(duì)列頭部元素
斷言，然后直接返回隊(duì)頭指針指向的節(jié)點(diǎn)元素
//獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
2.6、獲取隊(duì)列尾部元素
也是一樣的，直接返回隊(duì)尾指針指向的節(jié)點(diǎn)元素
//獲取隊(duì)列尾部元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->ptail->val;
}
2.7、判空
檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0文章來源：http://www.zghlxwxcb.cn/news/detail-758215.html
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
2.8、獲取有效元素個(gè)數(shù)
//獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
完整代碼
Queue.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//鏈?zhǔn)浇Y(jié)構(gòu) 表示隊(duì)列
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
//隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//銷毀隊(duì)列
void QueueDeatroy(Queue* pq);
//隊(duì)尾入列
void QueuePush(Queue* pq, QDataType x);
//隊(duì)頭出列
void QueuePop(Queue* pq);
//獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq);
//獲取隊(duì)列尾部元素
QDataType QueueBack(Queue* pq);
//檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* pq);
//獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq);
Queue.c
#include"Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//銷毀隊(duì)列
void QueueDeatroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}
//隊(duì)尾入列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->next = NULL;
newnode->val = x;
if (pq->ptail == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
//現(xiàn)在newnode是新的尾結(jié)點(diǎn)
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
//隊(duì)頭出列
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->phead);
//保存當(dāng)前節(jié)點(diǎn)
QNode* tmp = pq->phead;
//phead往下走
pq->phead = pq->phead->next;
free(tmp);
tmp = NULL;
if (pq->phead = NULL)
{
pq->ptail = NULL;
}
pq->size--;
}
//獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
//獲取隊(duì)列尾部元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->ptail;
}
//檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
//獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
Test.c
#include"Queue.h"
int main()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
QueueDeatroy(&q);
return 0;
}
文章來源地址http://www.zghlxwxcb.cn/news/detail-758215.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列超詳解！(Stack && Queue)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
