线性表--队列-1

主要内容

1. 队列基础练习题

一.队列基础练习题

1.用链式存储方式的队列进行删除操作时需要 ( D ).

A.仅修改头指针
B.仅修改尾指针
C.头尾指针都要修改
D.头尾指针可能都要修改

代码如下（示例）:

队列用链式存储时，删除元素从表头删除，通常仅需修改头指针，
但若队列中仅有一个元素则尾指针也需要被修改，
当仅有一个元素时，删除后队列为空，需修改尾指针为 rear=front。
1
2
3

2.若以1,2,3,4作为双端队列的输入序列，则既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是( C )

A.1,2,3,4
B.4,1,3,2
C.4,2,3,1
D.4,2,1,3

代码如下（示例）:

使用排除法。先看可由输入受限的双端队列产生的序列:
设右端输入受限，1,2,3,4 依次左入，则依次左出可得 4,3,2,1，排除 A;
右出、左出、右出、右出可得到4,1,3,2，排除 B;
再看可由输出受限的双端队列产生的序列:
设右端输出受限，1,2,3,4 依次左入、左入、右入、左入依次左出可得到 4,2,1,3，排除 D
1
2
3
4
5

3.现有队列Q与栈 S,初始时Q中的元素依次是 1,2.3,5,6(1在队头).S 为空。若仅允许下列3 种操作: (1) 出队并输出出队元素;(2)出队并将出队元素入栈:(3)出栈并输出出栈元素，则不能得到的输出序列是 ( C )。

A.1,2,5,6,4,3
B.2,3,4,5,6,1
C.3,4,5,6,1,2
D.6,5,4,3,2,1

代码如下（示例）:

A 的操作顺序为11221133。
B 的操作顺序为2111113。
D 的操作顺序为22222133333。
对于 C: 首先输出3，说明 1和2 必须先依次入栈，而此后2肯定比1先输出，
因此无法得到 1,2的输出顺序
1
2
3
4
5

4.Q是一个队列，S 是一个空栈，实现将队列中的元素逆置的算法

代码如下（示例）:

本题主要考查对队列和栈的特性与操作的理解。
由于对队列的一系列操作不可能将其中的元素逆置，而栈可以将入栈的元素逆序提取出来，
因此我们可以让队列中的元素逐个地出队列，入栈;全部入栈后再逐个出栈，入队列。

void Inverser(Stack &S,Queue &Q){
//本算法实现将队列中的元素逆置
	while(!QueueEmpty(Q)){
		x=DeQueue(O);  //队列中全部元素依次出队
		Push(S，x);  //元素依次入栈
	}
	while(!StackEmpty(S)){
		PoP(S,x);  //栈中全部元素依次出栈
		EnQueue(Q，x);  //再入队
	}
}

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

5.利用两个栈 S1，S2来模拟一个队列，已知栈的4个运算定义如下:

Push(S,x);  //元素x入栈s
Pop(S,x);  //s出栈并将出栈的值赋给 x
StackEmpty(s);  //判断栈是否为空
StackOverflow(S);  //判断栈是否满
1
2
3
4

如何利用栈的运算来实现该队列的 3 个运算(形参由读者根据要求自己设计)?

Enqueue;  //将元素x入队
Dequeue;  //出队，并将出队元素存储在x中
QueueEmpty;  //判断队列是否
1
2
3

代码如下（示例）:

利用两个栈S1和 s2来模拟一个队列，当需要向队列中插入一个元素时，
用S1 来存放已输入的元素，即 S1 执行入栈操作。
当需要出队时，则对 S2 执行出操作。
由于从栈中取出元素的顺序是原顺序的逆序，所以必须先将 S1 中的所有元素全部出栈并入栈到 S2 中，
再在 S2 中执行出栈操作，即可实现出队操作，
而在执行此操作前必须判断 S2 是否为空，否则会导致顺序混乱。当栈S1和s2都为空时队列为空。

总结如下:
1)对S2的出找操作用做出队，若s2为空，则先将是s1中的所有元素送入s2
2)对 s1的入操作用作入队，若 S1 满，必须先保证s2为空，才能将s1中的元素全部插入S2中。
1
2
3
4
5
6
7
8
9
10

入队算法：

入队算法

int EnQueue(Stack Sl,Stack &S2,ElemType e){
	if(!stackOverflow(s1)){
		Push(S1,e);
		return 1;
	}
	if(StackOverflow(S1)&!StackEmpty(s2)){
		printf("队列满");
		return 0;
	}
	if(StackOveflow(S1)&sStackEmpty(S2)){
		while(!stackEmpty(S1)){
			Pop(S1.x);
			Push(S2,x);
		}
	}
	Push(s1,e);
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

出队算法：

void DeQueue(Stack &S1,Stack &S2,ElemType &x){
	if(!StackEmpty(s2)){
		Pop(S2，x);
	}
	else if(StackEmpty(S1)){
		printf("队列为空");
	}
	else{
		while(!stackEmpty(S1)){
			Pop(S1,x);
			Push(S2，x);
		}
	Pop(S2,x);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

判断队列为空的算法：

int QueueEmpty(Stack Sl,Stack s2){
	if(StackEmpty(s1)&&StackEmpty(S2))
		return 1;
	else
		return 0;
}
1
2
3
4
5
6

---

总结

以上是今天要讲的内容，练习了线性表–队列的相关习题。