LeetCode鏈接：225. 用隊列實現(xiàn)棧 - 力扣（LeetCode）

本文默認讀者已經(jīng)掌握棧與隊列的基本知識

或者先看我的另一篇博客：【數(shù)據(jù)結(jié)構(gòu)】棧與隊列_字節(jié)連結(jié)的博客-CSDN博客

做題思路

由于我們使用的是C語言，不能直接使用隊列的操作，

所以做這道題得先把我們之前實現(xiàn)的隊列復(fù)制過來：

//C語言模擬實現(xiàn)隊列


//鏈?zhǔn)浇Y(jié)構(gòu)：表示隊列
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

//隊列的結(jié)構(gòu)
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Que;

//初始化隊列
void QueueInit(Que* pq);
//銷毀隊列
void QueueDestroy(Que* pq);
//隊尾入隊列
void QueuePush(Que* pq, QDataType x);
//隊頭出隊列
void QueuePop(Que* pq);
//獲取隊列頭部元素
QDataType QueueFront(Que* pq);
//獲取隊列隊尾元素
QDataType QueueBack(Que* pq);
//檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
bool QueueEmpty(Que* pq);
//獲取隊列中有效元素個數(shù)
int QueueSize(Que* pq);

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

void QueueDestroy(Que* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Que* 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->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

QDataType QueueFront(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

QDataType QueueBack(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

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

int QueueSize(Que* pq)
{
	assert(pq);
	return pq->size;
}

復(fù)制完成后進入正題：

答：用兩個隊列捯數(shù)據(jù)的方式來實現(xiàn)后入先出的棧

圖文解析：

代碼：

//用兩個隊列實現(xiàn)棧
typedef struct
{
    Que q1;//隊列1
    Que q2;//隊列2
} MyStack;

//開辟空間并初始化
MyStack* myStackCreate()
{
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
	return pst;
}

//將元素x壓入棧頂
void myStackPush(MyStack* obj, int x)
{
    if (!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

//移除并返回棧頂元素
int myStackPop(MyStack* obj)
{
    Que* empty = &obj->q1;
    Que* nonEmpty = &obj->q2;
    if (!QueueEmpty(&obj->q1))
    {
        nonEmpty = &obj->q1;
        empty = &obj->q2;
    }
    //前size-1個導(dǎo)入空隊列
    while (QueueSize(nonEmpty) > 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);
    }
}

//如果棧是空的，返回true；否則，返回false
bool myStackEmpty(MyStack* obj)
{
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

//銷毀棧
void myStackFree(MyStack* obj)
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

提交代碼：

成功通過

本文完文章來源地址http://www.zghlxwxcb.cn/news/detail-661268.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】如何用隊列實現(xiàn)棧？圖文詳解（LeetCode）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！