柚子快報激活碼778899分享：【數據結構】第五講：棧和隊列

http://yzkb.51969.com/

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

數據結構專欄：數據結構與算法

源碼獲?。簲祿Y構: 上傳我寫的關于數據結構的代碼 (gitee.com)

目錄

一、棧

1.棧的定義

?2.棧的實現

?a.棧結構的定義

b.初始化

c.擴容

d.入棧

e.出棧

f.打印

g.取棧頂元素

?h.判空

i.獲取棧中的元素個數

j.銷毀

二、隊列?

1.隊列的定義

2.隊列的實現

a.隊列結構的定義

b.初始化

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

d.入隊

e.出隊

f.隊中的元素個數

g.隊列判空

h.隊列打印

i.取隊頭元素

?j.取隊尾元素

?k.銷毀

一、棧

1.棧的定義

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

?2.棧的實現

? ? ? ? 棧的實現一般可以用數組和鏈表實現，一般情況下用數組實現更為合適，因為在數組尾部進行插入和刪除操作的代價較小。

?a.棧結構的定義

typedef int STDataType;

//定義棧結構（數組）

typedef struct Stack

{

STDataType* a; //數組棧

int top; //棧頂

int capacity; //容量

}Stack;

b.初始化

void STInit(Stack* pst)

{

assert(pst);

pst->a = NULL;

pst->capacity = 0;

pst->top = -1;

}

c.擴容

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;

}

}

? ? ? ? 在對棧中的數組進行擴容時，需要注意其他參數如容量（capacity）的變化，在一開始我們將capacity初始化為0，所以在這里要對capacity進行判空。

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.獲取棧中的元素個數

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.隊列的定義

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

2.隊列的實現

?????????隊列可以用數組和鏈表實現，使用鏈表的結構更優(yōu)，因為如果使用數組，在執(zhí)行出隊列的操作時效率會比較低。

a.隊列結構的定義

typedef int QDataType;

//定義隊列節(jié)點

typedef struct QueueNode

{

struct QueueNode* next; //后繼指針

QDataType val; //數值

}QNode;

//隊列指針

typedef struct Queue

{

QNode* head; //隊頭指針

QNode* tail; //隊尾指針

int size; //隊列中的元素

}Queue;

? ? ? ? 為了簡化實現函數時參數的傳遞，我們額外定義一個包含一個頭節(jié)點和尾節(jié)點的結構體，其中頭節(jié)點和尾節(jié)點應分別指向一個鏈表的頭和尾。

b.初始化

void QueueInit(Queue* pq)

{

assert(pq);

pq->head = NULL;

pq->tail = NULL;

pq->size = 0;

}

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

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.隊中的元素個數

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分享：【數據結構】第五講：棧和隊列

http://yzkb.51969.com/

好文閱讀