您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“C語(yǔ)言棧與隊(duì)列面試題實(shí)例分析”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“C語(yǔ)言棧與隊(duì)列面試題實(shí)例分析”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來學(xué)習(xí)新知識(shí)吧。
鏈接直達(dá):
有效的括號(hào)
題目:
思路:
做題前,得先明確解題方案是啥,此題用棧的思想去解決是較為方便的,棧明確指出后進(jìn)先出。我們可以這樣設(shè)定:
遇到左括號(hào)“ ( ”、“ [ ”、“ { ”,入棧。
遇到右括號(hào)“ ) ”、“ ] ”、“ } ”,出棧,跟左括號(hào)進(jìn)行匹配,不匹配就報(bào)錯(cuò)。
上兩句話的意思就是說我去遍歷字符串,如果遇到左括號(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); //銷毀棧 void StackDestory(ST* ps); //壓棧 void StackPush(ST* ps, STDataType x); //出棧 void StackPop(ST* ps); //判空 bool StackEmpty(ST* ps); //訪問棧頂數(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; } //銷毀棧 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,那么就為真,即返回 } //訪問棧頂數(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)建好了棧開始實(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; //此處說明前面根本沒有左括號(hào),導(dǎo)致棧為空,直接返回false } char top = StackTop(&st); //獲取棧頂元素 StackPop(&st); //出棧頂元素,接下來進(jìn)行匹配 if ((*s == ']' && top != '[') || (*s == ')' && top != '(') || (*s == '}' && top != '{')) { StackDestory(&st); //返回前先銷毀,防止內(nèi)存泄漏 return false; //如果不匹配,直接返回false } else { //此時(shí)匹配,繼續(xù)比較,直到遍歷結(jié)束 ++s; } } } //棧為空,說明所有左括號(hào)都匹配 bool ret = StackEmpty(&st); StackDestory(&st); //返回前先銷毀,防止內(nèi)存泄漏 return ret; }
鏈接直達(dá):
用隊(duì)列實(shí)現(xiàn)棧
題目:
思路:
做題之前,再明確下兩個(gè)基本知識(shí)點(diǎn)
棧:后進(jìn)先出
隊(duì)列:先進(jìn)先出
此題要用先進(jìn)先出的隊(duì)列來實(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ì)列用來導(dǎo)數(shù)據(jù)。
代碼如下:
//創(chuàng)建隊(duì)列結(jié)構(gòu) typedef int QDataType; //方便后續(xù)更改存儲(chǔ)數(shù)據(jù)類型,本文以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); //銷毀隊(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; } //銷毀隊(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; //如果一開始沒有數(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),開始正文模擬實(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類型的棧 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); }
鏈接直達(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ù)來回導(dǎo),從而實(shí)現(xiàn)棧的后進(jìn)先出功能,但是此題就完全不需要來回導(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拿下來并導(dǎo)入棧popST里頭,并繼續(xù)把pushST棧里的數(shù)據(jù)導(dǎo)下來,直至棧pushST數(shù)據(jù)為空。此時(shí)popST數(shù)據(jù)即為 4 3 2 1,剛好反過來了。
根據(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)一次即可,無需多次。
代碼如下:
//創(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); //銷毀棧 void StackDestory(ST* ps); //壓棧 void StackPush(ST* ps, STDataType x); //出棧 void StackPop(ST* ps); //判空 bool StackEmpty(ST* ps); //訪問棧頂數(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; } //銷毀棧 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,那么就為真,即返回 } //訪問棧頂數(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),開始正文************/ typedef struct { ST pushST; //插入數(shù)據(jù)的棧 ST popST; //刪除數(shù)據(jù)的棧 } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); //申請(qǐng)隊(duì)列類型 assert(obj); StackInit(&obj->pushST);//初始化pushST StackInit(&obj->popST);//初始化popST return obj; } void myQueuePush(MyQueue* obj, int x) { assert(obj); StackPush(&obj->pushST, x);//不管有沒有數(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); }
鏈接直達(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ù)利用的。
這樣分析下來再加上畫圖看似沒有什么缺陷,但是存在兩個(gè)問題?
什么情況下數(shù)組為空?
什么情況下數(shù)組滿了?
問題1:
當(dāng)tail = front時(shí)數(shù)組為空,看似沒什么問題,但相等又要分兩種情況。先畫個(gè)圖:
由上圖得知,在情況一下,數(shù)組里確實(shí)是一個(gè)數(shù)據(jù)也沒有,并且tail也是等于front的,滿足數(shù)組為空的條件,但是在情況二下,數(shù)組的數(shù)據(jù)全滿,此時(shí)的tail和front同樣是相等的,這里數(shù)組不為空了,而是全滿,由此可見,是存在問題的。
解決方案:
這里我們可以多開一個(gè)空間,不存放數(shù)據(jù),只是用來分別數(shù)組為空或滿。原理如下:當(dāng)數(shù)組長(zhǎng)度為4時(shí),也就是說實(shí)際能存放3個(gè)有效數(shù)據(jù),另外一個(gè)空間用來判斷空或滿,此時(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));//多開一個(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); }
讀到這里,這篇“C語(yǔ)言棧與隊(duì)列面試題實(shí)例分析”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì),如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。