C語(yǔ)言用棧模擬實(shí)現(xiàn)隊(duì)列問(wèn)題詳解

更新時(shí)間：2022年04月01日 08:54:10 作者：_奇奇

本片文章帶你分析如何用兩個(gè)棧，并且只使用棧的基本功能來(lái)模擬實(shí)現(xiàn)隊(duì)列，其中同樣只實(shí)現(xiàn)隊(duì)列的基本功能，感興趣的朋友來(lái)看看吧

題目描述

請(qǐng)你僅使用兩個(gè)棧實(shí)現(xiàn)先入先出隊(duì)列。隊(duì)列應(yīng)當(dāng)支持一般隊(duì)列支持的所有操作（push、pop、peek、empty）。

你只能使用標(biāo)準(zhǔn)的棧操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

題目鏈接

用棧實(shí)現(xiàn)隊(duì)列

思路分析

題目的意思是要用兩個(gè)棧來(lái)模擬實(shí)現(xiàn)一個(gè)隊(duì)列。僅可以用棧的基本功能實(shí)現(xiàn)隊(duì)列的基本功能。所以需要?jiǎng)?chuàng)建兩個(gè)棧。所以這兩個(gè)棧st1，st2可用一個(gè)結(jié)構(gòu)體包含。本質(zhì)就是用兩個(gè)后進(jìn)先出的棧，來(lái)模擬一個(gè)先進(jìn)先出的隊(duì)列。

在這里插入圖片描述

思路：

在這里插入圖片描述

1.st2這個(gè)棧用來(lái)壓棧，st1的作用：把st2的所有值壓到st1中，然后經(jīng)過(guò)st1出棧。這樣就達(dá)到了隊(duì)列先進(jìn)先出的性質(zhì)。

2.st2一直用來(lái)壓棧。如果st1為空則將st2里面的值全都轉(zhuǎn)移到st1，如果st1不為空，則繼續(xù)出棧，知道st1為空為止。

代碼實(shí)現(xiàn)

在這里插入圖片描述

ypedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化結(jié)構(gòu)體
void StackInit(ST* ps);
//銷毀結(jié)構(gòu)體
void StackDestroy(ST* ps);
//壓棧
void StackPush(ST* ps, STDataType x);
//出棧
void StackPop(ST* ps);
//得到棧頂?shù)闹?
STDataType StackTop(ST* ps);
//判斷棧是否為空
bool StackEmpty(ST* ps);
//得到棧的長(zhǎng)度
int StackSize(ST* ps);


//初始化結(jié)構(gòu)體
void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
//銷毀結(jié)構(gòu)體
void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;


}
//壓棧
void StackPush(ST* ps, STDataType x)
{

	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* new = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (new == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = new;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}
STDataType StackTop(ST* ps)
{
	assert(ps);
    assert(ps->top>0);
	return ps->a[ps->top-1];
}
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//得到棧的長(zhǎng)度
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}



//創(chuàng)建了兩個(gè)棧
typedef struct
 {
    ST st1;
    ST st2;

} MyQueue;

//對(duì)兩個(gè)棧進(jìn)行初始化。
MyQueue* myQueueCreate() 
{
    MyQueue* newQueue = (MyQueue*)malloc(sizeof(MyQueue));
    assert(newQueue);
    StackInit(&newQueue->st1);
    StackInit(&newQueue->st2);

    return newQueue;

}

void myQueuePush(MyQueue* obj, int x) 
{
    assert(obj);
    StackPush(&obj->st2, x);

}

int myQueuePop(MyQueue* obj)
 {
     assert(obj);
     if(StackEmpty(&obj->st1))
     {
        while(!StackEmpty(&obj->st2))
        {
          StackPush(&obj->st1,  StackTop(&obj->st2));
            StackPop(&obj->st2);
        }
     }
        int top = 0;
     if(!StackEmpty(&obj->st1))
     {
         top = StackTop(&obj->st1);
         StackPop(&obj->st1);
     }    
    return top;
}

int myQueuePeek(MyQueue* obj) 
{
   assert(obj);
     if(StackEmpty(&obj->st1))
     {
        while(!StackEmpty(&obj->st2))
        {
          StackPush(&obj->st1,  StackTop(&obj->st2));
            StackPop(&obj->st2);
        }
     }
 
     if(!StackEmpty(&obj->st1))
     {
         return StackTop(&obj->st1);
     }
     return 0;
}

bool myQueueEmpty(MyQueue* obj)
{
    return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->st1);
    StackDestroy(&obj->st2);
    free(obj);
}

到此這篇關(guān)于C語(yǔ)言用棧模擬實(shí)現(xiàn)隊(duì)列問(wèn)題詳解的文章就介紹到這了,更多相關(guān)C語(yǔ)言棧實(shí)現(xiàn)隊(duì)列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: