文章目錄

目錄

前言

一、棧

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

2.棧的實現(xiàn)

入棧

?出棧

?獲取棧頂元素

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

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

?銷毀棧

二、隊列

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

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

初始化隊列

?隊尾入隊列

?隊頭出隊列

??獲取隊列隊頭元素

?獲取隊列隊尾元素

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

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

銷毀隊列?

?最后

---

前言

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

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

---

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

?

一、棧

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

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數(shù)據(jù)插入和刪除操作的一端 稱為棧頂，另一端稱為棧底。棧中的數(shù)據(jù)元素遵守后進先出LIFO（Last In First Out）的原則。 壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。 出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。?

2.棧的實現(xiàn)

棧的實現(xiàn)一般可以使用數(shù)組或者鏈表實現(xiàn)，相對而言數(shù)組的結(jié)構(gòu)實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據(jù)的 代價比較小。

// 下面是定長的靜態(tài)棧的結(jié)構(gòu)，實際中一般不實用，所以我們主要實現(xiàn)下面的支持動態(tài)增長的棧
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType a[N];int _top; // 棧頂
}ST;// 支持動態(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); // 獲取棧中有效元素個數(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];
}

?獲取棧中有效元素個數(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;
}

二、隊列

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

隊列：只允許在一端進行插入數(shù)據(jù)操作，在另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出 FIFO(First In First Out) 入隊列：進行插入操作的一端稱為隊尾 出隊列：進行刪除操作的一端稱為隊頭

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

隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù) 組頭上出數(shù)據(jù)，效率會比較低。

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

初始化隊列

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

?隊尾入隊列

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++;
}

?隊頭出隊列

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

??獲取隊列隊頭元素

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

?獲取隊列隊尾元素

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

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

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

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

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

銷毀隊列?

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

---

?最后

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

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