堆疊的實作：

一、堆疊的概念和性質

堆疊（stack）又名堆疊，它是一種運算受限的線性表，限定僅在固定的一端進行插入和洗掉操作的線性表，這一端被稱為堆疊頂，相對地，把另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，
壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂

二、堆疊的實作思路

堆疊的實作一般可以使用陣列或者鏈表實作，相對而言陣列的結構實作更優一些，因為陣列在尾上插入資料的代價比較小這里我們用順序表結構來實作堆疊，
順序表可以把使用的空間寫成固定值，也可以構建動態開辟記憶體；但是如果寫成固定的陣列形式當存的資料滿了就不能再使用了，所以下面我們實作的是動態開辟記憶體的形式，

所以我們先創建一個順序表結構體型別，結構體型別中有指標，下標，容量，
指標： 用來維護在堆上連續的一段空間，
下標：表示資料存放到哪一個位置了，因為資料只能一個接著一個地存放，要有個下標來記錄我資料放到哪一個位置了，
容量：與下標相比較，當下標與容量相等就表示空間存盤滿了，要進行擴容處理，
創建型別如下：

typedef int STDataType; //對int型別重新起個名字叫DataType

//創建一個堆疊結構體型別
struct Stack   
{
	STDataType* a; //資料的指標
	int top;    //堆疊頂
	int capacity; //記錄開辟空間的最大下標處
};

//對順序表型別struct Stack型別重新起個名字叫SL
typedef struct Stack ST;  

//當size 和 capacity相等時要進行擴容處理

三、堆疊的相關變數記憶體布局圖

四、堆疊的初始化和銷毀

//初始化變數st
void StackInit(ST* ps)
{
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//堆疊的銷毀
void StackDestroy(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

五、堆疊的介面實作：

1.入堆疊

//入堆疊
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//記憶體滿了要擴容
	if (ps->capacity == ps->top)
	{
		ps->capacity = ps->capacity > 0 ? ps->capacity * 2 : 2;
		STDataType* tmp = 
		(STDataType*)realloc(ps->a,sizeof(STDataType) * ps->capacity);
		if (tmp == NULL)
		{
			perror("erron ");
			exit(-1);
		}
		ps->a = tmp;
	}
	//沒有滿就直接在后面入堆疊
	ps->a[ps->top] = x;
	ps->top++;

}

2.出堆疊

//出堆疊，要注意堆疊不能為空
void StackPop(ST* ps)
{
	assert(ps);
	//堆疊為空就不能再出堆疊了
	assert(ps->top >= 1);

	ps->top--;
}

3.獲取堆疊頂的資料

//回傳堆疊頂的元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	//堆疊不能為空
	assert(ps->top >= 1);
	return ps->a[ps->top - 1];

}

4.獲取堆疊的元素個數

//獲取堆疊的元素個數
int StackSize(ST* ps)
{
	assert(ps);
	assert(ps->top >= 1);
	return ps->top - 1;
}

5.判斷堆疊是否為空

//判斷堆疊是否為空
bool StackEmpty(ST* ps)
{
	return ps->top == 0;
}

佇列的實作：

一、佇列的概念和性質

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out)的性質，
佇列：進行插入操作的一端稱為隊尾
出佇列： 進行洗掉操作的一端稱為隊頭

二、佇列的實作思路

佇列也可以陣列和鏈表的結構實作，使用鏈表的結構實作更優一些，因為如果使用陣列的結構，出佇列在陣列頭上出資料，效率會比較低，
而鏈表我們采用雙向鏈接結構，一個指標來維護頭節點，一個指標維護尾部節點

定義的結構體型別如下：

typedef int QDataType;

//創建一個結點型結構體
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

//創建一個佇列
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

三、佇列相關變數的記憶體布局圖

四、佇列的初始化和銷毀

//初始化佇列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

//佇列銷毀
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = NULL;
	pq->tail = NULL;
}

五、佇列的介面實作：

1. 入資料

//入資料有兩種情況
void QueuePush(Queue* pq,QDataType x)
{
	assert(pq);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		perror("erron ");
		exit(-1);
	}
	newNode->next = NULL;
	newNode->data = x;
	//1.入佇列時佇列為空狀態
	if (pq->head == NULL)
	{
		pq->head = newNode;
		pq->tail = newNode;
	}
	//2.入佇列，佇列不為空，直接在尾指標后面鏈接即可
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

2.出資料

//出資料，類似鏈表的頭刪
void QueuePop(Queue* pq)
{
	assert(pq);
	//要保證佇列不能為空
	assert(pq->head != NULL);
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	//防止野指標出現，當佇列為空時要把tail指標置為空
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

3.取隊頭資料

//取隊頭資料
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//檢驗佇列不能為空
	assert(pq->head != NULL);
	return pq->head->data;
}

4.取隊尾資料

//取隊尾資料
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//同樣要檢驗佇列不能為空
	assert(pq->head != NULL);
	return pq->tail->data;
}

5.獲取佇列元素個數

//獲取佇列元素個數
int QueueSize(Queue* pq)
{
	assert(pq);
	int count = 0;
	QueueNode* cur = pq->head;
	while (cur != NULL)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

6.判斷佇列是否為空

//判斷佇列是否為空
bool QueueEmpty(Queue* pq)
{
	return pq->head == NULL;
}

總結

以上就是堆疊和佇列的實作內容了，其中前面我只有把源檔案Stack.c 和Queue.c拆開來分析了，如果想要堆疊和佇列的全部內容，闊以移步到gitee上獲取
【堆疊的原始碼鏈接，點擊即可】
【佇列的原始碼鏈接，點擊即可】