用栈模拟队列

【例】请利用两个栈s1和 s2来模拟一个队列，假设栈中元素为 int 型，栈中元素最多为maxSize。已知栈的3个运算定义如下。

1. push(ST,x)：元素 x 入ST栈。
2. pop(ST,&x)：ST栈顶元素出栈，赋给变量x。
3. isEmpty(ST):判断ST栈是否为空。

如何利用栈的运算来实现该队列的3个运算：enQueue（元素入队列)、deQueue（元素出队列)、isQueueEmpty （判断队列是否为空，空返回1，不空返回0)。采用C语言描述算法

• 入队

void enQueue(StStack &s1,StStack &s2,int x,int value){
	if(isEmpty(s1)==0){       //说明 s1 不空,则先将其全放到 s2，再让 value 进栈
		while(isEmpty(s1)==0){
			pop(s1,&x);
			push(s2,x);
		}
	}
	push(s1,value);
	while(isEmpty(s2)==0){
			pop(s2,&x);
			push(s1,x);
	}	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 出队

//出队
int deQueue(StStack &s1,int &x){
	if(isEmpty(s1)==1)
		return 0;
	 pop(s1,&x);		
}
1
2
3
4
5
6

• 判断队空

int isQueueEmpty(StStack s1){
	isEmpty(s1);
}
1
2
3

---

总结：将 s2 当作跳板，为 s1 服务。不理解可以看点击看🖱️哔哩哔哩视频讲解