C語言棧與隊列面試題詳解
1、括號匹配問題
鏈接直達:
題目:
思路:
做題前,得先明確解題方案是啥,此題用棧的思想去解決是較為方便的,棧明確指出后進先出。我們可以這樣設定:
- 遇到左括號“ ( ”、“ [ ”、“ { ”,入棧。
- 遇到右括號“ ) ”、“ ] ”、“ } ”,出棧,跟左括號進行匹配,不匹配就報錯。
上兩句話的意思就是說我去遍歷字符串,如果遇到左括號,就入棧;遇到右括號,就出棧頂元素,并判斷這個右括號是否與棧頂括號相匹配,若不匹配則返回false,匹配繼續(xù)遍歷字符串,直到遍歷完全,遍歷后,檢查棧是否為空,若為空,則均匹配,返回true,反之false。
代碼如下:
//創(chuàng)建棧結構 typedef char STDataType; typedef struct Stack { STDataType* a; //存儲數(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); //有效元素個數(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); //如果棧滿了,考慮擴容 if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //檢測容量 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ù)壓進去 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ù)脑? } //有效元素個數(shù) int StackSize(ST* ps) { assert(ps); return ps->top; } //創(chuàng)建好了棧開始實現(xiàn) bool isValid(char* s) { ST st;//先創(chuàng)建一個棧 StackInit(&st);//初始化棧 while (*s) { if (*s == '[' || *s == '(' || *s == '{') { StackPush(&st, *s); //如果是左括號就入棧 ++s; } else { if (StackEmpty(&st)) { return false; //此處說明前面根本沒有左括號,導致棧為空,直接返回false } char top = StackTop(&st); //獲取棧頂元素 StackPop(&st); //出棧頂元素,接下來進行匹配 if ((*s == ']' && top != '[') || (*s == ')' && top != '(') || (*s == '}' && top != '{')) { StackDestory(&st); //返回前先銷毀,防止內存泄漏 return false; //如果不匹配,直接返回false } else { //此時匹配,繼續(xù)比較,直到遍歷結束 ++s; } } } //棧為空,說明所有左括號都匹配 bool ret = StackEmpty(&st); StackDestory(&st); //返回前先銷毀,防止內存泄漏 return ret; }
2、用隊列實現(xiàn)棧
鏈接直達:
題目:
思路:
做題之前,再明確下兩個基本知識點
- 棧:后進先出
- 隊列:先進先出
此題要用先進先出的隊列來實現(xiàn)后進先出的棧,并模擬實現(xiàn)隊列的基本接口。
假設我們有一串數(shù)字,進入隊列A順序為1 2 3 4,此時再有一個隊列B,此時我們取隊列A的隊頭數(shù)據(jù),并將其導入隊列B,當隊列A出到只剩最后一個時,把隊列A給pop刪掉,此時隊列B就是1 2 3,間接性是實現(xiàn)了棧的功能,實現(xiàn)了后進先出的功能。當我們需要再入數(shù)據(jù)時,只需往不為空的隊列入即可。再出就像剛剛那樣。簡而言之兩句話:
- 入棧:push數(shù)據(jù)到不為空的隊列。
- 出棧:把不為空的隊列的數(shù)據(jù)前N-1導入另一個空隊列,最后剩下一個刪掉。
本質:保持一個隊列存儲數(shù)據(jù),另外一個隊列空著,要出棧時,空隊列用來導數(shù)據(jù)。
代碼如下:
//創(chuàng)建隊列結構 typedef int QDataType; //方便后續(xù)更改存儲數(shù)據(jù)類型,本文以int為例 //創(chuàng)建隊列節(jié)點 typedef struct QueueNode { QDataType data; //存儲數(shù)據(jù) struct QueueNode* next; //記錄下一個節(jié)點 }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); //判空 bool QueueEmpty(Queue* pq); //獲取有效元素個數(shù) size_t QueueSize(Queue* pq); //獲取隊頭元素 QDataType QueueFront(Queue* pq); //獲取隊尾元素 QDataType QueueBack(Queue* pq); //定義: //初始化隊列 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); //創(chuàng)建一個新節(jié)點保存數(shù)據(jù) QNode* newnode = (QNode*)malloc(sizeof(QNode)); //暴力檢測newnode,因為malloc的都要檢測 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; } } //出隊列 void QueuePop(Queue* pq) { assert(pq); assert(pq->head && pq->tail); //tail和head均不能為空 //特殊:當刪到head=tail的位置時 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } //一般情況 else { //保存head的下一個節(jié)點 QNode* next = pq->head->next; free(pq->head); pq->head = next; } } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } //獲取有效元素個數(shù) size_t QueueSize(Queue* pq) { assert(pq); QNode* cur = pq->head; size_t size = 0; while (cur) { size++; cur = cur->next; } return size; } //獲取隊頭元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); //頭部不能為空 return pq->head->data; } //獲取隊尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->tail); //尾部不能為空 return pq->tail->data; } /**************創(chuàng)建好隊列結構,開始正文模擬實現(xiàn)棧**************/ typedef struct { Queue q1; //隊列q1 Queue q2; //隊列q2 } MyStack; MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); //申請一個MyStack類型的棧 assert(pst); QueueInit(&pst->q1);//初始化隊列1 QueueInit(&pst->q2);//初始化隊列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; //默認q1為空 Queue* nonEmtpyQ = &obj->q2;//默認q2不為空 if (!QueueEmpty(&obj->q1)) { emptyQ = &obj->q2; //若假設錯誤,則q2為空 nonEmtpyQ = &obj->q1;//此時q1就為空 } while (QueueSize(nonEmtpyQ) > 1) { QueuePush(emptyQ, QueueFront(nonEmtpyQ)); //把非空的隊列數(shù)據(jù)導到空的隊列,直到只剩一個 QueuePop(nonEmtpyQ); //此時把非空的隊頭數(shù)據(jù)給刪掉,方便后續(xù)導入數(shù)據(jù) } int top = QueueFront(nonEmtpyQ); //記錄此時的棧頂數(shù)據(jù) QueuePop(nonEmtpyQ); //刪除棧頂數(shù)據(jù),使該隊列置空 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); //兩個隊列均為空,則為空 return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { assert(obj); QueueDestory(&obj->q1); //釋放q1 QueueDestory(&obj->q2); //釋放q2 free(obj); }
3、用棧實現(xiàn)隊列
鏈接直達:
題目:
思路:
假設入棧的順序為1 2 3 4,那么根據(jù)題意,想要達到1 2 3 4的出棧順序以此實現(xiàn)隊列。
此題和上一道題正好相反,用棧實現(xiàn)隊列,上一道題中,我們需要把數(shù)據(jù)來回導,從而實現(xiàn)棧的后進先出功能,但是此題就完全不需要來回導了,只需要導一次即可。
假設我們有兩個棧,分別命名為pushST和popST。并往棧pushST里頭入4個數(shù)據(jù)1 2 3 4,在出數(shù)據(jù)時根據(jù)棧的性質只能拿到4,此時我們直接把4拿下來并導入棧popST里頭,并繼續(xù)把pushST棧里的數(shù)據(jù)導下來,直至棧pushST數(shù)據(jù)為空。此時popST數(shù)據(jù)即為 4 3 2 1,剛好反過來了。
根據(jù)隊列的先進先出規(guī)則,進1 2 3 4,出必然是1 2 3 4,而上文已經知曉棧popST的數(shù)據(jù)為4 3 2 1,當刪除數(shù)據(jù)時,會按照1 2 3 4 的順序逐個刪除。恰好利用棧的性質實現(xiàn)了隊列的先進先出功能。并只需導一次即可,無需多次。
代碼如下:
//創(chuàng)建棧結構 typedef int STDataType; typedef struct Stack { STDataType* a; //存儲數(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); //有效元素個數(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); //如果棧滿了,考慮擴容 if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity; //檢測容量 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ù)壓進去 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ù)脑? } //有效元素個數(shù) int StackSize(ST* ps) { assert(ps); return ps->top; } /************創(chuàng)建好棧結構,開始正文************/ typedef struct { ST pushST; //插入數(shù)據(jù)的棧 ST popST; //刪除數(shù)據(jù)的棧 } MyQueue; MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); //申請隊列類型 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里導入數(shù)據(jù)才能刪除 { while (!StackEmpty(&obj->pushST)) //pushST數(shù)據(jù)不為空,就一直向popST里導入數(shù)據(jù) { StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST棧頂數(shù)據(jù)導到popST里 StackPop(&obj->pushST);//導完后把pushST棧頂元素刪掉,方便后續(xù)繼續(xù)導 } } int front = StackTop(&obj->popST); //記錄popST棧頂元素 StackPop(&obj->popST);//刪除popST棧頂元素,實現(xiàn)隊列先進先出 return front; //返回棧頂數(shù)據(jù) } //取隊頭數(shù)據(jù) int myQueuePeek(MyQueue* obj) { assert(obj); //如果popST數(shù)據(jù)為空,要從pushST里導入數(shù)據(jù)才能取到隊頭數(shù)據(jù) if (StackEmpty(&obj->popST)) { while (!StackEmpty(&obj->pushST)) //pushST數(shù)據(jù)不為空,就一直向popST里導入數(shù)據(jù) { StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST棧頂數(shù)據(jù)導到popST里 StackPop(&obj->pushST);//導完后把pushST棧頂元素刪掉,方便后續(xù)繼續(xù)導 } } 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、設計循環(huán)隊列
鏈接直達:
題目:
思路:
此題可以用數(shù)組實現(xiàn),也可以用鏈表實現(xiàn),但其實是用數(shù)組更加方便些。
數(shù)組:
假設隊頭front和隊尾tail都指向第一個數(shù)據(jù),在隊尾插入數(shù)據(jù),tail隨著數(shù)據(jù)的插入跟著移動,tail始終為最后一個數(shù)據(jù)的下一個位置。刪除數(shù)據(jù)只需要將隊頭front往后挪即可,不需要按照之前隊列的pop一樣刪完還挪動數(shù)據(jù),因為是循環(huán)鏈表,且數(shù)據(jù)是可以重復利用的。
這樣分析下來再加上畫圖看似沒有什么缺陷,但是存在兩個問題?
- 什么情況下數(shù)組為空?
- 什么情況下數(shù)組滿了?
問題1:
當tail = front時數(shù)組為空,看似沒什么問題,但相等又要分兩種情況。先畫個圖:
由上圖得知,在情況一下,數(shù)組里確實是一個數(shù)據(jù)也沒有,并且tail也是等于front的,滿足數(shù)組為空的條件,但是在情況二下,數(shù)組的數(shù)據(jù)全滿,此時的tail和front同樣是相等的,這里數(shù)組不為空了,而是全滿,由此可見,是存在問題的。
解決方案:
這里我們可以多開一個空間,不存放數(shù)據(jù),只是用來分別數(shù)組為空或滿。原理如下:當數(shù)組長度為4時,也就是說實際能存放3個有效數(shù)據(jù),另外一個空間用來判斷空或滿,此時判斷空或滿的條件如下:
- front == tail 時是空
- tail 下一個位置是 front 時,就是滿
代碼如下:
typedef struct { int* a; //用數(shù)組模擬環(huán)形隊列 int front;//隊頭 int tail; //隊尾 int k; //表示存的數(shù)據(jù)長度為k } MyCircularQueue; bool myCircularQueueIsFull(MyCircularQueue* obj); //前置聲明 bool myCircularQueueIsEmpty(MyCircularQueue* obj);//前置聲明 MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//創(chuàng)建環(huán)形鏈表結構 assert(obj); obj->a = (int*)malloc(sizeof(int) * (k + 1));//多開一個空間,便于后續(xù)區(qū)分空或滿 obj->front = obj->tail = 0; obj->k = k; //隊列存儲有效數(shù)據(jù)長度為k return obj; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (myCircularQueueIsFull(obj)) { return false; //隊列已滿,不能插入數(shù)據(jù) } obj->a[obj->tail] = value; //賦值 if (obj->tail == obj->k) { obj->tail = 0; //當tail走到尾端 } else { obj->tail++; } return true; } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) { return false; //隊列為空,不能刪除 } if (obj->front == obj->k) { obj->front = 0; //當front走到尾端 } else { obj->front++; } return true; } //取頭 int myCircularQueueFront(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) { return -1; //隊列為空,取不了 } return obj->a[obj->front]; //返回隊頭 } //取尾 int myCircularQueueRear(MyCircularQueue* obj) { if (myCircularQueueIsEmpty(obj)) { return -1; //隊列為空,取不了 } if (obj->tail == 0) { return obj->a[obj->k]; //tail為0,隊尾在長度的最后一個位置 } else { return obj->a[obj->tail - 1]; } } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->front == obj->tail; //front==tail時為空 } bool myCircularQueueIsFull(MyCircularQueue* obj) { if (obj->tail == obj->k && obj->front == 0) { return true; //當tail尾端,front在頭端時也是滿 } else { return obj->tail + 1 == obj->front; //一般情況,當tail的下一個位置為front時為滿 } } void myCircularQueueFree(MyCircularQueue* obj) { free(obj->a); free(obj); }
到此這篇關于C語言棧與隊列面試題詳解的文章就介紹到這了,更多相關C語言 棧與隊列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
string中c_str(),data(),copy(p,n)函數(shù)的用法總結
以下是對string中c_str(),data(),copy(p,n)函數(shù)的用法進行了詳細的介紹,需要的朋友可以過來參考下2013-09-09C語言之棧和堆(Stack && Heap)的優(yōu)缺點及其使用區(qū)別
本篇文章主要介紹了什么是棧(Stack) 、什么是堆( Heap),以及棧和堆的優(yōu)缺點,同時介紹了應該什么時候使用堆和棧,有需要的朋友可以參考下2015-07-07ubunt18.04LTS+vscode+anaconda3下的python+C++調試方法
這篇文章主要介紹了ubunt18.04LTS+vscode+anaconda3下的python+C++調試方法,本文給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03Visual Studio Community 2022(VS2022)安裝圖文方法
這篇文章主要介紹了Visual Studio Community 2022(VS2022)安裝方法,本文分步驟通過圖文并茂的形式給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-09-09