亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C語言超詳細講解棧與隊列實現(xiàn)實例

 更新時間：2022年03月29日 14:43:51   作者：許同學。。  
棧和隊列，嚴格意義上來說，也屬于線性表，因為它們也都用于存儲邏輯關系為?"一對一"?的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨作為一章，做重點講解

1.思考-1

為什么棧用數(shù)組來模擬比用鏈表來模擬更優(yōu)一些？

隊列也可以數(shù)組和鏈表的結構實現(xiàn)，使用鏈表的結構實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結構，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低，時間復雜度為O(n)。

2.?；静僮鞯膶崿F(xiàn)

2.1 初始化棧

void StackInit(stack*ps)
{
	assert(ps);
	ps->_a = (StackDate*)malloc(sizeof(StackDate) * 4);
	ps->_top = 0;
	ps->_capacity = 4;
}

2.2 入棧

void StackPush(stack*ps, StackDate x)
{
	assert(ps);
	if (ps->_top == ps->_capacity)
	{
		stack*tmp = (StackDate*)realloc(ps, sizeof(StackDate)*(ps->_capacity) * 2);
		if (NULL == tmp)
		{
			printf("realloc failed\n");
			exit(-1);
		}
		ps = tmp;
		ps->_capacity *= 2;
	}
	ps->_a[ps->_top] = x;
	ps->_top++;
}

2.3 出棧

void StackPop(stack*ps)
{
	assert(ps);
	assert(!StackIsEmpty(ps));
	--ps->_top;
}

注意： 出棧并不是真正意義上的刪除數(shù)據(jù)，而是將_top向后挪動了一個位置。

2.4 獲取棧頂數(shù)據(jù)

StackDate StackTop(stack*ps)
{
	assert(ps);
	assert(!StackIsEmpty(ps));
	return ps->_a[ps->_top - 1];
}

2.5 獲取棧中有效元素個數(shù)

int StackSize(stack*ps)
{
	assert(ps);
	return ps->_top;
}

2.6 判斷棧是否為空

bool StackIsEmpty(stack*ps)
{
	assert(ps);
	return ps->_top == 0;
}

2.7 銷毀棧

void StackDestory(stack*ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_top = ps->_capacity = 0;
}

3.測試

3.1 測試

void test()
{
	//插入數(shù)據(jù)
	stack  st;
	StackInit(&st);
	StackPush(&st,1);
	StackPush(&st,2);
	StackPush(&st,3);
	StackPush(&st,4);
	while (!StackIsEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	printf("\n");


	//獲取棧頂數(shù)據(jù)
	StackPush(&st, 1);
	StackPush(&st, 2);
	printf("%d ", StackTop(&st));
	printf("\n");

	
	//棧中有效數(shù)據(jù)個數(shù)
	printf("%d ", StackSize(&st));

	
	//銷毀棧
	StackDestory(&st);
}

3.2 測試結果

4.思考-2

為什么隊列用鏈表模擬比數(shù)組模擬更加合適？

棧的實現(xiàn)一般可以使用數(shù)組或者鏈表實現(xiàn)，相對而言數(shù)組的結構實現(xiàn)更優(yōu)一些。因為數(shù)組在尾上插入數(shù)據(jù)的代價小。

5.隊列的基本操作實現(xiàn)

5.1 初始化隊列

void QueueInit(Queue*pq)
{
	assert(pq);
	pq->_head = pq->_tail = NULL;
}

5.2 隊尾入隊列

void QueuePush(Queue*pq, QueueDate x)
{
	assert(pq);
	QueueNode*newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (NULL == newnode)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->val = x;
	if (NULL == pq->_tail)
	{
		pq->_head = pq->_tail = newnode;
	}
	else
	{
		pq->_tail->next = newnode;
		pq->_tail = newnode;
	}
}

5.3 隊頭出隊列

void QueuePop(Queue*pq)
{
	assert(pq);
	assert(!QueueIsEmpty(pq));
	if (NULL == pq->_head->next)
	{
		free(pq->_head);
		pq->_head = pq->_tail = NULL;
		
	}
	else
	{
		QueueNode*next = pq->_head->next;
		free(pq->_head);
		pq->_head = next;
	}
}

代碼分析：

5.4 隊列中有效元素的個數(shù)

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

5.5 判斷隊列是否為空

bool QueueIsEmpty(Queue*pq)
{
	assert(pq);
	return pq->_head == NULL;
}

5.6 獲取隊頭數(shù)據(jù)

QueueDate QueueFront(Queue*pq)
{
	assert(pq);
	assert(!QueueIsEmpty(pq));
	return pq->_head->val;
}

5.7 獲取隊尾的數(shù)據(jù)

QueueDate QueueBack(Queue*pq)
{
	assert(pq);
	assert(!QueueIsEmpty(pq));
	return pq->_tail->val;
}

5.8 銷毀隊列

void QueueDestory(Queue*pq)
{
	assert(pq);
	while (pq->_head)
	{
		if (pq->_head == pq->_tail)
		{
			free(pq->_head);
			pq->_head = pq->_tail = NULL;
		}
		else
		{
			QueueNode*next = pq->_head->next;
			free(pq->_head);
			pq->_head = next;
		}
	}
}

注意： 和隊頭出隊列一樣分析。

6.測試

6.1 測試

void test1()
{
	//插入數(shù)據(jù)
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);


	//有效數(shù)據(jù)的個數(shù)
	printf("%d ", QueueSize(&q));
	printf("\n");


	//獲取隊頭數(shù)據(jù)
	printf("%d",QueueFront(&q));
	printf("\n");


	//獲取隊尾數(shù)據(jù)
	printf("%d",QueueBack(&q));
	printf("\n");


	//出隊
	QueuePop(&q);
	while (!QueueIsEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");


	//銷毀
	QueueDestory(&q);
	printf("\n");
}

6.2 測試結果

今天數(shù)據(jù)結構棧與隊列的相關知識點就分享到這里了，感謝你的瀏覽，如果對你有幫助的話，可以給個關注，順便來個贊。

到此這篇關于C語言超詳細講解棧與隊列實現(xiàn)實例的文章就介紹到這了,更多相關C語言 棧與隊列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

最新評論