文章目錄

目錄

前言

一、棧

1.棧的概念及結(jié)構(gòu)

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

入棧

?出棧

?獲取棧頂元素

?獲取棧中有效元素個(gè)數(shù)

?檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0?

?銷毀棧

二、隊(duì)列

1.隊(duì)列的概念及結(jié)構(gòu)

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

初始化隊(duì)列

?隊(duì)尾入隊(duì)列

?隊(duì)頭出隊(duì)列

??獲取隊(duì)列隊(duì)頭元素

?獲取隊(duì)列隊(duì)尾元素

?獲取隊(duì)列中有效元素個(gè)數(shù)

?檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0?

銷毀隊(duì)列?

?最后

---

前言

本篇文章內(nèi)容講述了棧和隊(duì)列的概念結(jié)構(gòu)、分類與函數(shù)聲明部分，以及對(duì)于各個(gè)函數(shù)的實(shí)現(xiàn)。

以下內(nèi)容僅供參考，歡迎各位大佬批評(píng)指正呦~

---

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

?

一、棧

1.棧的概念及結(jié)構(gòu)

棧：一種特殊的線性表，其只允許在固定的一端進(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í)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的 代價(jià)比較小。

// 下面是定長的靜態(tài)棧的結(jié)構(gòu)，實(shí)際中一般不實(shí)用，所以我們主要實(shí)現(xiàn)下面的支持動(dòng)態(tài)增長的棧
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType a[N];int _top; // 棧頂
}ST;// 支持動(dòng)態(tài)增長的棧
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top; // 棧頂int capacity; // 容量
}ST;// 初始化棧
void StackInit(ST* ps); // 入棧
void StackPush(ST* ps, STDataType x); // 出棧
void StackPop(ST* ps); // 獲取棧頂元素
STDataType StackTop(ST* ps); // 獲取棧中有效元素個(gè)數(shù)
int StackSize(ST* ps); // 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0 
int StackEmpty(ST* ps); // 銷毀棧
void StackDestroy(ST* ps); 

初始化棧

void StackInit(ST* ps)
{assert(ps);ps->a = (STDatatype)malloc(sizeof(STDatatype) * 4);if (ps->a == NULL){perror("malloc fail");exit(-1);}ps->top = 0;ps->capacity = 4;
}

入棧

void StackPush(ST* ps, STDatatype x)
{assert(ps);if (ps->top == ps->capacity){STDatatype* tmp = (STDatatype*)realloc(ps->a,ps->capacity*2*sizeof(STDatatype));if (tmp == NULL){perror("realloc fail");exit(-1);}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;}

?出棧

void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}

?獲取棧頂元素

STDatatype StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}

?獲取棧中有效元素個(gè)數(shù)

int StackSize(ST* ps)
{assert(ps);return ps->top;
}

?檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0?

bool StackEmpty(ST* ps) 
{assert(ps);return ps->top == 0;
}

?銷毀棧

void StackDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 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)

隊(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ì)比較低。

// 鏈?zhǔn)浇Y(jié)構(gòu)：表示隊(duì)列
typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;// 隊(duì)列的結(jié)構(gòu)
typedef struct Queue
{ QNode* head;QNode* tail;int size;
}Queue; // 初始化隊(duì)列
void QueueInit(Queue* pq); // 隊(duì)尾入隊(duì)列
void QueuePush(Queue* pq, QDataType data); // 隊(duì)頭出隊(duì)列
void QueuePop(Queue* pq); // 獲取隊(duì)列頭部元素
QDataType QueueFront(Queue* pq); // 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* pq); // 獲取隊(duì)列中有效元素個(gè)數(shù)
int QueueSize(Queue* pq); // 檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0 
int QueueEmpty(Queue* pq); // 銷毀隊(duì)列
void QueueDestroy(Queue* pq);

初始化隊(duì)列

void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->size = 0;
}

?隊(duì)尾入隊(duì)列

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}

?隊(duì)頭出隊(duì)列

void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);}pq->size--;
}

??獲取隊(duì)列隊(duì)頭元素

QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

?獲取隊(duì)列隊(duì)尾元素

QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

?獲取隊(duì)列中有效元素個(gè)數(shù)

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

?檢測隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0?

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL && pq->tail == NULL;
}

銷毀隊(duì)列?

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);//del = NULL;}pq->head = pq->tail = NULL;pq->size = 0;
}

---

?最后

快樂的時(shí)光總是短暫的，以上就是今天要講的內(nèi)容，本文介紹了小趙同志對(duì)算法與數(shù)據(jù)結(jié)構(gòu)（C語言）的棧和隊(duì)列的初步認(rèn)知以及實(shí)現(xiàn)。歡迎家人們批評(píng)指正。小趙同志繼續(xù)更新，不斷學(xué)習(xí)的動(dòng)力是寶子們一鍵三連的支持呀~

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??