栈实现队列

发表于 分类于
本文详细讲解了基于C语言用栈实现队列

介绍

题目来源

题目来源于力扣网站:栈实现队列
题目

原理讲解

根据要求，只能使用标准的栈操作实现队列，关于标准的栈操作可以看我写过的文章:栈

我们知道，栈是先进后出，而队列是先进先出，所以毫无疑问，仅用一个栈没办法实现队列

进一步考虑，栈的出入顺序是相反的，所以如果将出栈顺序逆序，就实现了先进先出，因此可以使用两个栈来达到这个效果
结构示意图
上图用栈操作来讲解就是，队列尾插，相当于对pushst入栈，然后将pushst出栈同时对popst入栈，当队列头删时，相当于popst出栈

以上是基本原理，接下来我们用代码实现这个队列

代码实现

栈的基本操作如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

//初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

//入栈 出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);

//取栈顶
STDataType STTop(ST* pst);

//判空
bool STEmpty(ST* pst);

//获取数据个数
int STSize(ST* pst);

队列结构

1
2
3
4
5
//MyQueue
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;

初始化

 
初始化一个队列，返回队列的指针
1.申请空间
2.将队列里两个栈初始化
3.返回队列的指针

1
2
3
4
5
6
MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&(obj->pushst));
    STInit(&(obj->popst));
    return obj;
}

销毁

 
销毁队列占用的空间，传入队列的指针
1.销毁两个栈
2.释放队列指针

1
2
3
4
5
void myQueueFree(MyQueue* obj) {
    STDestroy(&(obj->pushst));
    STDestroy(&(obj->popst));
    free(obj);
}

尾插

 
尾插新数据，传入队列指针和新数据x
根据前文中讲的原理，对队列尾插相当于对pushst入栈，因此直接调用入栈函数即可

1
2
3
void myQueuePush(MyQueue* obj, int x) {
    STPush(&(obj->pushst),x);
}

头删

 
队列头删，传队列指针，返回队头元素
根据上述原理，队列头删相当于popst出栈
popst的顶端元素就是队列的队头元素，根据题目要求，头删时返回队头元素
因此首先判断popst是否为空
如果popst为空，就将pushst里的所有数据先出栈，再入栈到popst
接下来用ret接收popst的顶端元素，再对popst执行出栈
最后返回ret

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int myQueuePop(MyQueue* obj) {
	//栈判空
    if(STEmpty(&(obj->popst)))
    {	
    	//将数据从pushst出栈，同时入栈到popst
        while(!STEmpty(&(obj->pushst)))
        {
            STPush(&(obj->popst),STTop(&(obj->pushst)));
            STPop(&(obj->pushst));
        }
    }
    //接收队头数据
    int ret = STTop(&(obj->popst));
    STPop(&(obj->popst));
    return ret;
}

返回队头数据

 
获取队头元素，传入队列指针
这个函数来源于上面头删函数，但是不需要对popst出栈

1
2
3
4
5
6
7
8
9
10
11
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&(obj->popst)))
    {
        while(!STEmpty(&(obj->pushst)))
        {
            STPush(&(obj->popst),STTop(&(obj->pushst)));
            STPop(&(obj->pushst));
        }
    }
    return STTop(&(obj->popst));
}

判空

 
判断队列是否为空，返回bool值
当队列中两个栈都为空时，队列就是空，因此用逻辑与对两个栈判空即可

1
2
3
4
5
6
7
bool myQueueEmpty(MyQueue* obj) {
    if(STEmpty(&(obj->pushst)) && STEmpty(&(obj->popst)))
    {
        return true;
    }
    return false;
}

总结

问题的突破关键在于，栈遵守先进后出的原则，队列遵守先进先出的原则，栈可以逆序数据，两个栈就是两次逆序，两次逆序后顺序不变，从而实现了队列的原则

在尾插时对pushst入栈，在头删时对popst出栈，两个栈互不干扰
只有当popst为空时，才需要将pushst的数据压入popst

最后这是代码的通过截图
通过截图

如果文章内容有误，欢迎指出