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

http://yzkb.51969.com/

?個人主頁：深情秋刀魚@-CSDN博客

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

源碼獲?。簲?shù)據(jù)結(jié)構(gòu): 上傳我寫的關(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.獲取棧中的元素個數(shù)

j.銷毀

二、隊列?

1.隊列的定義

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

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

b.初始化

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

d.入隊

e.出隊

f.隊中的元素個數(shù)

g.隊列判空

h.隊列打印

i.取隊頭元素

?j.取隊尾元素

?k.銷毀

一、棧

1.棧的定義

? ? ? ? 棧是一種特殊的線性表，其只允許在固定的一段進(jìn)行插入和刪除元素的操作。進(jìn)行數(shù)據(jù)的插入和刪除元素的操作的一端被稱為棧頂，另一端被稱為棧底。棧中的數(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)行插入和刪除操作的代價較小。

?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;

}

}

? ? ? ? 在對棧中的數(shù)組進(jìn)行擴(kuò)容時，需要注意其他參數(shù)如容量（capacity）的變化，在一開始我們將capacity初始化為0，所以在這里要對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.獲取棧中的元素個數(shù)

int STSize(Stack* pst)

{

assert(pst);

return pst->top + 1;

}

j.銷毀

void STDestroy(Stack* pst)

{

assert(pst);

free(pst->a);

pst->a = NULL;

pst->capacity = 0;

pst->top = 0;

}

二、隊列?

1.隊列的定義

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

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

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

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

typedef int QDataType;

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

typedef struct QueueNode

{

struct QueueNode* next; //后繼指針

QDataType val; //數(shù)值

}QNode;

//隊列指針

typedef struct Queue

{

QNode* head; //隊頭指針

QNode* tail; //隊尾指針

int size; //隊列中的元素

}Queue;

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

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.入隊

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.出隊

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) //隊列為空

pq->tail = NULL;

pq->size--;

}

f.隊中的元素個數(shù)

int QueueSize(Queue* pq)

{

assert(pq);

return pq->size;

}

g.隊列判空

bool QueueEmpty(Queue* pq)

{

assert(pq);

return pq->size == 0;

}

h.隊列打印

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.取隊頭元素

QDataType QueueFront(Queue* pq)

{

assert(pq && pq->head);

return pq->head->val;

}

?j.取隊尾元素

QDataType QueueBack(Queue* pq)

{

assert(pq && pq->tail);

return pq->tail->val;

}

?k.銷毀

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;

}

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

http://yzkb.51969.com/

好文閱讀