【队列和栈】相关的题（数据结构期末）

题目

设定义栈的类型为Stack，队列类型为Queue；其基本操作列表如下：
（1）栈的基本操作有：初始化（InitStack），判空（EmptyS），出栈（Pop），入栈（Push）；
（2）队列的基本操作有：初始化（InitQueue），判空（EmptyQ），出队（DeQueue），入 队（EnQueue）；

若初始栈S＝｛'s‘，‘t’，‘a’，‘c’，‘k’｝，其中‘k’为栈顶，
调用FB3算法后，栈T从栈底到栈顶依次内容是什么？

void FB2(Stack S){
	//初始化
	int k=0; 
	Queue Q;
	Stack T;
	InitQueue(Q);
	InitStack(T);
	
	//①第一个while循环
	while(!EmptyS(S)){
		k++;
		if(k%2!=0){
			Pop(S,e); Push(T,e);
		} else{
			Pop(S, e); EnQueue(Q,e);
		} 
	}
	//②第二个while循环
	while(!EmptyQ(Q)){
		 DeQueue(Q,e);
		 Push(T,e); 
	}
}

画出栈S初始状态（push）

我习惯竖着画栈

S＝｛'s＇，'t'，'a'，'c'，'k'｝
//其中“k＇为栈顶

k为栈顶部，那s就是栈底喽
先把s push进栈（进栈的操作叫push）,进来就到栈底了
之后分别把t、a、c、k叠在栈里边就行

图的注解：注意看我画的线，都是从栈的最上边往下走的。手写的时候，拿着笔画画就好了，从栈的上边往下找位置，别穿。

初始化（这有点简单了吧，就是创建一个栈和队列呗）

int k=0; 
Queue Q;
Stack T;
InitQueue(Q);
InitStack(T);

Init 在编程里经常用来给一些初始化的操作起名
在函数里我们又创建了
栈T
队列Q
int k

①第一个while循环

Empty 在编程里经常用来给 判断是否为空的函数起名

//①第一个while循环
while(!EmptyS(S)){
	k++;
	if(k%2!=0){
		Pop(S,e); Push(T,e);
	} else{
		Pop(S, e); EnQueue(Q,e);
	} 
}

循环的判断语句是：!EmptyS(S)

如果S不为空的话，这个布尔表达式的结果是真还是假？
不为空，EmptyS(S)返回一个false（因为有元素嘛）
接着再 加个感叹号 ！false 不就变成 true了吗？

那什么时候会进循环？栈S不为空的时候
什么时候会出循环？栈S为空的时候。
栈S怎么就为空了？循环里边肯定有S的 pop操作(pop是出栈的操作，【脑补动画】从栈顶弹出来一个元素)
分析到这儿，就可以进循环体，里边看了。

k++，

k刚开始就初始化成0了，在这里先加加了一下，就变成一了。(不会加加怎么办？点这个)

if-else

先看布尔表达式，k%2！=0
什么时候这个式子为假？k模上2不等于0的时候。k%2为0，也就是说k除以2没有余数。那不就是当k是2的整数倍（2、4、6、8）的时候，这个式子就为真了嘛（不会模运算？点这个）
什么时候这个式子为真？k不是2的整数倍的时候，比如k为1、3、5。

分析完if的布尔表达式，我们知道了，当k为1、3、5的时候，会走if里边的语句，当k为2、4的时候，会走false里边的语句。
第一次来的时候，k是几？k是1.所以走这一句Pop(S,e); Push(T,e);
在咱学的书里边执行Pop (S,e),会弹出来栈顶的元素，赋到e身上。再Push(T,e),会把e压入栈T中
画图：S弹出来一个到T里边

图的注解：这里两步和一步，从栈S弹出来的K，直接压入到T中了。Pop操作，弹出来之后自己就没有了。

执行完Pop(S,e); Push(T,e);之后，第一次循环就结束了，开始第二次判断、循环

第二次进循环

栈S肯定不为空啊，还有4个元素呢，所以就又进来循环了
接着k++,变成2了
2%2为0，所以走else里的Pop(S,e);Enqueue(Q,e);

Enqueue 入队操作

又遇见新的操作了——Enqueue,题里说这是入队
下面咱先看看入队的图解

如果把数组[1,2,3,4,5]，挨着Enqueue 入队，入完之后，队列就是[1,2,3,4,5]。
如果把队列[1,2,3,4,5],挨着出队到一个数组，出完之后，数组还是[1,2,3,4,5]。
队列和排队买饭挺像的其实，先到先得，后来的后边儿排队。
队列，我自己学二叉树的时候，有一种层序遍历需要用到队列，以及图论的广度优先搜索。

学完队列，咱回来接着看else里的语句

else里的Pop（S,e）；EnQueue(Q,e)

先是Pop(S,e),不就是再从S里弹出一个元素嘛
然后把弹出的元素 Enqueue 入队到Q

小技巧：队列横着画，从前往后排；栈要竖着画，进出都从最上边。

之后的操作

之后不就是再接着循环嘛，k再++，然后再走if判断，看是走if还是走else，再继续画图弹栈入栈、入队。就走完第一个while了

因为一会儿讲第二个循环还得用，所以我在这儿再写一下 出第一个循环时的状态
栈：S[]
栈：T[k，a，s]
队列：Q[c，t]

②第二个while循环

//②第二个while循环
while(!EmptyQ(Q)){
	 DeQueue(Q,e);
	 Push(T,e); 
}

判断进循环的条件（！EmptyQ(Q)）

EmptyQ(Q), 如果队列Q为空，就会返回true，如果队列Q不为空，就返回false
理解性记忆Empty返回结果的真假：我自己学Java的时候，里面判断为不为空的方法叫isEmpty(),返回值其实说的是 这个函数名——一个命题的真假，如果这个集合为空，那它确实是空的 it is Empty，如果不为空，it isn’t empty。你能读出来这里边蕴含着肯定和否定的语气吗？

包括我们判断，！EmptyQ（Q）的真假也一样。简单理解“！” 你就读成“不”，“Empty” 不就是空吗？
和一块儿 “！Empty”=不空，我们都是中国人，都知道这句话肯定要补全的，不然就成病句了，肯定要补上是谁不空呀，不就是Q吗？
Q不空
再把“while”读成当，（它在英语里确实是这个意思）
那"while(!EmptyQ(Q)",连一块儿读，不就是当（Q）不为空的时候吗？

也就是当Q不为空的时候，就会进循环。而且循环里边，一定有出队的操作，不然就死循环了。

DeQueue出队（从前往后出，参考打饭）

while循环里边儿，一共就两句，一句Dequeue是用来出队Q的，一句是Push是用来把 从Q里出来的元素 压入T中的
这里边儿也没有额外的判断条件，所以这两行代码的意思不就是：把Q里边所有的元素出队之后压入T中吗？

回顾

怎么画栈和队列？栈要竖着画，队列要横这画

Pop是什么意思？出栈，从栈顶弹出一个元素

Push是什么意思？

Enqueue是什么意思？

Dequeue是什么意思？

Empty时候返回真？