所屬專欄：玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)題型??
?? >博主首頁：初陽785??
?? >代碼托管：chuyang785??
?? >感謝大家的支持，您的點(diǎn)贊和關(guān)注是對(duì)我最大的支持?。?！??
?? >博主也會(huì)更加的努力，創(chuàng)作出更優(yōu)質(zhì)的博文??！??
?? >關(guān)注我，關(guān)注我，關(guān)注我，重要的事情說三遍?。。。。。。?！??
??????????????????????????????????????????????????

?? 1.題目來源

LeetCode用隊(duì)列實(shí)現(xiàn)棧
??注意：本題涉及到有關(guān)數(shù)據(jù)結(jié)構(gòu)——隊(duì)列和棧，這兩章節(jié)的知識(shí)點(diǎn)，如有小伙伴還不熟棧的，可以先復(fù)習(xí)復(fù)習(xí)一下有關(guān)棧的相關(guān)知識(shí)，復(fù)習(xí)的地方我也提供了哦??，所用到的知識(shí)點(diǎn)——棧，所用到的知識(shí)點(diǎn)——隊(duì)列
??注意：同樣的本題是使用純C語言實(shí)現(xiàn)的.

??2.題目描述

請(qǐng)你僅使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。
實(shí)現(xiàn) MyStack 類：
1.void push(int x) 將元素 x 壓入棧頂。
2.int pop() 移除并返回棧頂元素。
3.int top() 返回棧頂元素。
4.boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

??注意：

• 你只能使用隊(duì)列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作。
• 你所使用的語言也許不支持隊(duì)列。 你可以使用 list （列表）或者 deque（雙端隊(duì)列）來模擬一個(gè)隊(duì)列 , 只要是標(biāo)準(zhǔn)的隊(duì)列操作即可。

??3.解題思路

• 從題目要求我們知道，要用兩個(gè)隊(duì)列實(shí)現(xiàn)棧的功能，這個(gè)就是用隊(duì)列實(shí)現(xiàn)棧
• 開始做題之前我們首要的是明白隊(duì)列和棧的特點(diǎn)。這里我們就簡(jiǎn)單的提一下，具體的知識(shí)請(qǐng)看上述給的鏈接。??隊(duì)列——隊(duì)列的特性是??先進(jìn)的先出，就跟食堂打飯一樣，先到的先打飯，打完飯就可以走了。?！獥５奶匦允??先進(jìn)的后出，就跟我們?cè)谧雷由席B書一樣，想要拿到最底下的書就要先把最上面的書先拿走。
• 搞清楚特性之后，我們就可以開始分析了。首先無論是隊(duì)列還是棧，插入數(shù)據(jù)都是往尾插入的，關(guān)鍵就是怎么使用隊(duì)列實(shí)現(xiàn)棧的尾刪。我們知道隊(duì)列刪除是頭刪，同樣可以拿到頭的數(shù)據(jù)，而且我們有兩個(gè)隊(duì)列，我們能不能先把第一個(gè)隊(duì)列的（n-1）個(gè)數(shù)據(jù)放到另一個(gè)隊(duì)列里面，再把最后剩下的那個(gè)數(shù)據(jù)刪除，這個(gè)樣子就實(shí)現(xiàn)了棧的尾刪。那既然有兩個(gè)隊(duì)列，??怎么知道數(shù)據(jù)從那個(gè)隊(duì)列放到那個(gè)隊(duì)列里面去呢？??這個(gè)簡(jiǎn)單只要判斷兩個(gè)隊(duì)列那個(gè)為空，另一個(gè)數(shù)據(jù)不為空，就把數(shù)據(jù)放到為空的隊(duì)列中去。

• ??同時(shí)解釋一下我們oj刷題的時(shí)出現(xiàn)的一些一些疑問

typedef struct {

} MyStack;

MyStack* myStackCreate() {

}

這個(gè)是我們題目出現(xiàn)的函數(shù)接口，我來解釋一下表示什么意思。文章來源地址http://www.zghlxwxcb.cn/news/detail-635793.html

1. 題目已經(jīng)明確我們要使用兩個(gè)隊(duì)列來實(shí)現(xiàn)棧，所有我們就得創(chuàng)建兩個(gè)隊(duì)列的，而我們通常遇到這種兩個(gè)及以上的要使用的成員時(shí)，??為了減少傳遞的參數(shù)，以及代碼的可讀性，簡(jiǎn)潔性，??我們通常會(huì)用一個(gè)結(jié)構(gòu)體把他們封裝起來，所以我們的上述結(jié)構(gòu)體就是用來創(chuàng)建兩個(gè)隊(duì)列的，并且這個(gè)結(jié)構(gòu)體還是個(gè)匿名結(jié)構(gòu)體，匿名結(jié)構(gòu)體的特點(diǎn)就是只能用一次，這里我們只需要使用一次即可，所以匿名合理。
2. 而另一個(gè)函數(shù)接口是用來初始化我們的結(jié)構(gòu)體的，并返回結(jié)構(gòu)體指針。??

??4.代碼展示

//隊(duì)列函數(shù)接口
typedef int QueueDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDataType data;
}QNode;

typedef struct Node
{
	QNode* head;
	QNode* tail;
	int size;
}Node;

void QueueInit(Node* pq);
void QueueDestroy(Node* pq);
void QueuePushu(Node* pq, QueueDataType x);
void QueuePop(Node* pq);
QueueDataType QueueFindFront(Node* pq);
QueueDataType QueueFindBack(Node* pq);
bool QueueEmpt(Node* pq);
int QueueSize(Node* pq);

void QueueInit(Node* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
void QueueDestroy(Node* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->tail = pq->head = NULL;
	pq->size = 0;
}
void QueuePushu(Node* pq, QueueDataType x)
{
	assert(pq);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	if (pq->tail == NULL)
	{
		pq->tail = pq->head = newNode;
	}
	else
	{
		pq->tail->next = newNode;
		pq->tail = newNode;
	}
	pq->size++;
}
void QueuePop(Node* pq)
{
	assert(pq);
	assert(!QueueEmpt(pq));

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

	if (pq->head == NULL)
	{
		pq->tail = NULL;
	}
	pq->size--;
}
QueueDataType QueueFindFront(Node* pq)
{
	assert(pq);
	assert(!QueueEmpt(pq));

	return pq->head->data;
}
QueueDataType QueueFindBack(Node* pq)
{
	assert(pq);
	assert(!QueueEmpt(pq));

	return pq->tail->data;
}
bool QueueEmpt(Node* pq)
{
	assert(pq);
	
	return pq->head == NULL;
}
int QueueSize(Node* pq)
{
	assert(pq);
	return pq->size;
}



//函數(shù)實(shí)現(xiàn)
typedef struct {
    //創(chuàng)建兩個(gè)隊(duì)列
    Node q1;
    Node q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* ret = (MyStack*)malloc(sizeof(MyStack));
    //初始化隊(duì)列
    QueueInit(&ret->q1);
    QueueInit(&ret->q2);
    //返回結(jié)構(gòu)體指針
    return ret;
}

void myStackPush(MyStack* obj, int x) {
    //判斷那個(gè)隊(duì)列不為空，遍插入數(shù)據(jù)
    if (!QueueEmpt(&obj->q1))
    {
        QueuePushu(&obj->q1,x);
    }
    else
    {
        QueuePushu(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    //判斷那個(gè)為空，（n-1）個(gè)數(shù)據(jù)放到空的隊(duì)列中
    Node* empt = &obj->q1;
    Node* noEmpt = &obj->q2;
    if (!QueueEmpt(&obj->q1))
    {
        noEmpt = &obj->q1;
        empt = &obj->q2;
    }

    while (QueueSize(noEmpt)>1)
    {
        QueuePushu(empt,QueueFindFront(noEmpt));
        QueuePop(noEmpt);
    }
    
    int top = QueueFindFront(noEmpt);
    QueuePop(noEmpt);
    return top;
}

int myStackTop(MyStack* obj) {
    if (!QueueEmpt(&obj->q1))
    {
        return QueueFindBack(&obj->q1);
    }
    else
    {
        return QueueFindBack(&obj->q2);
    }
}

bool myStackEmpty(MyStack* obj) {
    //兩個(gè)隊(duì)列為空才為空
    return QueueEmpt(&obj->q1) && QueueEmpt(&obj->q2);
}

void myStackFree(MyStack* obj) {
    //顯示放隊(duì)列
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    //在釋放結(jié)構(gòu)體
    free(obj);
}

到了這里，關(guān)于【LeetCode】數(shù)據(jù)結(jié)構(gòu)題解（11）[用隊(duì)列實(shí)現(xiàn)棧]的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！