快捷導(dǎo)航

C語(yǔ)言棧與隊(duì)列面試題詳解

更新時(shí)間：2022年04月11日 10:17:42 作者：三分苦

棧和隊(duì)列，嚴(yán)格意義上來(lái)說(shuō)，也屬于線性表，因?yàn)樗鼈円捕加糜诖鎯?chǔ)邏輯關(guān)系為 "一對(duì)一" 的數(shù)據(jù)，但由于它們比較特殊，因此將其單獨(dú)作為一章，做重點(diǎn)講解

1、括號(hào)匹配問(wèn)題

鏈接直達(dá)：

有效的括號(hào)

題目：

思路：

做題前，得先明確解題方案是啥，此題用棧的思想去解決是較為方便的，棧明確指出后進(jìn)先出。我們可以這樣設(shè)定：

遇到左括號(hào)“ ( ”、“ [ ”、“ { ”，入棧。
遇到右括號(hào)“ ) ”、“ ] ”、“ } ”，出棧，跟左括號(hào)進(jìn)行匹配，不匹配就報(bào)錯(cuò)。

上兩句話的意思就是說(shuō)我去遍歷字符串，如果遇到左括號(hào)，就入棧；遇到右括號(hào)，就出棧頂元素，并判斷這個(gè)右括號(hào)是否與棧頂括號(hào)相匹配，若不匹配則返回false，匹配繼續(xù)遍歷字符串，直到遍歷完全，遍歷后，檢查棧是否為空，若為空，則均匹配，返回true，反之false。

代碼如下：

//創(chuàng)建棧結(jié)構(gòu)
typedef char STDataType;
typedef struct Stack
{
	STDataType* a; //存儲(chǔ)數(shù)據(jù)
	int top; //棧頂?shù)奈恢?
	int capacity; //容量
}ST;
//初始化棧
void StackInit(ST* ps);
//銷(xiāo)毀棧
void StackDestory(ST* ps);
//壓棧
void StackPush(ST* ps, STDataType x);
//出棧
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//訪問(wèn)棧頂數(shù)據(jù)
STDataType StackTop(ST* ps);
//有效元素個(gè)數(shù)
int StackSize(ST* ps);
 
//定義：
//初始化棧
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}
//銷(xiāo)毀棧
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->top = 0;
}
//壓棧
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//如果棧滿了，考慮擴(kuò)容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測(cè)容量
		ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (ps->a == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->capacity = newcapacity; //更新容量
	}
	ps->a[ps->top] = x;//將數(shù)據(jù)壓進(jìn)去
	ps->top++;//棧頂上移
}
//出棧
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0; //如果top為0，那么就為真，即返回
}
//訪問(wèn)棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}
//有效元素個(gè)數(shù)
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
 
//創(chuàng)建好了棧開(kāi)始實(shí)現(xiàn)
bool isValid(char* s) {
    ST st;//先創(chuàng)建一個(gè)棧
    StackInit(&st);//初始化棧
    while (*s)
    {
        if (*s == '[' || *s == '(' || *s == '{')
        {
            StackPush(&st, *s); //如果是左括號(hào)就入棧
            ++s;
        }
        else
        {
            if (StackEmpty(&st))
            {
                return false; //此處說(shuō)明前面根本沒(méi)有左括號(hào)，導(dǎo)致棧為空，直接返回false
            }
            char top = StackTop(&st); //獲取棧頂元素
            StackPop(&st); //出棧頂元素，接下來(lái)進(jìn)行匹配
            if ((*s == ']' && top != '[')
                || (*s == ')' && top != '(')
                || (*s == '}' && top != '{'))
            {
                StackDestory(&st); //返回前先銷(xiāo)毀，防止內(nèi)存泄漏
                return false; //如果不匹配，直接返回false
            }
            else
            {
                //此時(shí)匹配，繼續(xù)比較，直到遍歷結(jié)束
                ++s;
            }
        }
    }
    //棧為空，說(shuō)明所有左括號(hào)都匹配
    bool ret = StackEmpty(&st);
    StackDestory(&st); //返回前先銷(xiāo)毀，防止內(nèi)存泄漏
    return ret;
}

2、用隊(duì)列實(shí)現(xiàn)棧

鏈接直達(dá)：

用隊(duì)列實(shí)現(xiàn)棧

題目：

思路：

做題之前，再明確下兩個(gè)基本知識(shí)點(diǎn)

棧：后進(jìn)先出
隊(duì)列：先進(jìn)先出

此題要用先進(jìn)先出的隊(duì)列來(lái)實(shí)現(xiàn)后進(jìn)先出的棧，并模擬實(shí)現(xiàn)隊(duì)列的基本接口。

假設(shè)我們有一串?dāng)?shù)字，進(jìn)入隊(duì)列A順序?yàn)? 2 3 4，此時(shí)再有一個(gè)隊(duì)列B，此時(shí)我們?nèi)￡?duì)列A的隊(duì)頭數(shù)據(jù)，并將其導(dǎo)入隊(duì)列B，當(dāng)隊(duì)列A出到只剩最后一個(gè)時(shí)，把隊(duì)列A給pop刪掉，此時(shí)隊(duì)列B就是1 2 3，間接性是實(shí)現(xiàn)了棧的功能，實(shí)現(xiàn)了后進(jìn)先出的功能。當(dāng)我們需要再入數(shù)據(jù)時(shí)，只需往不為空的隊(duì)列入即可。再出就像剛剛那樣。簡(jiǎn)而言之兩句話：

入棧：push數(shù)據(jù)到不為空的隊(duì)列。
出棧：把不為空的隊(duì)列的數(shù)據(jù)前N-1導(dǎo)入另一個(gè)空隊(duì)列，最后剩下一個(gè)刪掉。

本質(zhì)：保持一個(gè)隊(duì)列存儲(chǔ)數(shù)據(jù)，另外一個(gè)隊(duì)列空著，要出棧時(shí)，空隊(duì)列用來(lái)導(dǎo)數(shù)據(jù)。

代碼如下：

//創(chuàng)建隊(duì)列結(jié)構(gòu)
typedef int QDataType; //方便后續(xù)更改存儲(chǔ)數(shù)據(jù)類(lèi)型，本文以int為例
 //創(chuàng)建隊(duì)列節(jié)點(diǎn)
typedef struct QueueNode
{
	QDataType data; //存儲(chǔ)數(shù)據(jù)
	struct QueueNode* next; //記錄下一個(gè)節(jié)點(diǎn)
}QNode;
//保存隊(duì)頭和隊(duì)尾
typedef struct Queue
{
	QNode* head; //頭指針
	QNode* tail; //尾指針
}Queue;
//初始化隊(duì)列
void QueueInit(Queue* pq);
//銷(xiāo)毀隊(duì)列
void QueueDestory(Queue* pq);
//入隊(duì)列
void QueuePush(Queue* pq, QDataType x);
//出隊(duì)列
void QueuePop(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//獲取有效元素個(gè)數(shù)
size_t QueueSize(Queue* pq);
//獲取隊(duì)頭元素
QDataType QueueFront(Queue* pq);
//獲取隊(duì)尾元素
QDataType QueueBack(Queue* pq);
 
//定義：
//初始化隊(duì)列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
//銷(xiāo)毀隊(duì)列
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;
}
//入隊(duì)列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//創(chuàng)建一個(gè)新節(jié)點(diǎn)保存數(shù)據(jù)
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	//暴力檢測(cè)newnode，因?yàn)閙alloc的都要檢測(cè)
	assert(newnode);
	newnode->next = NULL;
	newnode->data = x;
	//如果一開(kāi)始沒(méi)有數(shù)據(jù)，為空的情況
	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
//出隊(duì)列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail); //tail和head均不能為空
	//特殊：當(dāng)刪到head=tail的位置時(shí)
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	//一般情況
	else
	{
		//保存head的下一個(gè)節(jié)點(diǎn)
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
//判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
//獲取有效元素個(gè)數(shù)
size_t QueueSize(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	size_t size = 0;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}
//獲取隊(duì)頭元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head); //頭部不能為空
	return pq->head->data;
}
//獲取隊(duì)尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail); //尾部不能為空
	return pq->tail->data;
}
 
/**************創(chuàng)建好隊(duì)列結(jié)構(gòu)，開(kāi)始正文模擬實(shí)現(xiàn)棧**************/
typedef struct {
	Queue q1; //隊(duì)列q1
	Queue q2; //隊(duì)列q2
} MyStack;
 
 
MyStack* myStackCreate() {
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); //申請(qǐng)一個(gè)MyStack類(lèi)型的棧
	assert(pst);
	QueueInit(&pst->q1);//初始化隊(duì)列1
	QueueInit(&pst->q2);//初始化隊(duì)列2
	return pst;
}
 
void myStackPush(MyStack* obj, int x) {
	assert(obj);
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);//如果q1不為空，就往q1插入數(shù)據(jù)
	}
	else
	{
		QueuePush(&obj->q2, x);//這兒不需要知道q2是否為空，直接push
	}
}
 
int myStackPop(MyStack* obj) {
	assert(obj);
	Queue* emptyQ = &obj->q1; //默認(rèn)q1為空
	Queue* nonEmtpyQ = &obj->q2;//默認(rèn)q2不為空
	if (!QueueEmpty(&obj->q1))
	{
		emptyQ = &obj->q2; //若假設(shè)錯(cuò)誤，則q2為空
		nonEmtpyQ = &obj->q1;//此時(shí)q1就為空
	}
	while (QueueSize(nonEmtpyQ) > 1)
	{
		QueuePush(emptyQ, QueueFront(nonEmtpyQ)); //把非空的隊(duì)列數(shù)據(jù)導(dǎo)到空的隊(duì)列，直到只剩一個(gè)
		QueuePop(nonEmtpyQ); //此時(shí)把非空的隊(duì)頭數(shù)據(jù)給刪掉，方便后續(xù)導(dǎo)入數(shù)據(jù)
	}
	int top = QueueFront(nonEmtpyQ); //記錄此時(shí)的棧頂數(shù)據(jù)
	QueuePop(nonEmtpyQ); //刪除棧頂數(shù)據(jù)，使該隊(duì)列置空
	return top;
}
 
int myStackTop(MyStack* obj) {
	assert(obj);
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);//如果q1不為空，返回
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}
 
bool myStackEmpty(MyStack* obj) {
	assert(obj);
	//兩個(gè)隊(duì)列均為空，則為空
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
 
void myStackFree(MyStack* obj) {
	assert(obj);
	QueueDestory(&obj->q1); //釋放q1
	QueueDestory(&obj->q2); //釋放q2
	free(obj);
}

3、用棧實(shí)現(xiàn)隊(duì)列

鏈接直達(dá)：

用棧實(shí)現(xiàn)隊(duì)列

題目：

思路：

假設(shè)入棧的順序?yàn)? 2 3 4，那么根據(jù)題意，想要達(dá)到1 2 3 4的出棧順序以此實(shí)現(xiàn)隊(duì)列。

此題和上一道題正好相反，用棧實(shí)現(xiàn)隊(duì)列，上一道題中，我們需要把數(shù)據(jù)來(lái)回導(dǎo)，從而實(shí)現(xiàn)棧的后進(jìn)先出功能，但是此題就完全不需要來(lái)回導(dǎo)了，只需要導(dǎo)一次即可。

假設(shè)我們有兩個(gè)棧，分別命名為pushST和popST。并往棧pushST里頭入4個(gè)數(shù)據(jù)1 2 3 4，在出數(shù)據(jù)時(shí)根據(jù)棧的性質(zhì)只能拿到4，此時(shí)我們直接把4拿下來(lái)并導(dǎo)入棧popST里頭，并繼續(xù)把pushST棧里的數(shù)據(jù)導(dǎo)下來(lái)，直至棧pushST數(shù)據(jù)為空。此時(shí)popST數(shù)據(jù)即為 4 3 2 1，剛好反過(guò)來(lái)了。

根據(jù)隊(duì)列的先進(jìn)先出規(guī)則，進(jìn)1 2 3 4，出必然是1 2 3 4，而上文已經(jīng)知曉棧popST的數(shù)據(jù)為4 3 2 1，當(dāng)刪除數(shù)據(jù)時(shí)，會(huì)按照1 2 3 4 的順序逐個(gè)刪除。恰好利用棧的性質(zhì)實(shí)現(xiàn)了隊(duì)列的先進(jìn)先出功能。并只需導(dǎo)一次即可，無(wú)需多次。

代碼如下：

//創(chuàng)建棧結(jié)構(gòu)
typedef int STDataType;
typedef struct Stack
{
    STDataType* a; //存儲(chǔ)數(shù)據(jù)
    int top; //棧頂?shù)奈恢?
    int capacity; //容量
}ST;
//初始化棧
void StackInit(ST* ps);
//銷(xiāo)毀棧
void StackDestory(ST* ps);
//壓棧
void StackPush(ST* ps, STDataType x);
//出棧
void StackPop(ST* ps);
//判空
bool StackEmpty(ST* ps);
//訪問(wèn)棧頂數(shù)據(jù)
STDataType StackTop(ST* ps);
//有效元素個(gè)數(shù)
int StackSize(ST* ps);
 
//初始化棧
void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    ps->capacity = 0;
}
//銷(xiāo)毀棧
void StackDestory(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}
//壓棧
void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    //如果棧滿了，考慮擴(kuò)容
    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity; //檢測(cè)容量
        ps->a = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        if (ps->a == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->capacity = newcapacity; //更新容量
    }
    ps->a[ps->top] = x;//將數(shù)據(jù)壓進(jìn)去
    ps->top++;//棧頂上移
}
//出棧
void StackPop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}
//判空
bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0; //如果top為0，那么就為真，即返回
}
//訪問(wèn)棧頂數(shù)據(jù)
STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(ps->top > 0);
    return ps->a[ps->top - 1]; //top-1的位置才為棧頂?shù)脑?
}
//有效元素個(gè)數(shù)
int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}
 
/************創(chuàng)建好棧結(jié)構(gòu)，開(kāi)始正文************/
typedef struct {
    ST pushST; //插入數(shù)據(jù)的棧
    ST popST; //刪除數(shù)據(jù)的棧
} MyQueue;
 
 
MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); //申請(qǐng)隊(duì)列類(lèi)型
    assert(obj);
    StackInit(&obj->pushST);//初始化pushST
    StackInit(&obj->popST);//初始化popST
    return obj;
}
 
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushST, x);//不管有沒(méi)有數(shù)據(jù)，都插入
}
 
int myQueuePop(MyQueue* obj) {
    assert(obj);
    if (StackEmpty(&obj->popST)) //如果popST數(shù)據(jù)為空，要從pushST里導(dǎo)入數(shù)據(jù)才能刪除
    {
        while (!StackEmpty(&obj->pushST)) //pushST數(shù)據(jù)不為空，就一直向popST里導(dǎo)入數(shù)據(jù)
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST棧頂數(shù)據(jù)導(dǎo)到popST里
            StackPop(&obj->pushST);//導(dǎo)完后把pushST棧頂元素刪掉，方便后續(xù)繼續(xù)導(dǎo)
        }
    }
    int front = StackTop(&obj->popST); //記錄popST棧頂元素
    StackPop(&obj->popST);//刪除popST棧頂元素，實(shí)現(xiàn)隊(duì)列先進(jìn)先出
    return front; //返回棧頂數(shù)據(jù)
}
 
//取隊(duì)頭數(shù)據(jù)
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    //如果popST數(shù)據(jù)為空，要從pushST里導(dǎo)入數(shù)據(jù)才能取到隊(duì)頭數(shù)據(jù)
    if (StackEmpty(&obj->popST))
    {
        while (!StackEmpty(&obj->pushST)) //pushST數(shù)據(jù)不為空，就一直向popST里導(dǎo)入數(shù)據(jù)
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST棧頂數(shù)據(jù)導(dǎo)到popST里
            StackPop(&obj->pushST);//導(dǎo)完后把pushST棧頂元素刪掉，方便后續(xù)繼續(xù)導(dǎo)
        }
    }
    return StackTop(&obj->popST);//直接返回棧頂元素
}
 
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}
 
void myQueueFree(MyQueue* obj) {
    assert(obj);
    StackDestory(&obj->pushST);
    StackDestory(&obj->popST);
    free(obj);
}

4、設(shè)計(jì)循環(huán)隊(duì)列

鏈接直達(dá)：

設(shè)計(jì)循環(huán)隊(duì)列

題目：

思路：

此題可以用數(shù)組實(shí)現(xiàn)，也可以用鏈表實(shí)現(xiàn)，但其實(shí)是用數(shù)組更加方便些。

數(shù)組：

假設(shè)隊(duì)頭front和隊(duì)尾tail都指向第一個(gè)數(shù)據(jù)，在隊(duì)尾插入數(shù)據(jù)，tail隨著數(shù)據(jù)的插入跟著移動(dòng)，tail始終為最后一個(gè)數(shù)據(jù)的下一個(gè)位置。刪除數(shù)據(jù)只需要將隊(duì)頭front往后挪即可，不需要按照之前隊(duì)列的pop一樣刪完還挪動(dòng)數(shù)據(jù)，因?yàn)槭茄h(huán)鏈表，且數(shù)據(jù)是可以重復(fù)利用的。

這樣分析下來(lái)再加上畫(huà)圖看似沒(méi)有什么缺陷，但是存在兩個(gè)問(wèn)題？

什么情況下數(shù)組為空？
什么情況下數(shù)組滿了？

問(wèn)題1：

當(dāng)tail = front時(shí)數(shù)組為空，看似沒(méi)什么問(wèn)題，但相等又要分兩種情況。先畫(huà)個(gè)圖：

由上圖得知，在情況一下，數(shù)組里確實(shí)是一個(gè)數(shù)據(jù)也沒(méi)有，并且tail也是等于front的，滿足數(shù)組為空的條件，但是在情況二下，數(shù)組的數(shù)據(jù)全滿，此時(shí)的tail和front同樣是相等的，這里數(shù)組不為空了，而是全滿，由此可見(jiàn)，是存在問(wèn)題的。

解決方案：

這里我們可以多開(kāi)一個(gè)空間，不存放數(shù)據(jù)，只是用來(lái)分別數(shù)組為空或滿。原理如下：當(dāng)數(shù)組長(zhǎng)度為4時(shí)，也就是說(shuō)實(shí)際能存放3個(gè)有效數(shù)據(jù)，另外一個(gè)空間用來(lái)判斷空或滿，此時(shí)判斷空或滿的條件如下：

front == tail 時(shí)是空
tail 下一個(gè)位置是 front 時(shí)，就是滿

代碼如下：

typedef struct {
    int* a; //用數(shù)組模擬環(huán)形隊(duì)列
    int front;//隊(duì)頭
    int tail; //隊(duì)尾
    int k; //表示存的數(shù)據(jù)長(zhǎng)度為k
} MyCircularQueue;
 
bool myCircularQueueIsFull(MyCircularQueue* obj); //前置聲明
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//前置聲明
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//創(chuàng)建環(huán)形鏈表結(jié)構(gòu)
    assert(obj);
    obj->a = (int*)malloc(sizeof(int) * (k + 1));//多開(kāi)一個(gè)空間，便于后續(xù)區(qū)分空或滿
    obj->front = obj->tail = 0;
    obj->k = k; //隊(duì)列存儲(chǔ)有效數(shù)據(jù)長(zhǎng)度為k
    return obj;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj))
    {
        return false; //隊(duì)列已滿，不能插入數(shù)據(jù)
    }
    obj->a[obj->tail] = value; //賦值
    if (obj->tail == obj->k)
    {
        obj->tail = 0; //當(dāng)tail走到尾端
    }
    else
    {
        obj->tail++;
    }
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return false; //隊(duì)列為空，不能刪除
    }
    if (obj->front == obj->k)
    {
        obj->front = 0; //當(dāng)front走到尾端
    }
    else
    {
        obj->front++;
    }
    return true;
}
//取頭
int myCircularQueueFront(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1; //隊(duì)列為空，取不了
    }
    return obj->a[obj->front]; //返回隊(duì)頭
}
//取尾
int myCircularQueueRear(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj))
    {
        return -1; //隊(duì)列為空，取不了
    }
    if (obj->tail == 0)
    {
        return obj->a[obj->k]; //tail為0，隊(duì)尾在長(zhǎng)度的最后一個(gè)位置
    }
    else
    {
        return obj->a[obj->tail - 1];
    }
}
 
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail; //front==tail時(shí)為空
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if (obj->tail == obj->k && obj->front == 0)
    {
        return true; //當(dāng)tail尾端，front在頭端時(shí)也是滿
    }
    else
    {
        return obj->tail + 1 == obj->front; //一般情況，當(dāng)tail的下一個(gè)位置為front時(shí)為滿
    }
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

到此這篇關(guān)于C語(yǔ)言棧與隊(duì)列面試題詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言棧與隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: