C語言數據結構進階之棧和隊列的實現

Posted on by

棧的實現：

一、棧的概念和性質

棧（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上獲取
【棧的源碼鏈接，點擊即可】
【隊列的源碼鏈接，點擊即可】

到此這篇關於C語言數據結構進階之棧和隊列的實現的文章就介紹到這瞭,更多相關C語言 數據結構 內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：