溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“C語言棧與隊列面試題實例分析”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C語言棧與隊列面試題實例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
鏈接直達：
有效的括號
題目：
思路：
做題前，得先明確解題方案是啥，此題用棧的思想去解決是較為方便的，棧明確指出后進先出。我們可以這樣設定：
遇到左括號“ ( ”、“ [ ”、“ { ”，入棧。
遇到右括號“ ) ”、“ ] ”、“ } ”，出棧，跟左括號進行匹配，不匹配就報錯。
上兩句話的意思就是說我去遍歷字符串，如果遇到左括號，就入棧；遇到右括號，就出棧頂元素，并判斷這個右括號是否與棧頂括號相匹配，若不匹配則返回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 fail\n");
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;
}鏈接直達：
用隊列實現棧
題目：
思路：
做題之前，再明確下兩個基本知識點
棧：后進先出
隊列：先進先出
此題要用先進先出的隊列來實現后進先出的棧，并模擬實現隊列的基本接口。
假設我們有一串數字，進入隊列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);
}鏈接直達：
用棧實現隊列
題目：
思路：
假設入棧的順序為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 fail\n");
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);
}鏈接直達：
設計循環隊列
題目：
思路：
此題可以用數組實現，也可以用鏈表實現，但其實是用數組更加方便些。
數組：
假設隊頭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語言棧與隊列面試題實例分析”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
