我先来简单的介绍一下栈和队列
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。不含任何元素的栈称为空栈,栈又称为后进先出的线性表。
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表
进行插入操作的一端称为队尾(入队列)
进行删除操作的一端称为队头(出队列)
队列具有先进先出(FIFO)的特性
那么如何用两个栈来实现队列呢?
我们只要使用这两个栈来实现队列的功能即可
对于队列的插入:我们只往一个栈 stack1 中插入元素
void PushQueueB2S(QueueB2S* qbs, SDataType data)
{
assert(qbs);
PushStack(qbs->s1, data);
}
- 对于队列的出队列,也就是删除,那么我们就需要删除最开始进队列的那个元素,那么将栈stack1中的元素全部搬移到栈stack2中,那么最开始进入队列的元素就会出现在栈stack2的栈顶,那么我们将stack2的栈顶元素出栈就可以了。
- 完成之后,我们在将栈stack2中的元素全部搬移到栈stack1中即可。始终保持stack2是空的。
- 出队列前先检测栈1,是否为空,如果为空,那么说明队列为空。不用检测栈stack2,因为不用栈stack2的时候,栈stack2一直是空的。
void PopQueueB2S(QueueB2S* qbs)
{
assert(qbs);
if (!EmptyStack(qbs->s2))
PopStack(qbs->s2);
else
{
if (EmptyStack(qbs->s1))
return;
while (!EmptyStack(qbs->s1))
{
PushStack(qbs->s2, TopStack(qbs->s1));
PopStack(qbs->s1);
}
PopStack(qbs->s2);
}
while (!EmptyStack(qbs->s2))
{
PushStack(qbs->s1, TopStack(qbs->s2));
PopStack(qbs->s2);
}
}
- 打印队列的元素:我们只需要打印栈stack1中的元素即可。
- 栈stack2中若不使用,里面是没有元素的。
void PrintQueueB2S(QueueB2S* qbs)
{
assert(qbs);
PrintStack(qbs->s1);
printf("\n");
}
- 获取队列的队头元素:这个方法和出栈的方法类似,队头元素就是最开始进队列的那个元素,那么我们将栈stack1中的所有元素搬移到栈stack2中,那么栈stack2中栈顶元素就是所要求的队头元素。
- 注意要判断栈stack1是否为空,如果为空,则队列为空。栈stack2一直为空,不用管。
SDataType FrontQueueB2S(QueueB2S* qbs)
{
SDataType temp;
assert(qbs);
if (EmptyStack(qbs->s1))
return NULL;
else
{
while (!EmptyStack(qbs->s1))
{
PushStack(qbs->s2, TopStack(qbs->s1));
PopStack(qbs->s1);
}
temp = TopStack(qbs->s2);
}
while (!EmptyStack(qbs->s2))
{
PushStack(qbs->s1, TopStack(qbs->s2));
PopStack(qbs->s2);
}
return temp;
}
- 队列的初始化:差点把这个给忘了,这个简单,直接将两个栈初始化就行了。
void InitQueueB2S(QueueB2S* qbs)
{
assert(qbs);
InitStack(qbs->s1);
InitStack(qbs->s2);
- 哈哈哈,我又忘了告诉大家结构体了
typedef struct QueueB2S{
Stack* s1;
Stack* s2;
}QueueB2S;
最后上面代码需要栈的代码,我这儿就不写了,大家明白两个栈是如何构成一个队列这个思想就好了。
如果有错误,欢迎下方留言讨论