91精品观看91久久久久久,91热久久免费频精品99欧美,狠狠色丁香婷婷综合

棧的實(shí)現(xiàn)：

一、棧的概念和性質(zhì)

棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。限定僅在固定的一端進(jìn)行插入和刪除操作的線性表。這一端被稱(chēng)為棧頂，相對(duì)地，把另一端稱(chēng)為棧底。棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)

二、棧的實(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à)比較小這里我們用順序表結(jié)構(gòu)來(lái)實(shí)現(xiàn)棧。
順序表可以把使用的空間寫(xiě)成固定值，也可以構(gòu)建動(dòng)態(tài)開(kāi)辟內(nèi)存；但是如果寫(xiě)成固定的數(shù)組形式當(dāng)存的數(shù)據(jù)滿了就不能再使用了，所以下面我們實(shí)現(xiàn)的是動(dòng)態(tài)開(kāi)辟內(nèi)存的形式。

所以我們先創(chuàng)建一個(gè)順序表結(jié)構(gòu)體類(lèi)型，結(jié)構(gòu)體類(lèi)型中有指針，下標(biāo)，容量。
指針：用來(lái)維護(hù)在堆上連續(xù)的一段空間，
下標(biāo)：表示數(shù)據(jù)存放到哪一個(gè)位置了，因?yàn)閿?shù)據(jù)只能一個(gè)接著一個(gè)地存放，要有個(gè)下標(biāo)來(lái)記錄我數(shù)據(jù)放到哪一個(gè)位置了。
容量：與下標(biāo)相比較，當(dāng)下標(biāo)與容量相等就表示空間存儲(chǔ)滿了，要進(jìn)行擴(kuò)容處理。
創(chuàng)建類(lèi)型如下：

typedef int STDataType; //對(duì)int類(lèi)型重新起個(gè)名字叫DataType

//創(chuàng)建一個(gè)棧結(jié)構(gòu)體類(lèi)型
struct Stack   
{
	STDataType* a; //數(shù)據(jù)的指針
	int top;    //棧頂
	int capacity; //記錄開(kāi)辟空間的最大下標(biāo)處
};

//對(duì)順序表類(lèi)型struct Stack類(lèi)型重新起個(gè)名字叫SL
typedef struct Stack ST;  

//當(dāng)size 和 capacity相等時(shí)要進(jìn)行擴(kuò)容處理

三、棧的相關(guān)變量?jī)?nèi)存布局圖

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)

四、棧的初始化和銷(xiāo)毀

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

//棧的銷(xiāo)毀
void StackDestroy(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

五、棧的接口實(shí)現(xiàn)：

1.入棧

//入棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//內(nèi)存滿了要擴(kuò)容
	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;
	}
	//沒(méi)有滿就直接在后面入棧
	ps->a[ps->top] = x;
	ps->top++;

}

2.出棧

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

	ps->top--;
}

3.獲取棧頂?shù)臄?shù)據(jù)

//返回棧頂?shù)脑?
STDataType StackTop(ST* ps)
{
	assert(ps);
	//棧不能為空
	assert(ps->top >= 1);
	return ps->a[ps->top - 1];

}

4.獲取棧的元素個(gè)數(shù)

//獲取棧的元素個(gè)數(shù)
int StackSize(ST* ps)
{
	assert(ps);
	assert(ps->top >= 1);
	return ps->top - 1;
}

5.判斷棧是否為空

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

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

一、隊(duì)列的概念和性質(zhì)

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

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)

二、隊(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ì)比較低。
而鏈表我們采用雙向鏈接結(jié)構(gòu)，一個(gè)指針來(lái)維護(hù)頭節(jié)點(diǎn)，一個(gè)指針維護(hù)尾部節(jié)點(diǎn)

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)

定義的結(jié)構(gòu)體類(lèi)型如下：

typedef int QDataType;

//創(chuàng)建一個(gè)結(jié)點(diǎn)型結(jié)構(gòu)體
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

//創(chuàng)建一個(gè)隊(duì)列
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

三、隊(duì)列相關(guān)變量的內(nèi)存布局圖

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)

四、隊(duì)列的初始化和銷(xiāo)毀

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

//隊(duì)列銷(xiāo)毀
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;
}

五、隊(duì)列的接口實(shí)現(xiàn)：

1. 入數(shù)據(jù)

//入數(shù)據(jù)有兩種情況
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.入隊(duì)列時(shí)隊(duì)列為空狀態(tài)
	if (pq->head == NULL)
	{
		pq->head = newNode;
		pq->tail = newNode;
	}
	//2.入隊(duì)列，隊(duì)列不為空，直接在尾指針后面鏈接即可
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

2.出數(shù)據(jù)

//出數(shù)據(jù)，類(lèi)似鏈表的頭刪
void QueuePop(Queue* pq)
{
	assert(pq);
	//要保證隊(duì)列不能為空
	assert(pq->head != NULL);
	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	//防止野指針出現(xiàn)，當(dāng)隊(duì)列為空時(shí)要把tail指針置為空
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

3.取隊(duì)頭數(shù)據(jù)

//取隊(duì)頭數(shù)據(jù)
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//檢驗(yàn)隊(duì)列不能為空
	assert(pq->head != NULL);
	return pq->head->data;
}

4.取隊(duì)尾數(shù)據(jù)

//取隊(duì)尾數(shù)據(jù)
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//同樣要檢驗(yàn)隊(duì)列不能為空
	assert(pq->head != NULL);
	return pq->tail->data;
}

5.獲取隊(duì)列元素個(gè)數(shù)

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

6.判斷隊(duì)列是否為空

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

總結(jié)

以上就是棧和隊(duì)列的實(shí)現(xiàn)內(nèi)容了，其中前面我只有把源文件Stack.c 和Queue.c拆開(kāi)來(lái)分析了。如果想要棧和隊(duì)列的全部?jī)?nèi)容，闊以移步到gitee上獲取
【棧的源碼鏈接，點(diǎn)擊即可】
【隊(duì)列的源碼鏈接，點(diǎn)擊即可】

到此這篇關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)進(jìn)階之棧和隊(duì)列的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！

原文鏈接：https://blog.csdn.net/m0_56311933/article/details/121068933