棧和隊列的互相實現

用隊列實現棧

OJ鏈接

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop?和?empty）。

實現?MyStack?類：

void push(int x)?將元素 x 壓入棧頂。
int pop()?移除并返回棧頂元素。
int top()?返回棧頂元素。
boolean empty()?如果棧是空的，返回?true?；否則，返回?false?。

隊列：先進先出，后進后出

棧：先進后出，后進先出?

思路：一個隊列存數據；另一個隊列用來出數據時，導數據

用單鏈表實現隊列代碼

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int QDataType;//創建隊列節點
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;//創建維護隊列的指針
typedef struct Queue
{QNode* phead;QNode* ptail;int size;//原本是需要遍歷的，寫在結構體里可以很好的是時間復雜度由O(N)變為O(1)
}Queue;//初始化
void QueueInit(Queue* pq);//空間釋放
void QueueDestroy(Queue* pq);//尾插
void QueuePush(Queue* pq, QDataType x);//頭刪
void QueuePop(Queue* pq);//取隊頭的數據
QDataType QueueFront(Queue* pq);//取隊尾的數據
QDataType QueueBack(Queue* pq);//判斷是否為空
bool QueueEmpty(Queue* pq);//隊列元素個數
int QueueSize(Queue* pq);void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;if (pq->ptail == NULL){pq->ptail = pq->phead = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);// assert(pq->phead);QNode* del = pq->phead;pq->phead = pq->phead->next;free(del);del = NULL;if (pq->phead == NULL)pq->ptail = NULL;pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);// assert(pq->phead);return pq->phead->val;
}QDataType QueueBack(Queue* pq)
{assert(pq); assert(pq->ptail);return pq->ptail->val;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

聲明棧MyStack

//匿名結構體
typedef struct {Queue q1;Queue q2;
} MyStack;//結構體類型
//如果不加typedef，MyStack就是結構體變量

創建&初始化棧myStackCreate

//初始化
MyStack* myStackCreate() {//MyStack mystack;出了作用域就銷毀了MyStack* pst=(MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}

壓棧myStackPush

哪個隊列不為空就往哪個隊列里面插入

//插入元素
void myStackPush(MyStack* obj, int x) {assert(obj);//找不為NULL的隊列依次插入if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);//尾插}else{QueuePush(&obj->q2, x);}
}

出棧并返回棧頂元素myStackPop?

這里有一個問題：如何知道q1和q2誰為空誰不為空？

首先用假設法，假設其中一個隊列是空，另一個隊列不是空，然后進行驗證。如果驗證第一個隊列不是空，就交換位置。
然后就開始找棧頂元素。先將非空隊列里的元素一個一個導入到空隊列，（記得Pop！）直到非空隊列里只剩下一個元素的時候停止。這個元素就是棧頂元素，然后返回它。最后不要忘記Pop一下。

//出棧
int myStackPop(MyStack* obj) {assert(obj);//判斷為空/非空------假設法Queue*nonempty=&obj->q1;Queue*empty=&obj->q2;if(QueueEmpty(&obj->q1))//{nonempty=&obj->q2;empty=&obj->q1;//創建}//直到隊列里只剩下一個元素，剩下的這個元素就是我們要找的棧頂元素while(QueueSize(nonempty)>1)//隊列里面的元素個數 > 1{QueuePush(empty, QueueFront(nonempty));//把隊頭的元素一個一個放到空隊列，QueuePop(nonempty);//把剛放的那個元素從原隊列刪除}int top=QueueFront(nonempty);//隊列尾的元素——棧頂元素QueuePop(nonempty);return top;
}

返回棧頂元素myStackTop

我們要能夠發現，棧頂的元素也就是隊尾的元素。所以我們直接返回隊尾元素就可以了。

//棧頂元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)) {return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}

判斷棧是否為空myStackEmpty

//判斷是否為空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);//&&
}

釋放空間myStackFree

//釋放空間
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj=NULL;
}

總代碼

//匿名結構體
typedef struct {Queue q1;Queue q2;
} MyStack;//結構體類型
//如果不加typedef，MyStack就是結構體變量//初始化
MyStack* myStackCreate() {//MyStack mystack;出了作用域就銷毀了MyStack* pst=(MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}//插入元素
void myStackPush(MyStack* obj, int x) {assert(obj);//找不為NULL的隊列依次插入if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);//尾插}else{QueuePush(&obj->q2, x);}
}//出棧
int myStackPop(MyStack* obj) {assert(obj);//判斷為空/非空------假設法Queue*nonempty=&obj->q1;Queue*empty=&obj->q2;if(QueueEmpty(&obj->q1))//{nonempty=&obj->q2;empty=&obj->q1;//創建}//直到隊列里只剩下一個元素，剩下的這個元素就是我們要找的棧頂元素while(QueueSize(nonempty)>1)//隊列里面的元素個數 > 1{QueuePush(empty, QueueFront(nonempty));//把隊頭的元素一個一個放到空隊列，QueuePop(nonempty);//把剛放的那個元素從原隊列刪除}int top=QueueFront(nonempty);//隊列尾的元素——棧頂元素QueuePop(nonempty);return top;
}//棧頂元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)) {return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}//判斷是否為空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);//&&
}//釋放空間
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj=NULL;
}

用棧實現隊列

OJ鏈接

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現 MyQueue 類：

void push(int x) 將元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并返回元素
int peek() 返回隊列開頭的元素
boolean empty() 如果隊列為空，返回 true ；否則，返回 false

思路：

一個棧用于push，另一個棧用于pop。當用來出棧的那個棧空了以后，入棧的那個棧里面的元素才能導入另一個棧！這樣就可以很好的實現隊列的先進先出原則。

用數組實現棧代碼

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst->a = 0;pst->top = 0;pst->capacity = 0;
}void Createcapacity(ST* pst)
{//擴容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}
}void STPush(ST* pst, STDatatype x)
{assert(pst);Createcapacity(pst);pst->a[pst->top] = x;pst->top++;
}void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}STDatatype STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}bool STempty(ST* pst)
{assert(pst);return pst->top == 0;//為0就是true 為！=0就是為flase
}int STSize(ST* pst)
{assert(pst);return pst->top;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}

聲明隊列MyQueue

typedef struct {ST stpush;ST stpop;
} MyQueue;

創建&初始化隊列myQueueCreate?

創建的臨時變量出了作用域就銷毀了，所以需要malloc才可。

MyQueue* myQueueCreate() {MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->stpush);STInit(&obj->stpop);return obj;
}

入隊列myQueuePush

//入隊列
void myQueuePush(MyQueue* obj, int x) {STPush(&obj->stpush, x);
}

返回隊頭元素myQueuePeek

int myQueuePeek(MyQueue* obj) {//當stpop為空的時候if(STempty(&obj->stpop)){//當stpush不為空while(!STempty(&obj->stpush)){int x=STTop(&obj->stpush);STPush(&obj->stpop,x);STPop(&obj->stpush);}}return STTop(&obj->stpop);
}

從隊列的開頭移除并返回元素myQueuePop?

可以直接調用myQueuePeek，就會直接把元素都移到stpop，我們只管刪除就行了。

int myQueuePop(MyQueue* obj) {int first=myQueuePeek(obj);STPop(&obj->stpop);return first;
}

判斷隊列是否為空myQueueEmpty

bool myQueueEmpty(MyQueue* obj) {return STempty(&obj->stpush) && STempty(&obj->stpop);
}

?釋放空間myQueueFree

銷毀的時候要先銷毀隊列開辟的空間，不然會造成野指針。

void myQueueFree(MyQueue* obj) {STDestroy(&obj->stpush);STDestroy(&obj->stpop);free(obj);obj=NULL;
}

總代碼

typedef struct {ST stpush;ST stpop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->stpush);STInit(&obj->stpop);return obj;
}//入隊列
void myQueuePush(MyQueue* obj, int x) {STPush(&obj->stpush, x);
}int myQueuePeek(MyQueue* obj) {//當stpop為空的時候if (STempty(&obj->stpop)){//當stpush不為空while (!STempty(&obj->stpush)){int x = STTop(&obj->stpush);STPush(&obj->stpop, x);STPop(&obj->stpush);}}return STTop(&obj->stpop);
}int myQueuePop(MyQueue* obj) {int first = myQueuePeek(obj);STPop(&obj->stpop);return first;
}bool myQueueEmpty(MyQueue* obj) {return STempty(&obj->stpush) && STempty(&obj->stpop);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->stpush);STDestroy(&obj->stpop);free(obj);obj = NULL;
}