两个栈实现一个队列

我先来简单的介绍一下栈和队列

  • :一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。不含任何元素的栈称为空栈,栈又称为后进先出的线性表。
    两个栈实现一个队列

  • 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表

  • 进行插入操作的一端称为队尾(入队列)

  • 进行删除操作的一端称为队头(出队列)

  • 队列具有先进先出(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;

最后上面代码需要栈的代码,我这儿就不写了,大家明白两个栈是如何构成一个队列这个思想就好了。
如果有错误,欢迎下方留言讨论