柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】第五講：棧和隊(duì)列

http://yzkb.51969.com/

?個(gè)人主頁(yè)：深情秋刀魚(yú)@-CSDN博客

數(shù)據(jù)結(jié)構(gòu)專(zhuān)欄：數(shù)據(jù)結(jié)構(gòu)與算法

源碼獲取：數(shù)據(jù)結(jié)構(gòu): 上傳我寫(xiě)的關(guān)于數(shù)據(jù)結(jié)構(gòu)的代碼 (gitee.com)

目錄

一、棧

1.棧的定義

?2.棧的實(shí)現(xiàn)

?a.棧結(jié)構(gòu)的定義

b.初始化

c.擴(kuò)容

d.入棧

e.出棧

f.打印

g.取棧頂元素

?h.判空

i.獲取棧中的元素個(gè)數(shù)

j.銷(xiāo)毀

二、隊(duì)列?

1.隊(duì)列的定義

2.隊(duì)列的實(shí)現(xiàn)

a.隊(duì)列結(jié)構(gòu)的定義

b.初始化

c.創(chuàng)建節(jié)點(diǎn)

d.入隊(duì)

e.出隊(duì)

f.隊(duì)中的元素個(gè)數(shù)

g.隊(duì)列判空

h.隊(duì)列打印

i.取隊(duì)頭元素

?j.取隊(duì)尾元素

?k.銷(xiāo)毀

一、棧

1.棧的定義

? ? ? ? 棧是一種特殊的線(xiàn)性表，其只允許在固定的一段進(jìn)行插入和刪除元素的操作。進(jìn)行數(shù)據(jù)的插入和刪除元素的操作的一端被稱(chēng)為棧頂，另一端被稱(chēng)為棧底。棧中的數(shù)據(jù)元素遵循后進(jìn)先出LIFO（Last in First out）的原則。

?2.棧的實(shí)現(xiàn)

? ? ? ? 棧的實(shí)現(xiàn)一般可以用數(shù)組和鏈表實(shí)現(xiàn)，一般情況下用數(shù)組實(shí)現(xiàn)更為合適，因?yàn)樵跀?shù)組尾部進(jìn)行插入和刪除操作的代價(jià)較小。

?a.棧結(jié)構(gòu)的定義

typedef int STDataType;

//定義棧結(jié)構(gòu)（數(shù)組）

typedef struct Stack

{

STDataType* a; //數(shù)組棧

int top; //棧頂

int capacity; //容量

}Stack;

b.初始化

void STInit(Stack* pst)

{

assert(pst);

pst->a = NULL;

pst->capacity = 0;

pst->top = -1;

}

c.擴(kuò)容

void STExpan(Stack* pst)

{

if (pst->top + 1 == pst->capacity)

{

int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;

STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc fail!");

return;

}

pst->a = tmp;

pst->capacity = newcapacity;

}

}

? ? ? ? 在對(duì)棧中的數(shù)組進(jìn)行擴(kuò)容時(shí)，需要注意其他參數(shù)如容量（capacity）的變化，在一開(kāi)始我們將capacity初始化為0，所以在這里要對(duì)capacity進(jìn)行判空。

d.入棧

void STPush(Stack* pst, STDataType x)

{

assert(pst);

STExpan(pst);

pst->top++;

pst->a[pst->top] = x;

}

e.出棧

void STPop(Stack* pst)

{

assert(pst && pst->top > -1);

pst->top--;

}

f.打印

void STPrint(Stack* pst)

{

while (!STEmpty(pst))

{

printf("%d ", STTop(pst));

STPop(pst);

}

}

g.取棧頂元素

STDataType STTop(Stack* pst)

{

assert(pst && pst->top > -1);

return pst->a[pst->top];

}

?h.判空

bool STEmpty(Stack* pst)

{

assert(pst);

return pst->top == -1;

}

i.獲取棧中的元素個(gè)數(shù)

int STSize(Stack* pst)

{

assert(pst);

return pst->top + 1;

}

j.銷(xiāo)毀

void STDestroy(Stack* pst)

{

assert(pst);

free(pst->a);

pst->a = NULL;

pst->capacity = 0;

pst->top = 0;

}

二、隊(duì)列?

1.隊(duì)列的定義

? ? ? ? 隊(duì)列是只允許在一端進(jìn)行插入，另一端進(jìn)行刪除數(shù)據(jù)操作的線(xiàn)性表。隊(duì)列中的數(shù)據(jù)元素遵循先進(jìn)先出FIFO（First in First out）的原則。進(jìn)行插入操作的一端稱(chēng)為隊(duì)尾，進(jìn)行刪除操作的一端成為隊(duì)頭。

2.隊(duì)列的實(shí)現(xiàn)

?????????隊(duì)列可以用數(shù)組和鏈表實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)更優(yōu)，因?yàn)槿绻褂脭?shù)組，在執(zhí)行出隊(duì)列的操作時(shí)效率會(huì)比較低。

a.隊(duì)列結(jié)構(gòu)的定義

typedef int QDataType;

//定義隊(duì)列節(jié)點(diǎn)

typedef struct QueueNode

{

struct QueueNode* next; //后繼指針

QDataType val; //數(shù)值

}QNode;

//隊(duì)列指針

typedef struct Queue

{

QNode* head; //隊(duì)頭指針

QNode* tail; //隊(duì)尾指針

int size; //隊(duì)列中的元素

}Queue;

? ? ? ? 為了簡(jiǎn)化實(shí)現(xiàn)函數(shù)時(shí)參數(shù)的傳遞，我們額外定義一個(gè)包含一個(gè)頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的結(jié)構(gòu)體，其中頭節(jié)點(diǎn)和尾節(jié)點(diǎn)應(yīng)分別指向一個(gè)鏈表的頭和尾。

b.初始化

void QueueInit(Queue* pq)

{

assert(pq);

pq->head = NULL;

pq->tail = NULL;

pq->size = 0;

}

c.創(chuàng)建節(jié)點(diǎn)

QNode* QueueBuyNode(QDataType x)

{

QNode* newNode = (QNode*)malloc(sizeof(QNode));

if (newNode == NULL)

{

perror("malloc fail!");

exit(1);

}

newNode->next = NULL;

newNode->val = x;

return newNode;

}

d.入隊(duì)

void QueuePush(Queue* pq, QDataType x)

{

assert(pq);

QNode* node = QueueBuyNode(x);

if (pq->head == NULL) // 判空

{

pq->head = pq->tail = node;

pq->size++;

}

else

{

pq->tail->next = node;

pq->tail = pq->tail->next;

pq->size++;

}

}

e.出隊(duì)

void QueuePop(Queue* pq)

{

assert(pq && pq->head);

QNode* phead = pq->head;

pq->head = pq->head->next;

free(phead);

phead = NULL;

if (pq->head == NULL) //隊(duì)列為空

pq->tail = NULL;

pq->size--;

}

f.隊(duì)中的元素個(gè)數(shù)

int QueueSize(Queue* pq)

{

assert(pq);

return pq->size;

}

g.隊(duì)列判空

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->size == 0;

}

h.隊(duì)列打印

void QueuePrint(Queue* pq)

{

assert(pq);

if (pq->size == NULL)

{

printf("NULL\n");

return;

}

QNode* pcur = pq->head;

while (pcur)

{

printf("%d ", pcur->val);

pcur = pcur->next;

}

printf("\n");

}

i.取隊(duì)頭元素

QDataType QueueFront(Queue* pq)

{

assert(pq && pq->head);

return pq->head->val;

}

?j.取隊(duì)尾元素

QDataType QueueBack(Queue* pq)

{

assert(pq && pq->tail);

return pq->tail->val;

}

?k.銷(xiāo)毀

void QueueDestroy(Queue* pq)

{

assert(pq);

QNode* pcur = pq->head;

while (pcur)

{

QNode* pnext = pcur->next;

free(pcur);

pcur = pcur->next;

}

pq->head = pq->tail = NULL;

pq->size = 0;

}

柚子快報(bào)激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】第五講：棧和隊(duì)列

http://yzkb.51969.com/

好文閱讀