棧的定義

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

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

棧的實現

前置

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

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語言 棧與隊列內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！

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