两个栈实现一个队列C

首先明白两个概念

栈：先入后出

队列：先入先出

我们规定入栈1，出栈2

入：入栈1

出：此时分为两种情况。

若栈2为空，则将栈1所有元素移入栈2，从栈2栈顶出即可

若栈2不为空，直接从栈2栈顶出即可

以下为代码实现：

初始化

void my_Init_queue(PTSTqueue pq) {
	assert(pq != NULL);
	Init_Stack(&pq->s1);
	Init_Stack(&pq->s2);
}

由于是两个栈实现一个队列，直接调用栈的初始化即可

入队 

bool my_Push(PTSTqueue pq, int val) {
	assert(pq != NULL);
	return Push(&pq->s1, val);
}

统一往栈1中入

出队

bool my_Pop(PTSTqueue pq, int* rtval) {
	assert(pq != NULL);
	if (my_IsEmpty(pq)) {
		return false;
	}
	if (IsEmpty(&pq->s2)) {
		while (!IsEmpty(&pq->s1)) {
			int temp = 0;
			Pop(&pq->s1, &temp);
			Push(&pq->s2, temp);
		}
	}
		return Pop(&pq->s2, rtval);
}

先判断栈2是否为空，为空的话讲栈1所有元素移入栈2

出栈2栈顶元素即可

这里，我们传入rtval 用来接收出栈的元素

获取队头元素

bool my_Top(PTSTqueue pq, int* rtval) {
	assert(pq != NULL);
	if (my_IsEmpty(pq)) {
		return false;
	}
	if (IsEmpty(&pq->s2)) {
		while (!IsEmpty(&pq->s1)) {
			int temp = 0;
			Pop(&pq->s1, &temp);
			Push(&pq->s2, temp);
		}
	}
	return Top(&pq->s2, rtval);
}

此处与出队操作类似，只是少了最后一步Pop

其他函数

//获取有效值个数
int my_Get_length(PTSTqueue pq) {
	assert(pq != NULL);
	return Get_length(&pq->s1) + Get_length(&pq->s2);
}

//判空
bool my_IsEmpty(PTSTqueue pq) {
	return (IsEmpty(&pq->s1) && (IsEmpty(&pq->s2)));
}

//清空
void my_Clear(PTSTqueue pq) {
	Clear(&pq->s1);
	Clear(&pq->s2);
}

//销毁
void my_Destroy(PTSTqueue pq) {
	Destory(&pq->s1);
	Destory(&pq->s2);
}

//打印	先反向打印栈2 再打印栈1 此时打印顺序与出队顺序相同
void my_Show(PTSTqueue pq) {
	for (int i = Get_length(&pq->s2) - 1; i >= 0; i--) {
		printf("%d ", pq->s2.base[i]);
	}
	Show(&pq->s1);
}