棧的定義

棧同樣是一種線性表，它的特性是插入元素必須從后面插入，刪除元素也是從后面刪除，進行數(shù)據(jù)刪除和插入的一端稱為棧頂，另一端是棧底。
壓棧―就是插入元素
出棧―就是刪除元素
它可以用數(shù)組實現(xiàn)也可以用鏈表實現(xiàn)

但是用數(shù)組實現(xiàn)更好，因為鏈表的插入和刪除要進行遍歷，而數(shù)組可以進行隨機訪問，從而時間復雜度更低。

棧的實現(xiàn)

前置

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

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

}ST;

初始化棧

把元素置為空，棧頂在下標為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;
}

棧的插入

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

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--;

}

取棧頂元素

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

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;
}

隊列的定義

隊列只允許在一段進行插入操作，一段進行刪除操作，在隊尾進行插入，在隊頭進行刪除

隊列的基本操作

隊列的初始化

我們在進行基本操作的時候要用到頭指針和尾指針

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


}

隊列的銷毀

將臨時指針cur被賦值為head，保存下一個，遍歷進行刪除，最后把頭指針和尾指針進行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;
}

隊列的插入

隊列只能從隊尾查，如果開始的時候隊頭和隊尾重合，那就直接進行插入，
如果不，那就找到尾，在尾后邊進行插入

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;
	}
}

隊列的刪除

很簡單，刪除隊尾頭元素，先保存下一個，再把隊頭復制給新的

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;
	}
}

隊列的判空

是否隊頭指向空

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

取出隊頭元素

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

取出隊尾元素

先判空

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

}

隊列的大小

直接遍歷就行

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

點個贊把

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

原文鏈接：https://blog.csdn.net/m0_56186053/article/details/121100409