1.棧 1.1棧的概念及結構

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

創新互聯公司堅持“要么做到，要么別承諾”的工作理念，服務領域包括：網站制作、成都網站建設、企業官網、英文網站、手機端網站、網站推廣等服務，滿足客戶于互聯網時代的莒縣網站設計、移動媒體設計的需求，幫助企業找到有效的互聯網解決方案。努力成為您成熟可靠的網絡建設合作伙伴！

進行數據插入和刪除的一端稱為棧頂，另一端稱為棧底。

棧中的元素遵循后進先出的原則。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，在棧頂進行操作。

出棧：棧的刪除操作叫做出棧，出棧操作同樣在棧頂進行。

1.2棧的實現?

棧的實現一般可以使用數組或者鏈表，相對而言數組的結構更優一些，因為數組代價比較小。

從上圖可以看出，相對于單向不帶頭非循環鏈表而言，數組在進行尾插和尾刪的時候可以直接使用下標進行操作，所以我們在實現棧的時候使用的是動態開辟的數組。

// 支持動態增長的棧
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判斷棧是否為空?

// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回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獲取棧中數據的有效個數

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.隊列 2.1隊列的概念及結構

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表。

隊列具有先進先出的特點，進行插入操作的一端稱為隊尾，進行刪除操作的一端是隊頭。

2.2隊列的實現

隊列也可以使用數組和鏈表結構實現，使用鏈表的結構更優，因為如果使用數組的結構，出隊列在數組頭上出數據，效率降低。

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

typedef struct Queue
{
	//int size;
	QNode* head;//指向隊列的頭節點
	QNode* tail;//指向隊列的尾節點
}Queue;

2.2.1隊列的初始化和銷毀

// 初始化隊列
void QueueInit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
}
// 銷毀隊列
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* next = cur->next;//先保存next  否則釋放后無法訪問后面的空間
		free(cur);
		cur = next;
	}

	q->head = q->tail = NULL;
}

2.2.1隊尾入數據

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)//隊列中沒有數據
		q->head = q->tail = newnode;
	else//隊列中有數據
	{
		q->tail->next = newnode;
		//更新q->tail
		q->tail = newnode;
	}
}

2.2.3隊頭出數據

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head == q->tail)//隊列只有一個數據
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else//隊列中不止一個數據
	{
		QNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
}

2.3.4獲取隊頭和隊尾的數據

//獲取隊頭數據
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

2.3.5獲取隊列中元素個數

int QueueSize(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	int count = 0;
	while (cur)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

2.3.6判斷隊列是否為空

// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;//或者使用q->tail == NULL
}

棧和隊列的實現到這里就結束了，想要了解更多數據結構和C++方向的內容，那就點個關注吧，后面會繼續更新數據結構和C++方向的內容。

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

文章標題：【數據結構】棧和隊列的實現-創新互聯
網頁鏈接：http://www.yijiale78.com/article4/cspgie.html

成都網站建設公司_創新互聯，為您提供網站改版、響應式網站、標簽優化、服務器托管、App設計、用戶體驗

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯