<em>Mac</em>Book项目 2009年学校开始实施<em>Mac</em>Book项目,所有师生配备一本<em>Mac</em>Book,并同步更新了校园无线网络。学校每周进行电脑技术更新,每月发送技术支持资料,极大改变了教学及学习方式。因此2011
2021-06-01 09:32:01
C語言棧與佇列面試題詳解
2022-04-11 13:02:33
1、括號匹配問題
連結直達：
題目：
思路：
做題前，得先明確解題方案是啥，此題用棧的思想去解決是較為方便的，棧明確指出後進先出。我們可以這樣設定：
- 遇到左括號“ ( ”、“ [ ”、“ { ”，入棧。
- 遇到右括號“ ) ”、“ ] ”、“ } ”，出棧，跟左括號進行匹配，不匹配就報錯。
上兩句話的意思就是說我去遍歷字串，如果遇到左括號，就入棧；遇到右括號，就出棧頂元素，並判斷這個右括號是否與棧頂括號相匹配，若不匹配則返回false，匹配繼續遍歷字串，直到遍歷完全，遍歷後，檢查棧是否為空，若為空，則均匹配，返回true，反之false。
程式碼如下：
//建立棧結構
typedef char 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);
//判空
bool StackEmpty(ST* ps);
//存取棧頂資料
STDataType StackTop(ST* ps);
//有效元素個數
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 failn");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//將資料壓進去
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，那麼就為真，即返回
}
//存取棧頂資料
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂的元素
}
//有效元素個數
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//建立好了棧開始實現
bool isValid(char* s) {
ST st;//先建立一個棧
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
{
//此時匹配，繼續比較，直到遍歷結束
++s;
}
}
}
//棧為空，說明所有左括號都匹配
bool ret = StackEmpty(&st);
StackDestory(&st); //返回前先銷燬，防止記憶體漏失
return ret;
}2、用佇列實現棧
連結直達：
題目：
思路：
做題之前，再明確下兩個基本知識點
- 棧：後進先出
- 佇列：先進先出
此題要用先進先出的佇列來實現後進先出的棧，並模擬實現佇列的基本介面。
假設我們有一串數位，進入佇列A順序為1 2 3 4，此時再有一個佇列B，此時我們取佇列A的隊頭資料，並將其匯入佇列B，當佇列A出到只剩最後一個時，把佇列A給pop刪掉，此時佇列B就是1 2 3，間接性是實現了棧的功能，實現了後進先出的功能。當我們需要再入資料時，只需往不為空的佇列入即可。再出就像剛剛那樣。簡而言之兩句話：
- 入棧：push資料到不為空的佇列。
- 出棧：把不為空的佇列的資料前N-1匯入另一個空佇列，最後剩下一個刪掉。
本質：保持一個佇列儲存資料，另外一個佇列空著，要出棧時，空佇列用來導資料。
程式碼如下：
//建立佇列結構
typedef int QDataType; //方便後續更改儲存資料型別，本文以int為例
//建立佇列節點
typedef struct QueueNode
{
QDataType data; //儲存資料
struct QueueNode* next; //記錄下一個節點
}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);
//獲取有效元素個數
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);
//建立一個新節點儲存資料
QNode* newnode = (QNode*)malloc(sizeof(QNode));
//暴力檢測newnode，因為malloc的都要檢測
assert(newnode);
newnode->next = NULL;
newnode->data = x;
//如果一開始沒有資料，為空的情況
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的下一個節點
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
//判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
//獲取有效元素個數
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;
}
/**************建立好佇列結構，開始正文模擬實現棧**************/
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插入資料
}
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)); //把非空的佇列資料導到空的佇列，直到只剩一個
QueuePop(nonEmtpyQ); //此時把非空的隊頭資料給刪掉，方便後續匯入資料
}
int top = QueueFront(nonEmtpyQ); //記錄此時的棧頂資料
QueuePop(nonEmtpyQ); //刪除棧頂資料，使該佇列置空
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、用棧實現佇列
連結直達：
題目：
思路：
假設入棧的順序為1 2 3 4，那麼根據題意，想要達到1 2 3 4的出棧順序以此實現佇列。
此題和上一道題正好相反，用棧實現佇列，上一道題中，我們需要把資料來回導，從而實現棧的後進先出功能，但是此題就完全不需要來回導了，只需要導一次即可。
假設我們有兩個棧，分別命名為pushST和popST。並往棧pushST裡頭入4個資料1 2 3 4，在出資料時根據棧的性質只能拿到4，此時我們直接把4拿下來並匯入棧popST裡頭，並繼續把pushST棧裡的資料導下來，直至棧pushST資料為空。此時popST資料即為 4 3 2 1，剛好反過來了。
根據佇列的先進先出規則，進1 2 3 4，出必然是1 2 3 4，而上文已經知曉棧popST的資料為4 3 2 1，當刪除資料時，會按照1 2 3 4 的順序逐個刪除。恰好利用棧的性質實現了佇列的先進先出功能。並只需導一次即可，無需多次。
程式碼如下：
//建立棧結構
typedef 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);
//判空
bool StackEmpty(ST* ps);
//存取棧頂資料
STDataType StackTop(ST* ps);
//有效元素個數
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 failn");
exit(-1);
}
ps->capacity = newcapacity; //更新容量
}
ps->a[ps->top] = x;//將資料壓進去
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，那麼就為真，即返回
}
//存取棧頂資料
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1]; //top-1的位置才為棧頂的元素
}
//有效元素個數
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
/************建立好棧結構，開始正文************/
typedef struct {
ST pushST; //插入資料的棧
ST popST; //刪除資料的棧
} 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);//不管有沒有資料，都插入
}
int myQueuePop(MyQueue* obj) {
assert(obj);
if (StackEmpty(&obj->popST)) //如果popST資料為空，要從pushST裡匯入資料才能刪除
{
while (!StackEmpty(&obj->pushST)) //pushST資料不為空，就一直向popST裡匯入資料
{
StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST棧頂資料導到popST裡
StackPop(&obj->pushST);//導完後把pushST棧頂元素刪掉，方便後續繼續導
}
}
int front = StackTop(&obj->popST); //記錄popST棧頂元素
StackPop(&obj->popST);//刪除popST棧頂元素，實現佇列先進先出
return front; //返回棧頂資料
}
//取隊頭資料
int myQueuePeek(MyQueue* obj) {
assert(obj);
//如果popST資料為空，要從pushST裡匯入資料才能取到隊頭資料
if (StackEmpty(&obj->popST))
{
while (!StackEmpty(&obj->pushST)) //pushST資料不為空，就一直向popST裡匯入資料
{
StackPush(&obj->popST, StackTop(&obj->pushST));//把pushST棧頂資料導到popST裡
StackPop(&obj->pushST);//導完後把pushST棧頂元素刪掉，方便後續繼續導
}
}
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、設計迴圈佇列
連結直達：
題目：
思路：
此題可以用陣列實現，也可以用連結串列實現，但其實是用陣列更加方便些。
陣列：
假設隊頭front和隊尾tail都指向第一個資料，在隊尾插入資料，tail隨著資料的插入跟著移動，tail始終為最後一個資料的下一個位置。刪除資料只需要將隊頭front往後挪即可，不需要按照之前佇列的pop一樣刪完還挪動資料，因為是迴圈連結串列，且資料是可以重複利用的。
這樣分析下來再加上畫圖看似沒有什麼缺陷，但是存在兩個問題？
- 什麼情況下陣列為空？
- 什麼情況下陣列滿了？
問題1：
當tail = front時陣列為空，看似沒什麼問題，但相等又要分兩種情況。先畫個圖：
由上圖得知，在情況一下，陣列裡確實是一個資料也沒有，並且tail也是等於front的，滿足陣列為空的條件，但是在情況二下，陣列的資料全滿，此時的tail和front同樣是相等的，這裡陣列不為空了，而是全滿，由此可見，是存在問題的。
解決方案：
這裡我們可以多開一個空間，不存放資料，只是用來分別陣列為空或滿。原理如下：當陣列長度為4時，也就是說實際能存放3個有效資料，另外一個空間用來判斷空或滿，此時判斷空或滿的條件如下：
- front == tail 時是空
- tail 下一個位置是 front 時，就是滿
程式碼如下：
typedef struct {
int* a; //用陣列模擬環形佇列
int front;//隊頭
int tail; //隊尾
int k; //表示存的資料長度為k
} MyCircularQueue;
bool myCircularQueueIsFull(MyCircularQueue* obj); //前置宣告
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//前置宣告
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));//建立環形連結串列結構
assert(obj);
obj->a = (int*)malloc(sizeof(int) * (k + 1));//多開一個空間，便於後續區分空或滿
obj->front = obj->tail = 0;
obj->k = k; //佇列儲存有效資料長度為k
return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if (myCircularQueueIsFull(obj))
{
return false; //佇列已滿，不能插入資料
}
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語言 棧與佇列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！
相關文章
-
黑科技的輕簡出行，告別「電量焦慮症」：Anker氮化鎵超能充系列
综合看Anker超能充系列的性价比很高，并且与不仅和iPhone12/苹果<em>Mac</em>Book很配，而且适合多设备充电需求的日常使用或差旅场景，不管是安卓还是Switch同样也能用得上它，希望这次分享能给准备购入充电器的小伙伴们有所
2021-06-01 09:31:42
-
吳亦凡廠牌首秀，L4WUDU居然忘詞了，Rapper和明星比還是有差距！
除了L4WUDU与吴亦凡已经多次共事，成为了明面上的厂牌成员，吴亦凡还曾带领20XXCLUB全队参加2020年的一场音乐节，这也是20XXCLUB首次全员合照，王嗣尧Turbo、陈彦希Regi、<em>Mac</em> Ova Seas、林渝植等人全部出场。然而让
2021-06-01 09:31:34
-
IPFS、Chia、Bzz和ICP挖礦該怎麼選？哪一個更有優勢？
目前应用IPFS的机构：1 谷歌<em>浏览器</em>支持IPFS分布式协议 2 万维网 (历史档案博物馆)数据库 3 火狐<em>浏览器</em>支持 IPFS分布式协议 4 EOS 等数字货币数据存储 5 美国国会图书馆，历史资料永久保存在 IPFS 6 加
2021-06-01 09:31:24
-
有哪些事是買了雪佛蘭後才知道的？美事偷著樂，開拓者車主隨聊
开拓者的车机是兼容苹果和<em>安卓</em>，虽然我不怎么用，但确实兼顾了我家人的很多需求：副驾的门板还配有解锁开关，有的时候老婆开车，下车的时候偶尔会忘记解锁，我在副驾驶可以自己开门：第二排设计很好，不仅配置了一个很大的
2021-06-01 09:30:48
-
iPhone12在618最新定價，跌價幅度超過1400元，還等iPhone13嗎？
不仅是<em>安卓</em>手机，苹果手机的降价力度也是前所未有了，iPhone12也“跳水价”了，发布价是6799元，如今已经跌至5308元，降价幅度超过1400元，最新定价确认了。iPhone12是苹果首款5G手机，同时也是全球首款5nm芯片的智能机，它
2021-06-01 09:30:45