題目

用隊列實現(xiàn)棧

題目要求

題目鏈接

示例

解答

方法一、

使用兩個隊列來實現(xiàn)棧。

實現(xiàn)思路

題目說了使用兩個隊列來實現(xiàn)棧的操作，我們知道棧結(jié)構(gòu)的特點是元素后進先出，而隊列的特點是先進先出。即棧的操作是尾插尾刪，而隊列的操作是尾插頭刪，所以我們可以將一個隊列中按順序?qū)?shù)據(jù)入隊來模仿元素進棧。

當(dāng)元素出棧時，我們可以將有元素的隊列q1的數(shù)據(jù)依次出隊，并且依次進入到另一個空的隊列q2，當(dāng)隊列q1中只有一個元素時，我們停止將這個元素入隊q2，因為這個元素就相當(dāng)于棧頂元素。

此時我們將這個元素的空間釋放即完成了棧中元素的出棧操作，并且此時隊列q1也為空隊列了，當(dāng)有元素需要入棧時，將元素進入到不是空隊列的隊列中即可，當(dāng)再需要出棧時，還重復(fù)上面的操作，將隊列中的元素都進入到另一個隊列，然后將最后一個結(jié)點釋放即可。

時間復(fù)雜度和空間復(fù)雜度

時間復(fù)雜度：出棧為O(N)，其余為O(1)
空間復(fù)雜度：O(N)

代碼

include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDataType;
//隊列的結(jié)點設(shè)計
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//創(chuàng)建一個Queue結(jié)構(gòu)體變量，就相當(dāng)于創(chuàng)建了一個隊列，該結(jié)構(gòu)體變量中存的有該隊列的頭結(jié)點地址，尾結(jié)點地址
//所以當(dāng)有該結(jié)構(gòu)體變量的地址時，可以通過該地址改變隊列的頭結(jié)點地址和尾結(jié)點地址，即改變head指針和tail指針。
typedef struct Queue
{QNode* head;QNode* tail;int size;  //用來記錄隊列長度
}Queue;//隊列初始化
void QueueInit(Queue* pq);//判斷隊列是否為空
bool QueueEmpty(Queue* pq);//隊列的銷毀
void QueueDestroy(Queue* pq);//元素的入棧
void QueuePush(Queue* pq, QDataType x);//元素的出棧
void QueuePop(Queue* pq);//返回隊頭結(jié)點的數(shù)據(jù)
QDataType QueueFront(Queue* pq);//返回隊尾結(jié)點的數(shù)據(jù)
QDataType QueueBack(Queue* pq);//返回隊列的長度
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;
}bool QueueEmpty(Queue* pq)
{assert(pq);/*if (pq->head == NULL){return true;}else{return false;}*/return pq->head == NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc fail");exit(-1);}newNode->data = x;newNode->next = NULL;if (pq->head == NULL){pq->head = newNode;pq->tail = newNode;}else{pq->tail->next = newNode;pq->tail = newNode;}
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//當(dāng)隊列中只有一個結(jié)點時，該結(jié)點出隊后隊列就為空了//所以需要將隊列的頭指針和尾指針都置為NULLif (pq->head->next == NULL){free(pq->head);pq->head = NULL;//雖然按照下面的處理pq->head也會為NULL，//但tail指針還指向已經(jīng)釋放空間的最后一個結(jié)點的地址，所以此時tail為野指針，所以需要特別處理，將tail置為NULLpq->tail = NULL;}else{QNode* del = pq->head;pq->head = pq->head->next;free(del);}}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* curr = pq->head;while (curr != NULL){size++;curr = curr->next;}return size;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* curr = pq->head;while (curr){QNode* next = curr->next;free(curr);curr = next;}pq->head = NULL;pq->tail = NULL;//在這里面將pq置為空沒用，因為pq只是臨時創(chuàng)建的一個Queue*類型的結(jié)構(gòu)體指針//pq里面存的是Queue結(jié)構(gòu)體變量的地址，在函數(shù)里面將pq置為NULL對外面沒有影響。//只是讓pq指向不了這個結(jié)構(gòu)體變量了，但是這個結(jié)構(gòu)體變量還存在，
}//該結(jié)構(gòu)體采用了匿名結(jié)構(gòu)體，然后將這個匿名結(jié)構(gòu)體重命名為MyStack
typedef struct {//創(chuàng)建兩個隊列Queue q1;Queue q2;
} MyStack;
bool myStackEmpty(MyStack* obj);MyStack* myStackCreate() {//此時MyStack就相當(dāng)于一個棧，當(dāng)我們要使用一個棧時，先申請空間創(chuàng)建一個MyStack的結(jié)點MyStack* stack = (MyStack*)malloc(sizeof(MyStack));//然后我們初始化兩個隊列，因為我們定義的QueueInit函數(shù)的形參為Queue*類型的指針，//而MyStack結(jié)構(gòu)體中定義的成員變量q1和q2為Queue類型，所以要將q1和q2的地址傳過去。//如果傳的是stack->q1的話，那么函數(shù)會臨時創(chuàng)建一個Queue類型的變量tmp，然后函數(shù)里面tmp改變//但是stack結(jié)構(gòu)體里面的q1不會改變。QueueInit(&(stack->q1));QueueInit(&(stack->q2));return stack;
}void myStackPush(MyStack* obj, int x) {assert(obj);//先設(shè)q1為空隊列，q2為非空隊列Queue* emptyQ = &(obj->q1);Queue* noemptyQ = &(obj->q2);//如果q1非空，說明設(shè)錯了，則改正。if(!QueueEmpty(&(obj->q1))){emptyQ = &(obj->q2);noemptyQ = &(obj->q1);}QueuePush(noemptyQ,x);
}int myStackPop(MyStack* obj) {//先判斷棧是否為空，如果為空則不可以出棧assert(obj);assert(!myStackEmpty(obj));//先設(shè)q1為空隊列，q2為非空隊列Queue* emptyQ = &(obj->q1);Queue* noemptyQ = &(obj->q2);//如果q1非空，說明設(shè)錯了，則改正。if(!QueueEmpty(&(obj->q1))){emptyQ = &(obj->q2);noemptyQ = &(obj->q1);}//將非空隊列的除了最后一個元素外的元素都進入到空隊列中，while(QueueSize(noemptyQ)>1){QueuePush(emptyQ,QueueFront(noemptyQ));QueuePop(noemptyQ);}//將非空隊列中最后一個元素返回int top = QueueFront(noemptyQ);//將隊列中最后一個元素出隊。此時非空隊列變?yōu)榭贞犃?/span>QueuePop(noemptyQ);//返回棧頂元素的數(shù)據(jù)return top;
}int myStackTop(MyStack* obj) {assert(obj);//返回棧頂元素就相當(dāng)于返回非空隊列的隊尾結(jié)點的元素。//判斷棧非空assert(!myStackEmpty(obj));if(!QueueEmpty(&(obj->q1))){return QueueBack(&(obj->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);//先釋放兩個隊列的空間，然后再釋放obj的空間QueueDestroy(&(obj->q1));QueueDestroy(&(obj->q2));free(obj);
}

方法二、

使用兩個隊列來實現(xiàn)棧。

實現(xiàn)思路

第一種方法是入棧的元素直接入隊，當(dāng)出棧時才進行轉(zhuǎn)換，將棧頂元素出棧。而這個方法是在入棧時就將隊列中的元素排好出棧的順序。
當(dāng)元素入棧時，將元素進入一個空隊列中，然后將另一個非空隊列noempty的元素都進入空隊列empty中，這樣空隊列empty中元素的出隊順序剛好和在棧中出棧的順序一致。


當(dāng)再有元素入棧時，重復(fù)上述操作即可。

時間復(fù)雜度和空間復(fù)雜度

時間復(fù)雜度：入棧為O(N)，其余為O(1)
空間復(fù)雜度：O(N)

代碼

該方法只有入棧和出棧還有返回棧頂元素的函數(shù)和第一種方法不同，只需將這三個函數(shù)改變即可。

void myStackPush(MyStack* obj, int x) {assert(obj);//先設(shè)q1為空隊列，q2為非空隊列Queue* emptyQ = &(obj->q1);Queue* noemptyQ = &(obj->q2);//如果q1非空，說明設(shè)錯了，則改正。if(!QueueEmpty(&(obj->q1))){emptyQ = &(obj->q2);noemptyQ = &(obj->q1);}QueuePush(emptyQ,x);//將非空隊列中的元素都進入空隊列中while(QueueSize(noemptyQ)>0){QueuePush(emptyQ,QueueFront(noemptyQ));QueuePop(noemptyQ);}}int myStackPop(MyStack* obj) {//先判斷棧是否為空，如果為空則不可以出棧assert(obj);assert(!myStackEmpty(obj));//先設(shè)q1為空隊列，q2為非空隊列Queue* emptyQ = &(obj->q1);Queue* noemptyQ = &(obj->q2);//如果q1非空，說明設(shè)錯了，則改正。if(!QueueEmpty(&(obj->q1))){emptyQ = &(obj->q2);noemptyQ = &(obj->q1);}int top = QueueFront(noemptyQ);QueuePop(noemptyQ);return top;
}int myStackTop(MyStack* obj) {assert(obj);//此時非空隊列中元素的順序和出棧順序一致，所以棧頂元素在隊頭assert(!myStackEmpty(obj));if(!QueueEmpty(&(obj->q1))){return QueueFront(&(obj->q1));}else{return QueueFront(&(obj->q2));}
}

方法三、

使用一個隊列來實現(xiàn)棧。

實現(xiàn)思路

該方法只需要一個隊列即可，當(dāng)有元素要入棧時，在隊列中的操作是將該元素先入隊列，然后將該隊列的隊尾結(jié)點之前的結(jié)點都依次出隊列再入隊列，此時剛進入棧的元素即在隊列的隊頭中，當(dāng)要出棧時，直接將隊頭元素出隊即可。

時間復(fù)雜度和空間復(fù)雜度

時間復(fù)雜度：入棧為O(N)，其余為O(1)
空間復(fù)雜度：O(1)

代碼

該方法因為只用了一個結(jié)構(gòu)體，所以棧結(jié)構(gòu)體中只創(chuàng)建了一個隊列

/該結(jié)構(gòu)體采用了匿名結(jié)構(gòu)體，然后將這個匿名結(jié)構(gòu)體重命名為MyStack
typedef struct {//創(chuàng)建一個隊列Queue q1;
} MyStack;
bool myStackEmpty(MyStack* obj);MyStack* myStackCreate() {//此時MyStack就相當(dāng)于一個棧，當(dāng)我們要使用一個棧時，先申請空間創(chuàng)建一個MyStack的結(jié)點MyStack* stack = (MyStack*)malloc(sizeof(MyStack));QueueInit(&(stack->q1));return stack;
}void myStackPush(MyStack* obj, int x) {assert(obj);//先將元素入隊QueuePush(&(obj->q1),x);//然后將隊列中隊尾元素之前的結(jié)點都出隊再入隊int k = QueueSize(&(obj->q1))-1;while(k){QueuePush(&(obj->q1),QueueFront(&(obj->q1)));QueuePop(&(obj->q1));k--;}}int myStackPop(MyStack* obj) {//先判斷棧是否為空，如果為空則不可以出棧assert(obj);assert(!myStackEmpty(obj));//此時隊列中的隊頭元素即為棧頂元素int top = QueueFront(&(obj->q1));QueuePop(&(obj->q1));return top;
}int myStackTop(MyStack* obj) {assert(obj);//此時隊列中的隊頭元素即為棧頂元素assert(!myStackEmpty(obj));return QueueFront(&(obj->q1));
}bool myStackEmpty(MyStack* obj) {assert(obj);//判斷棧空就是判斷隊列是否為空return QueueEmpty(&(obj->q1));
}void myStackFree(MyStack* obj) {assert(obj);//先釋放隊列的空間，然后再釋放obj的空間QueueDestroy(&(obj->q1));free(obj);
}

總結(jié)

用隊列實現(xiàn)棧的第一種方法和第二種方法類似，不過一個是在入棧時進行處理，一個是在出棧時處理。而第三種方法只使用了一個隊列，在入棧時做處理。