《手撕資料結構經典題系列》用佇列實作堆疊

用佇列實作堆疊

力扣鏈接：225. 用佇列實作堆疊 - 力扣（LeetCode） (leetcode-cn.com)

• 題目描述：

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

• 實作 MyStack 類：

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

• 注意：

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

• 解題思路：

1. 堆疊的特性是先入后出，而佇列的特性是先入先出
2. 先讓一個佇列入資料，另一個佇列不入資料
3. 出資料時，先出佇列到最后一個資料，而之前的資料都入到另一個空佇列
4. 最后將佇列最后一個資料給出佇列
5. 以后再入資料時，都入到有資料的佇列
6. 出資料時，都現將最后一個資料之前的資料入到另一個空佇列，再將最后一個資料給出佇列
7. 總之永遠保持有一個佇列為空

• 圖示：

參考代碼：

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) {
    //出堆疊時，先將有資料的佇列出隊到最后一個元素，并將資料入隊到空佇列，最后將最后一個資料出隊達到出堆疊的效果
    Queue* emptyQ=&obj->q1;
    Queue* noemptyQ=&obj->q2;
    if(QueueEmpty(&obj->q2))
    {
        emptyQ=&obj->q2;
        noemptyQ=&obj->q1;
    }
    while(QueueSize(noemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(noemptyQ));
        QueuePop(noemptyQ);
    }
    int top=QueueFront(noemptyQ);
    QueuePop(noemptyQ);
    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->q1);
    free(obj);
}

佇列原始碼

typedef int QDataType;

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

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
	// size_t _size;
}Queue;

//void QueueInit(QueueNode** pphead, QueueNode** pptail);
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);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

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

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

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;

	if (pq->head == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	//if (pq->head == NULL)
	//	return;
	assert(!QueueEmpty(pq));

	QueueNode* next = pq->head->next;
	free(pq->head);
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = 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)
	{
		++n;
		cur = cur->next;
	}

	return n;
}

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