C語言棧與隊列面試題詳解
1、括號匹配問題
鏈接直達:
題目:

思路:
做題前,得先明確解題方案是啥,此題用棧的思想去解決是較為方便的,棧明確指出后進先出。我們可以這樣設(shè)定:
- 遇到左括號“ ( ”、“ [ ”、“ { ”,入棧。
- 遇到右括號“ ) ”、“ ] ”、“ } ”,出棧,跟左括號進行匹配,不匹配就報錯。
上兩句話的意思就是說我去遍歷字符串,如果遇到左括號,就入棧;遇到右括號,就出棧頂元素,并判斷這個右括號是否與棧頂括號相匹配,若不匹配則返回false,匹配繼續(xù)遍歷字符串,直到遍歷完全,遍歷后,檢查棧是否為空,若為空,則均匹配,返回true,反之false。

代碼如下:
//創(chuàng)建棧結(jié)構(gòu)
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; //此處說明前面根本沒有左括號,導(dǎo)致棧為空,直接返回false
}
char top = StackTop(&st); //獲取棧頂元素
StackPop(&st); //出棧頂元素,接下來進行匹配
if ((*s == ']' && top != '[')
|| (*s == ')' && top != '(')
|| (*s == '}' && top != '{'))
{
StackDestory(&st); //返回前先銷毀,防止內(nèi)存泄漏
return false; //如果不匹配,直接返回false
}
else
{
//此時匹配,繼續(xù)比較,直到遍歷結(jié)束
++s;
}
}
}
//棧為空,說明所有左括號都匹配
bool ret = StackEmpty(&st);
StackDestory(&st); //返回前先銷毀,防止內(nèi)存泄漏
return ret;
}2、用隊列實現(xiàn)棧
鏈接直達:
題目:

思路:
做題之前,再明確下兩個基本知識點
- 棧:后進先出
- 隊列:先進先出
此題要用先進先出的隊列來實現(xiàn)后進先出的棧,并模擬實現(xiàn)隊列的基本接口。
假設(shè)我們有一串數(shù)字,進入隊列A順序為1 2 3 4,此時再有一個隊列B,此時我們?nèi)£犃蠥的隊頭數(shù)據(jù),并將其導(dǎo)入隊列B,當隊列A出到只剩最后一個時,把隊列A給pop刪掉,此時隊列B就是1 2 3,間接性是實現(xiàn)了棧的功能,實現(xiàn)了后進先出的功能。當我們需要再入數(shù)據(jù)時,只需往不為空的隊列入即可。再出就像剛剛那樣。簡而言之兩句話:
- 入棧:push數(shù)據(jù)到不為空的隊列。
- 出棧:把不為空的隊列的數(shù)據(jù)前N-1導(dǎo)入另一個空隊列,最后剩下一個刪掉。
本質(zhì):保持一個隊列存儲數(shù)據(jù),另外一個隊列空著,要出棧時,空隊列用來導(dǎo)數(shù)據(jù)。

代碼如下:
//創(chuàng)建隊列結(jié)構(gòu)
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)建好隊列結(jié)構(gòu),開始正文模擬實現(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; //若假設(shè)錯誤,則q2為空
nonEmtpyQ = &obj->q1;//此時q1就為空
}
while (QueueSize(nonEmtpyQ) > 1)
{
QueuePush(emptyQ, QueueFront(nonEmtpyQ)); //把非空的隊列數(shù)據(jù)導(dǎo)到空的隊列,直到只剩一個
QueuePop(nonEmtpyQ); //此時把非空的隊頭數(shù)據(jù)給刪掉,方便后續(xù)導(dǎo)入數(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)隊列
鏈接直達:
題目:

思路:
假設(shè)入棧的順序為1 2 3 4,那么根據(jù)題意,想要達到1 2 3 4的出棧順序以此實現(xiàn)隊列。
此題和上一道題正好相反,用棧實現(xiàn)隊列,上一道題中,我們需要把數(shù)據(jù)來回導(dǎo),從而實現(xiàn)棧的后進先出功能,但是此題就完全不需要來回導(dǎo)了,只需要導(dǎo)一次即可。
假設(shè)我們有兩個棧,分別命名為pushST和popST。并往棧pushST里頭入4個數(shù)據(jù)1 2 3 4,在出數(shù)據(jù)時根據(jù)棧的性質(zhì)只能拿到4,此時我們直接把4拿下來并導(dǎo)入棧popST里頭,并繼續(xù)把pushST棧里的數(shù)據(jù)導(dǎo)下來,直至棧pushST數(shù)據(jù)為空。此時popST數(shù)據(jù)即為 4 3 2 1,剛好反過來了。
根據(jù)隊列的先進先出規(guī)則,進1 2 3 4,出必然是1 2 3 4,而上文已經(jīng)知曉棧popST的數(shù)據(jù)為4 3 2 1,當刪除數(shù)據(jù)時,會按照1 2 3 4 的順序逐個刪除。恰好利用棧的性質(zhì)實現(xiàn)了隊列的先進先出功能。并只需導(dǎo)一次即可,無需多次。

代碼如下:
//創(chuàng)建棧結(jié)構(gòu)
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)建好棧結(jié)構(gòu),開始正文************/
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里導(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棧頂元素,實現(xiàn)隊列先進先出
return front; //返回棧頂數(shù)據(jù)
}
//取隊頭數(shù)據(jù)
int myQueuePeek(MyQueue* obj) {
assert(obj);
//如果popST數(shù)據(jù)為空,要從pushST里導(dǎo)入數(shù)據(jù)才能取到隊頭數(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è)計循環(huán)隊列
鏈接直達:
題目:

思路:
此題可以用數(shù)組實現(xiàn),也可以用鏈表實現(xiàn),但其實是用數(shù)組更加方便些。
數(shù)組:
假設(shè)隊頭front和隊尾tail都指向第一個數(shù)據(jù),在隊尾插入數(shù)據(jù),tail隨著數(shù)據(jù)的插入跟著移動,tail始終為最后一個數(shù)據(jù)的下一個位置。刪除數(shù)據(jù)只需要將隊頭front往后挪即可,不需要按照之前隊列的pop一樣刪完還挪動數(shù)據(jù),因為是循環(huán)鏈表,且數(shù)據(jù)是可以重復(fù)利用的。

這樣分析下來再加上畫圖看似沒有什么缺陷,但是存在兩個問題?
- 什么情況下數(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)形鏈表結(jié)構(gòu)
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);
}到此這篇關(guān)于C語言棧與隊列面試題詳解的文章就介紹到這了,更多相關(guān)C語言 棧與隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
string中c_str(),data(),copy(p,n)函數(shù)的用法總結(jié)
以下是對string中c_str(),data(),copy(p,n)函數(shù)的用法進行了詳細的介紹,需要的朋友可以過來參考下2013-09-09
C語言之棧和堆(Stack && Heap)的優(yōu)缺點及其使用區(qū)別
本篇文章主要介紹了什么是棧(Stack) 、什么是堆( Heap),以及棧和堆的優(yōu)缺點,同時介紹了應(yīng)該什么時候使用堆和棧,有需要的朋友可以參考下2015-07-07
ubunt18.04LTS+vscode+anaconda3下的python+C++調(diào)試方法
這篇文章主要介紹了ubunt18.04LTS+vscode+anaconda3下的python+C++調(diào)試方法,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03
Visual Studio Community 2022(VS2022)安裝圖文方法
這篇文章主要介紹了Visual Studio Community 2022(VS2022)安裝方法,本文分步驟通過圖文并茂的形式給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-09-09

