今天我們來完成棧和隊列，首先我們要明白什么是棧，什么是隊列。

目前成都創(chuàng)新互聯(lián)公司已為上千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁空間、網(wǎng)站托管、服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計、東川網(wǎng)站維護(hù)等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

目錄

棧的選擇

棧的結(jié)構(gòu)

棧的初始化

棧的銷毀

入棧

出棧

返回棧頂元素

計算數(shù)據(jù)個數(shù)

判斷是否為空

隊列的選擇

隊列的結(jié)構(gòu)

入隊列

出隊列

判斷是否為空

取隊頭元素

取隊尾元素

計算數(shù)據(jù)個數(shù)

隊列的銷毀

---

我們之前寫過順序表，鏈表，這都是數(shù)據(jù)結(jié)構(gòu)，而棧和隊列，也是數(shù)據(jù)結(jié)構(gòu)，棧的特殊地方在于，棧是后進(jìn)先出，也叫LIFO（last in first out），比如我們平時在桌子上堆放的書，我們堆放了十本書，如果不直接把書抽出來的話，我們要拿到最下面那本書，需要把上面九本先拿下去，也就是先要從最上面的那一本開始拿，而最上面的那一本，是我們最后放上去的，這就是一個棧。再說隊列，隊列的特殊地方在于先進(jìn)先出，也叫FIFO（first in first out），比如我們?nèi)粘Ｉ罾锏呐抨牼褪且粋€隊列，不考慮插隊這些，正常情況下，第一個來的人一定第一個完成自己的業(yè)務(wù)，最后一個來的人最后完成，這就是一個隊列。

我們還是采取工程化的寫法。

首先我們來完成棧，棧的實現(xiàn)可以使用數(shù)組或者鏈表，那我們選取哪個比較好呢？

棧的選擇

我們來比較一下二者的優(yōu)缺點。

首先我們看數(shù)組：?使用數(shù)組就相當(dāng)于之前順序表的尾插和尾刪，用尾去做棧頂，非常合適，唯一的缺點是空間不足時需要擴容。完美避開了順序表插入刪除時需要挪動數(shù)據(jù)的缺點。

我們再來看鏈表，鏈表又有多種結(jié)構(gòu)，我們介紹一種使用單鏈表來完成的，插入和刪除都只有O(1)。

使用這種結(jié)構(gòu)即可完成，最初棧頂和棧底都為空，插入第一個元素后，棧頂棧底都指向第一個元素，每次插入新元素后，只需將其賦給棧頂，刪除時，先刪除節(jié)點，再把棧頂指向棧頂?shù)膎ext即可。

如果用尾做棧頂，那么使用雙向鏈表最好，如果使用頭做棧頂，那么單鏈表最好，插入刪除都是O(1)。

知道了兩種結(jié)構(gòu)完成棧的優(yōu)缺點，大家會選擇哪一個呢？我們這里選擇數(shù)組來完成棧，因為使用數(shù)組的話各方面效率都會更優(yōu)，這里知識和預(yù)加載有關(guān)，這里就不多介紹，我們舉個例子，使用數(shù)組和鏈表的區(qū)別，學(xué)生時代家里每個月都會給你打生活費，數(shù)組就像是一個月給你打一次生活費，夠你一個月花，鏈表就像每天給你打一次，很明顯，使用數(shù)組要比鏈表效率高。

決定好了用什么來實現(xiàn)棧，接著我們來完成棧的結(jié)構(gòu)和各類接口

棧的結(jié)構(gòu)

typedef int STDataType;

typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;
}ST;

我們將其寫為動態(tài)棧，即a不直接寫為數(shù)組，不然就寫死了，并且我們使用top來記錄棧頂位置

接著我們來完成棧的初始化

棧的初始化

void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}

這里的top選取0還是-1看自己喜歡，選取-1代表的是top就是當(dāng)前棧頂元素，選取0表示top為棧頂元素的后一位，我這里選擇初始賦0，同時，如果初始化失敗，我們輸出提示并結(jié)束程序

棧的銷毀

void StackDestory(ST* ps)//銷毀
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

入棧

void StackPush(ST* ps, STDataType x)//入棧
{
	assert(ps);
	if (ps->top == ps->capacity) {//滿了擴容
		STDataType* tmp= (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));
		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}
		else {
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}

入棧時我們要判斷棧是否滿了，滿了需要擴容，擴容時我們擴容到原來的二倍，并且要判斷是否擴容失敗，失敗的話我們給出提示并且結(jié)束程序，入棧后要記得給top+1

出棧

void StackPop(ST* ps)//出棧
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;
}

出棧我們直接使top-1，有人可能會先讓棧頂元素置為0，但是這句是不需要的，因為入棧元素有時候本身就可能為0，并且我們不能隨意出棧，比如top為0時，即空棧，所以我們加一句斷言

返回棧頂元素

STDataType StackTop(ST* ps)//返回棧頂元素
{
	assert(ps);
	assert(ps->top >0);
	return ps->a[ps->top - 1];
}

和出棧同理，棧為空時不能返回，我們加一句斷言

計算數(shù)據(jù)個數(shù)

void StackSize(ST* ps)//計算數(shù)據(jù)個數(shù)
{
	assert(ps);
	return ps->top;
}

判斷是否為空

bool StackEmpty(ST* ps)//判斷是否為空
{
	assert(ps);
	return ps->top == 0;
}

我們直接return ps->top==0，使用bool類型，如果top==0，為真，返回true，否則返回false

我們來測試一下我們的代碼

可以看到，沒有問題。

完成了棧，我們接著來看隊列

隊列的選擇

和棧一樣，隊列也需要在數(shù)組和鏈表里選擇一個，隊列只允許在它的一端插入數(shù)據(jù)，在另一端刪除數(shù)據(jù)

這次其實我們要選擇鏈表，因為數(shù)組會出現(xiàn)假溢出現(xiàn)象，比如這個數(shù)組可以放5個元素，現(xiàn)在已經(jīng)放了四個，我們出隊列一個元素，再入隊列一個，就會發(fā)現(xiàn)數(shù)組下標(biāo)0的位置是空的，但隊列卻顯示已滿，如果要挪動數(shù)據(jù)的話也非常麻煩，還有一種辦法就是寫成循環(huán)隊列，但那是后續(xù)的事情，而且也有局限性。選取鏈表的話，用單鏈表就可以解決，采用上圖結(jié)構(gòu)，隊列就只需要尾插和頭刪，效率都很高。

選擇好了用什么來實現(xiàn)隊列后，我們來設(shè)計隊列的結(jié)構(gòu)吧

隊列的結(jié)構(gòu)

typedef int QDataType;

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

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

我們設(shè)計好隊列的節(jié)點，然后采取兩個指針，隊頭和隊尾來設(shè)計隊列即可。而且采用這樣的結(jié)構(gòu)可以避免使用二級指針（后續(xù)接口如果參數(shù)傳QNode的話是需要二級指針的）

入隊列

void QueuePush(Queue* pq, QDataType x)//入隊列
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

入隊列是在隊尾入元素，入隊列我們需要判斷隊列是否為空，入隊列需要一個新節(jié)點，我們給節(jié)點申請一個空間，申請失敗我們輸出提示并且報錯，然后將x賦給節(jié)點的data，節(jié)點的next置為空，我們還要判斷隊列是否有節(jié)點，如果一個沒有，那么隊頭和隊尾都指向這個新節(jié)點，否則隊尾的next指向新節(jié)點，再把隊尾指向新節(jié)點

出隊列

void QueuePop(Queue* pq)//出隊列
{
	assert(pq);
	assert(pq->head);
	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		Queue* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

出隊列是出隊頭元素，我們要進(jìn)行斷言，我們出隊列需要把頭節(jié)點的空間釋放，然后讓head指向它的next，但在釋放前我們需要把head的next保存起來，否則我們就找不到next了，這是正常情況，如果隊列只有一個元素，出隊列后會造成tail的野指針現(xiàn)象，所以我們需要額外判斷，所以我們把出隊列分為隊列有一個元素和多個元素的情況

判斷是否為空

bool QueueEmpty(Queue* pq)//判斷是否為空
{
	assert(pq);
	return pq->head == NULL;
}

我們直接返回該判斷語句即可，為空返回true，否則返回false

取隊頭元素

QDataType QueueFront(Queue* pq)//取隊頭元素
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}

我們直接返回隊頭元素即可，最好再加一句斷言，有時候會很有用，比如初始化后，隊列里沒有元素，這種情況沒有第二句斷言我們就不知道程序哪里出現(xiàn)了錯誤

取隊尾元素

QDataType QueueBack(Queue* pq)//取隊尾元素
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}

取隊尾元素與取隊頭元素同理

計算數(shù)據(jù)個數(shù)

int QueueSize(Queue* pq)//計算數(shù)據(jù)個數(shù)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur) {
		cur = cur->next;
		size++;
	}
	return size;
}

這個接口有人可能會把循環(huán)條件寫成cur！=pq->tail，但這樣是錯誤的，會少計算一個元素

隊列的銷毀

void QueueDestory(Queue* pq)//銷毀
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

銷毀需要注意先要保存cur的下一個，不然會找不到，然后就是最后要把head和tail置為空

我們最后再來測試一下代碼

沒有問題，到這里，我們的棧和隊列以及他們的接口就全部實現(xiàn)了，希望大家可以有所收獲，下面我會附上全部代碼

#pragma once
//Stack.h
#include#include#include
#includetypedef int STDataType;

typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps);//初始化
void StackDestory(ST* ps);//銷毀
void StackPush(ST* ps,STDataType x);//入棧
void StackPop(ST* ps);//出棧
STDataType StackTop(ST* ps);//返回棧頂元素
void StackSize(ST* ps);//計算數(shù)據(jù)個數(shù)
bool StackEmpty(ST* ps);//判斷是否為空

//Stack.c
#include "Stack.h"
void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	ps->capacity = 4;
	ps->top = 0;
}
void StackDestory(ST* ps)//銷毀
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}
void StackPush(ST* ps, STDataType x)//入棧
{
	assert(ps);
	if (ps->top == ps->capacity) {//滿了擴容
		STDataType* tmp= (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));
		if (tmp == NULL) {
			printf("realloc fail\n");
			exit(-1);
		}
		else {
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)//出棧
{
	assert(ps);
	assert(ps->top>0);
	ps->top--;
}
STDataType StackTop(ST* ps)//返回棧頂元素
{
	assert(ps);
	assert(ps->top >0);
	return ps->a[ps->top - 1];
}
void StackSize(ST* ps)//計算數(shù)據(jù)個數(shù)
{
	assert(ps);
	return ps->top;
}
bool StackEmpty(ST* ps)//判斷是否為空
{
	assert(ps);
	return ps->top == 0;
}

#pragma once
//Queue.h
#include#include#include
#includetypedef int QDataType;

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

typedef struct Queue
{
	QNode* head;
	QNode* tail;
}Queue;

void QueueInit(Queue* pq);//初始化
void QueueDestory(Queue* pq);//銷毀
void QueuePush(Queue* pq, QDataType x);//入隊列
void QueuePop(Queue* pq);//出隊列
QDataType QueueFront(Queue* pq);//取隊頭元素
QDataType QueueBack(Queue* pq);//取隊尾元素
int QueueSize(Queue* pq);//取數(shù)據(jù)個數(shù)
bool QueueEmpty(Queue* pq);//判斷是否為空

//Queue.c
#include"Queue.h"

void QueueInit(Queue* pq)//初始化
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestory(Queue* pq)//銷毀
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)//入隊列
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
void QueuePop(Queue* pq)//出隊列
{
	assert(pq);
	assert(pq->head);
	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		Queue* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
QDataType QueueFront(Queue* pq)//取隊頭元素
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)//取隊尾元素
{
	assert(pq);
	assert(pq->head);
	return pq->tail->data;
}
int QueueSize(Queue* pq)//計算數(shù)據(jù)個數(shù)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur) {
		cur = cur->next;
		size++;
	}
	return size;
}
bool QueueEmpty(Queue* pq)//判斷是否為空
{
	assert(pq);
	return pq->head == NULL;
}

//test.c
#include "Stack.h"
#include"Queue.h"
void testStack() {
	ST st;
	StackInit(&st);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	while (!StackEmpty(&st)) {
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}

	StackDestory(&st);
}

void testQueue() {
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	while (!QueueEmpty(&q)) {
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	QueueDestory(&q);
}
int main() {
	//testStack();
	testQueue();
	return 0;
}

如有錯誤，還請指正。

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

網(wǎng)站標(biāo)題：棧和隊列及其多種接口實現(xiàn)-c語言-創(chuàng)新互聯(lián)
文章路徑：http://weahome.cn/article/ddddss.html