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

?? 1.題目來源

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

??2.題目描述

請你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（push、pop、peek、empty）：
實(shí)現(xiàn) MyQueue 類：
1.void push(int x) 將元素 x 推到隊(duì)列的末尾
2.int pop() 從隊(duì)列的開頭移除并返回元素
3.int peek() 返回隊(duì)列開頭的元素
4.boolean empty() 如果隊(duì)列為空，返回 true ；否則，返回 false

??說明：

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

??3.解題思路

• 從題目要求我們知道，要用兩個(gè)棧列實(shí)現(xiàn)隊(duì)列的功能，也就是使用的是棧，??但是實(shí)現(xiàn)的效果時(shí)隊(duì)列的效果。
• 開始做題之前我們首要的是明白隊(duì)列和棧的特點(diǎn)。這里我們就簡單的提一下，具體的知識請看上述給的鏈接。??隊(duì)列——隊(duì)列的特性是??先進(jìn)的先出，就跟食堂打飯一樣，先到的先打飯，打完飯就可以走了。?！獥５奶匦允??先進(jìn)的后出，就跟我們在桌子上疊書一樣，想要拿到最底下的書就要先把最上面的書先拿走。
• 首先隊(duì)列的插入和棧的插入都是一樣的，都是尾插，所以push這個(gè)動(dòng)作并不難，關(guān)鍵是棧的刪除是尾刪，而隊(duì)列的刪除時(shí)頭刪，那怎么樣才能使用兩個(gè)棧實(shí)現(xiàn)刪除頭上的數(shù)據(jù)呢。既然棧是尾刪，能不能把存放進(jìn)去的數(shù)據(jù)反過來，這樣雖然棧進(jìn)行的是尾刪，但是刪除的是頭上的數(shù)據(jù)，也就相當(dāng)于是頭刪一樣了。
• ??那么我們的思路肯定是這樣的：兩個(gè)棧，首先第一次存放數(shù)據(jù)的時(shí)候，??隨便找一個(gè)棧粗放數(shù)據(jù)，假設(shè)放的是1，2，3，4，5頭數(shù)據(jù)是1，尾數(shù)據(jù)是5，等到要?jiǎng)h除的時(shí)候通過找到尾的方式把數(shù)據(jù)一一放到另一個(gè)棧中，這樣另一個(gè)棧的數(shù)據(jù)就是5，4，3，2，1了，這個(gè)時(shí)候頭數(shù)據(jù)就是5，尾數(shù)據(jù)就是1了，Pop的時(shí)候就是Pop尾數(shù)據(jù)1，也就是插入時(shí)的頭數(shù)據(jù)，這樣就實(shí)現(xiàn)頭刪??。而如果還要繼續(xù)存放數(shù)據(jù)的時(shí)候就把數(shù)據(jù)按照上面同樣的操作把數(shù)據(jù)重新放回去，也就是2，3，4，5，然后繼續(xù)在后面放數(shù)據(jù)，要?jiǎng)h除的時(shí)候再重復(fù)第一次的操作即可。那么問題來了，從上述分析我們知道了兩個(gè)棧，一個(gè)棧是用來存放數(shù)據(jù)進(jìn)去的棧我們命名為Spush，一個(gè)是用來刪除數(shù)據(jù)的棧Spop，而且我們每次還要繼續(xù)放數(shù)據(jù)的是由都要把數(shù)據(jù)從Spop中把數(shù)據(jù)放回Spush，然后進(jìn)行追加數(shù)據(jù)???，但是這一步真的有必要嗎？??其實(shí)并不需要這兩個(gè)棧就只需要完成一個(gè)push另一個(gè)pop就行了，追加數(shù)據(jù)的時(shí)候也不需要把數(shù)據(jù)從Spop中重新放回Spush中，只需要等Spop中數(shù)據(jù)被刪除完后，再從Spush中導(dǎo)入即可。

• 所以總上所述，我們的兩個(gè)棧，每一棧復(fù)雜特定的功能，一個(gè)負(fù)責(zé)push數(shù)據(jù)，一個(gè)用來pop數(shù)據(jù)

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

typedef struct {

} MyQueue;

MyQueue* myQueueCreate() {

}

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

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

??4.代碼展示

//棧函數(shù)接口
typedef int STDataType;
typedef struct Stack
{
	STDataType* data;
	int capaciyt;
	int size;
}Stack;

void StackInit(Stack* ps);

void StackDestroy(Stack* ps);

void StackPush(Stack* ps, STDataType x);

void StackPop(Stack* ps);

STDataType StackTop(Stack* ps);

bool StackEmpt(Stack* ps);

int StackSize(Stack* ps);

void StackInit(Stack* ps)
{
	assert(ps);
	ps->data = NULL;
	ps->capaciyt = 0;
	ps->size = 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->data);
	ps->data = NULL;
	ps->capaciyt = ps->size = 0;
}

void StackPush(Stack* ps, STDataType x)
{
	assert(ps);

	if (ps->size == ps->capaciyt)
	{
		int newCapacity = ps->capaciyt == 0 ? 4 : ps->capaciyt * 2;
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->data = tmp;
		ps->capaciyt = newCapacity;
	}

	ps->data[ps->size] = x;
	ps->size++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpt(ps));

	ps->size--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpt(ps));

	return ps->data[ps->size - 1];
}

bool StackEmpt(Stack* ps)
{
	assert(ps);

	return ps->size == 0;
}

int StackSize(Stack* ps)
{
	assert(ps);

	return ps->size;
}

//函數(shù)實(shí)現(xiàn)
typedef struct {
    Stack Spush;
    Stack Spop;
} MyQueue;

MyQueue* myQueueCreate() {
    MyQueue* ret = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&ret->Spush);
    StackInit(&ret->Spop);

    return ret;
}

//這里我把Peek函數(shù)放到了前面，考慮到后面的Pop也會(huì)用到類似的功能，直接服用Peek就行了
int myQueuePeek(MyQueue* obj) {
    //為空導(dǎo)入數(shù)據(jù)
    if (StackEmpt(&obj->Spop))
    {
        while (!StackEmpt(&obj->Spush))
        {
            StackPush(&obj->Spop,StackTop(&obj->Spush));
            StackPop(&obj->Spush);
        }
    }
    return StackTop(&obj->Spop);
}

void myQueuePush(MyQueue* obj, int x) {
    //直接再Spush中插入數(shù)據(jù)
    StackPush(&obj->Spush,x);
}

int myQueuePop(MyQueue* obj) {
    //服用Peek,如果Spop為空，就從Spush中導(dǎo)入數(shù)據(jù)
   int ret = myQueuePeek(obj);
   StackPop(&obj->Spop);
   return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    //兩個(gè)為空才為空
    return StackEmpt(&obj->Spop) && StackEmpt(&obj->Spush);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->Spop);
    StackDestroy(&obj->Spush);

    free(obj);
}

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