【LeetCode】用佇列實作堆疊（225. 題）| 動圖演示，超詳細哦~

題目難度：《簡單》

（1）題目描述

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

實作 MyStack 類：

• void push(int x) 將元素 x 壓入堆疊頂，
• int pop() 移除并回傳堆疊頂元素，
• int top() 回傳堆疊頂元素，
• boolean empty() 如果堆疊是空的，回傳 true ；否則，回傳 false ，

注意：

• 你只能使用佇列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作，
• 你所使用的語言也許不支持佇列， 你可以使用 list （串列）或者 deque（雙端佇列）來模擬一個佇列 , 只要是標準的佇列操作即可，

示例：

輸入：
[ “MyStack”, “push”, “push”, “top”, “pop”, “empty” ]
[ [ ], [1], [2], [ ], [ ], [ ] ]
輸出：
[ null, null, null, 2, 2, false ]

解釋：
MyStack myStack = new MyStack( );
myStack.push(1);
myStack.push(2);
myStack.top( ); //回傳 2
myStack.pop( ); //回傳 2
myStack.empty( ); //回傳 False

LeetCode鏈接：225. 用佇列實作堆疊

（2）解題思路

• 兩個佇列 Q1 和 Q2，相互倒資料，實作堆疊（先進后出）
• 入資料，向不為空的那個佇列入，
• 出資料，將不為空的佇列的前 size - 1 個資料倒入到另外一個空佇列中，然后將不為空佇列中剩下的一個數 Pop 掉，此時該佇列為空了
• 動圖演示

• 代碼如下

首先實作一個佇列（鏈式結構），博主的上一篇博客講了佇列的實作，這里就直接貼代碼了哦

【資料結構入門】佇列（Queue）詳解（定義、銷毀、入隊、出隊等）| 圖解資料結構，超詳細哦~

typedef int QDataType;

typedef struct QueueNode  //佇列節點結構
{
	QDataType data;          //節點資料
	struct QueueNode* next;  //節點指標
}QueueNode;

typedef struct QueuePtr  //佇列的鏈式結構
{
	QueueNode* phead;  //隊頭指標
	QueueNode* ptail;  //隊尾指標
}LinkQueue;

//初始化佇列
void QueueInit(LinkQueue* pQ);
//銷毀佇列
void QueueDestroy(LinkQueue* pQ);
//入隊（尾插）
void QueuePush(LinkQueue* pQ, QDataType x);
//出隊（頭刪）
void QueuePop(LinkQueue* pQ);
//獲取佇列元素個數
int QueueSize(LinkQueue* pQ);
//獲取隊頭元素
QDataType QueueFront(LinkQueue* pQ);
//獲取隊尾元素
QDataType QueueBack(LinkQueue* pQ);
//檢查佇列是否為空
bool QueueEmpty(LinkQueue* pQ);

//初始化佇列
void QueueInit(LinkQueue* pQ)
{
	assert(pQ);
	//佇列為空
	pQ->phead = pQ->ptail = NULL;
}

//銷毀佇列
void QueueDestroy(LinkQueue* pQ)
{
	assert(pQ);

	QueueNode* cur = pQ->phead;
	while (cur)  //遍歷鏈式佇列
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	cur = NULL;
	pQ->phead = pQ->ptail = NULL;  //佇列為空
}

//入隊（尾插）
void QueuePush(LinkQueue* pQ, QDataType x)
{
	assert(pQ);

	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));  //動態申請一個節點
	if (newnode == NULL)  //檢查是否申請成功
	{
		perror("malloc");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;  //尾節點next指標置空

	if (pQ->phead == NULL)  //佇列為空
	{
		pQ->phead = newnode;
	}
	else  //佇列不為空
	{
		pQ->ptail->next = newnode;
	}
	pQ->ptail = newnode;   //更新隊尾指標
}

//出隊（頭刪）
void QueuePop(LinkQueue* pQ)
{
	assert(pQ);
	assert(!QueueEmpty(pQ));  //佇列不能為空

	if (pQ->phead == pQ->ptail)  //佇列中只有一個節點
	{
		free(pQ->phead);
		pQ->phead = pQ->ptail = NULL;
	}
	else
	{
		QueueNode* next = pQ->phead->next;  //記錄頭節點的直接后繼
		free(pQ->phead);  //釋放頭節點
		pQ->phead = next; //更新隊頭指標
	}
}

//獲取佇列元素個數
int QueueSize(LinkQueue* pQ)
{
	assert(pQ);

	int size = 0;
	QueueNode* cur = pQ->phead;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

//獲取隊頭元素
QDataType QueueFront(LinkQueue* pQ)
{
	assert(pQ);
	assert(!QueueEmpty(pQ));  //佇列不能為空

	return pQ->phead->data;
}

//獲取隊尾元素
QDataType QueueBack(LinkQueue* pQ)
{
	assert(pQ);
	assert(!QueueEmpty(pQ));  //佇列不能為空

	return pQ->ptail->data;
}

//檢查佇列是否為空，若為慷訓傳true，否則回傳false
bool QueueEmpty(LinkQueue* pQ)
{
	assert(pQ);
	return pQ->phead == NULL && pQ->ptail == NULL;
}

核心代碼：

typedef struct {
    LinkQueue Q1;  //佇列1
    LinkQueue Q2;  //佇列2
} MyStack;

/** 初始化堆疊 */
MyStack* myStackCreate() {
    //創建兩個佇列
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    if(pst == NULL)  //檢查是否申請成功
    {
        perror("malloc");
        exit(-1);
    }
    //初始化兩個佇列
    QueueInit(&pst->Q1);
    QueueInit(&pst->Q2);

    return pst;
}

/** 入堆疊 */
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //入資料，向不為空的那個佇列入
    if(!QueueEmpty(&obj->Q1))  //Q1不為空
    {
        QueuePush(&obj->Q1, x);
    }
    else
    {
        QueuePush(&obj->Q2, x);
    }
}

/** 出堆疊 */
int myStackPop(MyStack* obj) {
    assert(obj);
    
    //設定2個標志變數
    LinkQueue* emptyQ = &obj->Q1;    //假設Q1為空
    LinkQueue* nonemptyQ = &obj->Q2; //假設Q2不為空
    
    //確定標志變數
    if(!QueueEmpty(&obj->Q1))  //Q1不為空
    {
        nonemptyQ =  &obj->Q1; //Q1不為空
        emptyQ = &obj->Q2;     //Q2為空
    }
    
    //將非空佇列的前size-1個元素匯入到空佇列中
    while(QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ, QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    
    //Pop掉非空佇列中剩下的最后一個元素，這個資料相當于MyStack的堆疊頂元素
    int top = QueueFront(nonemptyQ);  //獲取最后一個元素
    QueuePop(nonemptyQ);              //出隊最后一個元素
    return top;
}

/** 獲取堆疊頂元素 */
int myStackTop(MyStack* obj) {
    assert(obj);

    //非空佇列的隊尾元素其實就是myStack堆疊頂元素
    if(!QueueEmpty(&obj->Q1))  //Q1不為空
    {
        return QueueBack(&obj->Q1);
    }
    else  //Q2不為空
    {
        return QueueBack(&obj->Q2);
    }
}

/** 對堆疊判空，若為慷訓傳true，否則回傳false */
bool myStackEmpty(MyStack* obj) {
    assert(obj);

    return QueueEmpty(&obj->Q1) && QueueEmpty(&obj->Q2);
}

/** 釋放堆疊 */
void myStackFree(MyStack* obj) {
    assert(obj);

    QueueDestroy(&obj->Q1);  //釋放鏈式佇列Q1
    QueueDestroy(&obj->Q2);  //釋放鏈式佇列Q2

    free(obj);  //釋放動態申請的空間
}

大家快去動手試一試吧！