欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語(yǔ)言 淺談棧與隊(duì)列的定義與操作

 更新時(shí)間：2021年11月04日 08:33:31   作者：王不患吖吖吖  
棧和隊(duì)列，嚴(yán)格意義上來(lái)說(shuō)，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯?chǔ)邏輯關(guān)系為 "一對(duì)一" 的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨(dú)作為一章，做重點(diǎn)講解

棧的定義

棧同樣是一種線性表，它的特性是插入元素必須從后面插入，刪除元素也是從后面刪除，進(jìn)行數(shù)據(jù)刪除和插入的一端稱為棧頂，另一端是棧底。
壓?！褪遣迦朐?br /> 出?！褪莿h除元素
它可以用數(shù)組實(shí)現(xiàn)也可以用鏈表實(shí)現(xiàn)

在這里插入圖片描述

但是用數(shù)組實(shí)現(xiàn)更好，因?yàn)殒湵淼牟迦牒蛣h除要進(jìn)行遍歷，而數(shù)組可以進(jìn)行隨機(jī)訪問(wèn)，從而時(shí)間復(fù)雜度更低。

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

前置

棧的元素需要表明容量，還有棧頂

typedef int SDType;
typedef struct Srack
{
	SDType* a;
	int top;
	int capacity;

}ST;

初始化棧

把元素置為空，棧頂在下標(biāo)為0的位置

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

棧的銷毀

不再贅述

void StackDestrory(ST* ps)
{
	assert(ps);
	free(ps);
	ps=NULL;
	ps->capacity = ps->top = 0;
}

棧的插入

先判空，如果容量滿了，進(jìn)行增容，把棧頂元素進(jìn)行賦值，再把棧頂指針加一

void StackPush(ST* ps, SDType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SDType* tmp = (SDType)realloc(ps->capacity, sizeof(SDType) * newCapacity);
		if (tmp == NULL)
		{
			printf("Realloc fail!\n");
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newCapacity;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

出棧的操作

棧頂指針減一即可

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

}

取棧頂元素

先進(jìn)行判空，不空的話直接取出棧頂指針指向的元素

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

棧的大小

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

判斷棧是否為空

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

隊(duì)列的定義

隊(duì)列只允許在一段進(jìn)行插入操作，一段進(jìn)行刪除操作，在隊(duì)尾進(jìn)行插入，在隊(duì)頭進(jìn)行刪除

在這里插入圖片描述

隊(duì)列的基本操作

隊(duì)列的初始化

我們?cè)谶M(jìn)行基本操作的時(shí)候要用到頭指針和尾指針

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


}

隊(duì)列的銷毀

將臨時(shí)指針cur被賦值為head，保存下一個(gè)，遍歷進(jìn)行刪除，最后把頭指針和尾指針進(jìn)行free

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

隊(duì)列的插入

隊(duì)列只能從隊(duì)尾查，如果開(kāi)始的時(shí)候隊(duì)頭和隊(duì)尾重合，那就直接進(jìn)行插入，
如果不，那就找到尾，在尾后邊進(jìn)行插入

void QueuePush(Queue* pq,QDataType x)
{
	assert(pq);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	newNode->data = x;
	newNode->next = NULL;
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
}

隊(duì)列的刪除

很簡(jiǎn)單，刪除隊(duì)尾頭元素，先保存下一個(gè)，再把隊(duì)頭復(fù)制給新的

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* NewHead = pq->head->next;
	free(pq->head);
	pq->head = NewHead;
	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
}

隊(duì)列的判空

是否隊(duì)頭指向空

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

取出隊(duì)頭元素

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

取出隊(duì)尾元素

先判空

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

}

隊(duì)列的大小

直接遍歷就行

int QueueSize(Queue* pq)
{
	assert(pq);
	int n = 0;
	QueueNode* cur = pq->head;
	while (cur)
	{
		cur = cur->next;
		n++;
	}
	return n;
}

點(diǎn)個(gè)贊把

到此這篇關(guān)于C語(yǔ)言 淺談棧與隊(duì)列的定義與操作的文章就介紹到這了,更多相關(guān)C語(yǔ)言 棧與隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評(píng)論