【圖解演算法】Leetcode 225. 用佇列實作堆疊

題目鏈接

解題思路

堆疊的結構特點是后入先出，

本題核心思路是：

1. 入資料時，往不為空的佇列入資料，保持另一個佇列為空，
2. 出資料，依次出掉隊頭資料到另一個佇列，留下最后一個資料，pop

圖解

1. 定義兩個佇列q1和q2，第一步壓入1, 2，3,4
   
2. 彈出4（后入的資料）
   
3. 壓入 5，6,7
   

堆疊結構

本題中我們考慮到一個因素，函式是在堆疊區開辟的，堆疊幀隨著函式結束而銷毀，所以初始化的堆疊要放在堆區，

代碼題解

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

// 初始化佇列
void QueueInit(Queue* pq);
// 隊尾入佇列
void QueuePush(Queue* pq, QDataType x);
// 隊頭出佇列
void QueuePop(Queue* pq);
// 判斷佇列是否為空
bool QueueEmpty(Queue* pq);
// 獲取佇列頭部元素
QDataType QueueFront(Queue* pq);
// 獲取佇列尾部元素
QDataType QueueBack(Queue* pq);
// 獲取佇列中有效元素個數
int QueueSize(Queue* pq);
// 銷毀佇列
void QueueDestroy(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->head = NULL;
	pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	// 創建新結點
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->next = NULL;
	newnode->data = x;

	// 尾插
	// 空鏈表
	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		// 非空鏈表
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	// 空鏈表
	assert(!QueueEmpty(pq));

	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;

	if (pq->head == NULL)
	{
		// 鏈表此時已經為空
		pq->tail = NULL;
	}
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

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 n = 0;
	QueueNode* cur = pq->head;
	while (cur)  // cur指向NULL的時候退出回圈
	{
		++n;
		cur = cur->next;
	}
	return n;
}

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}

	// 每一個結點都要釋放了，把head和tail置為NULL
	pq->head = pq->tail = NULL;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
    // 入資料到不為空的佇列
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    // 把佇列中資料都轉移到另一個佇列，再pop剩余的一個數字
    Queue* emptyQueue = &obj->q1;
    Queue* notemptyQueue = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQueue = &obj->q2;
        notemptyQueue = &obj->q1;
    }

    while(QueueSize(notemptyQueue) > 1)
    {
        QueuePush(emptyQueue, QueueFront(notemptyQueue));
        QueuePop(notemptyQueue);
    }

    int ret = QueueFront(notemptyQueue);
    QueuePop(notemptyQueue);
    return ret;
}

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);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

重點分析小結

1. 取堆疊頭元素，只需要呼叫非空佇列的尾指標

2. 針對測驗用例報錯

在寫代碼的時候遇到了一個報錯

這時候，就需要逐行分析，

因為獲得堆疊頂元素還可以通過把隊頭元素都轉移到空佇列，然后把最后一個資料的值直接回傳，
但是！
在這里，我忘記了把這個元素壓入佇列里，導致了這樣的錯誤，