【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列的實(shí)現(xiàn)-創(chuàng)新互聯(lián)

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

棧：一種特殊的線性表，只允許在固定的一端進(jìn)行插入和刪除元素操作。

創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：網(wǎng)站制作、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的莒縣網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

進(jìn)行數(shù)據(jù)插入和刪除的一端稱為棧頂，另一端稱為棧底。

棧中的元素遵循后進(jìn)先出的原則。

壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，在棧頂進(jìn)行操作。

出棧：棧的刪除操作叫做出棧，出棧操作同樣在棧頂進(jìn)行。

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

棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表，相對(duì)而言數(shù)組的結(jié)構(gòu)更優(yōu)一些，因?yàn)閿?shù)組代價(jià)比較小。

從上圖可以看出，相對(duì)于單向不帶頭非循環(huán)鏈表而言，數(shù)組在進(jìn)行尾插和尾刪的時(shí)候可以直接使用下標(biāo)進(jìn)行操作，所以我們?cè)趯?shí)現(xiàn)棧的時(shí)候使用的是動(dòng)態(tài)開辟的數(shù)組。

// 支持動(dòng)態(tài)增長(zhǎng)的棧
typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top; // 棧頂
    int capacity; // 容量
}Stack;
1.2.1初始化棧
void StackInit(Stack* ps)
{
    assert(ps);
    ps->a == NULL;
    ps->capacity = ps->top = 0;
}
1.2.2入棧
void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
1.2.3判斷棧是否為空?
// 檢測(cè)棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}
1.2.4出棧
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
1.2.5獲取棧頂元素
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}
1.2.6獲取棧中數(shù)據(jù)的有效個(gè)數(shù)
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}
1.2.7銷毀棧
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
2.隊(duì)列 2.1隊(duì)列的概念及結(jié)構(gòu)

隊(duì)列：只允許在一端進(jìn)行插入數(shù)據(jù)操作，在另一端進(jìn)行刪除數(shù)據(jù)操作的特殊線性表。

隊(duì)列具有先進(jìn)先出的特點(diǎn)，進(jìn)行插入操作的一端稱為隊(duì)尾，進(jìn)行刪除操作的一端是隊(duì)頭。

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

隊(duì)列也可以使用數(shù)組和鏈表結(jié)構(gòu)實(shí)現(xiàn)，使用鏈表的結(jié)構(gòu)更優(yōu)，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率降低。

typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	//int size;
	QNode* head;//指向隊(duì)列的頭節(jié)點(diǎn)
	QNode* tail;//指向隊(duì)列的尾節(jié)點(diǎn)
}Queue;
2.2.1隊(duì)列的初始化和銷毀
// 初始化隊(duì)列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
}
// 銷毀隊(duì)列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;//先保存next  否則釋放后無(wú)法訪問(wèn)后面的空間
		free(cur);
		cur = next;
	}

	q->head = q->tail = NULL;
}
2.2.1隊(duì)尾入數(shù)據(jù)
void QueuePush(Queue* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (q->head == NULL)//隊(duì)列中沒(méi)有數(shù)據(jù)
		q->head = q->tail = newnode;
	else//隊(duì)列中有數(shù)據(jù)
	{
		q->tail->next = newnode;
		//更新q->tail
		q->tail = newnode;
	}
}
2.2.3隊(duì)頭出數(shù)據(jù)
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head == q->tail)//隊(duì)列只有一個(gè)數(shù)據(jù)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else//隊(duì)列中不止一個(gè)數(shù)據(jù)
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
}
2.3.4獲取隊(duì)頭和隊(duì)尾的數(shù)據(jù)
//獲取隊(duì)頭數(shù)據(jù)
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
// 獲取隊(duì)列隊(duì)尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}
2.3.5獲取隊(duì)列中元素個(gè)數(shù)
int QueueSize(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
2.3.6判斷隊(duì)列是否為空
// 檢測(cè)隊(duì)列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;//或者使用q->tail == NULL
}

棧和隊(duì)列的實(shí)現(xiàn)到這里就結(jié)束了，想要了解更多數(shù)據(jù)結(jié)構(gòu)和C++方向的內(nèi)容，那就點(diǎn)個(gè)關(guān)注吧，后面會(huì)繼續(xù)更新數(shù)據(jù)結(jié)構(gòu)和C++方向的內(nèi)容。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章標(biāo)題：【數(shù)據(jù)結(jié)構(gòu)】棧和隊(duì)列的實(shí)現(xiàn)-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)鏈接：http://muchs.cn/article4/cspgie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、響應(yīng)式網(wǎng)站、標(biāo)簽優(yōu)化、服務(wù)器托管、App設(shè)計(jì)、用戶體驗(yàn)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

成都定制網(wǎng)站網(wǎng)頁(yè)設(shè)計(jì)