一个双端队列Deque是限定在两端，end1和end2都可以进行插入和删除的线性表。队空条件是end1=end2。若用顺序方式来组织双端队列，试根据下列要求，定义双端队列的结构，并给出在指定端 i ( i =1，2)进行插入enq和删除deq操作的实现。要求：① 当队满时，最多只能有一个元素空间可以是空的。② 在进行两端的插入和删除时，队列中其他元素是一律不动。
解 操作实现如下：FUNC add(Qu:Deque;x:datatype;tag:0..1):integer;BEGIN CASE tag OF 0:BEGIN IF(Qu.end1<>Qu.end2)THEN BEGIN Qu.elem[Qu.end1]:=x; Qu.end1:=(Qu.end1-1)MOD maxsize; RETURN((Qu.end1+1)MOD maxsize); END ELSE return(-1); END 1:BEGIN IF(Qu.end2<>Qu.end1)THEN BEGIN Qu.elem[Qu.end2]:=x; Qu.end2:=(Qu.end2+1)MOD maxsize; return((Qu.end2-1)MOD maxsize); END ELSE return(-1); ENDENDCASE;{add}ENDF;{add}FUNC delete(Qu:Deque;VAR x:datatype;tag:0..1):integer;BEGIN CASE tag OF 0:BEGIN IF(((Qu.end1+1)MOD maxsize)<>Qu.end2)THEN BEGIN i:=(Qu.end1+1)MOD maxsize; WHILE(i<>Qu.end2)AND(Qu.elem[Qu[i]]<>x)DO i:=(i+1)MOD maxsize; IF(Qu.elem[i]=x AND i<>Qu.end2)THEN BEGIN j:=i; WHILE((j-1)MOD maxsize<>Qu.end1)DO BEGIN Qu.elem[j]:=Qu.elem[(j-1)MOD maxsize]; j:=(j-1)MOD maxsize; END Qu.end1:=(Qu.end1+1)MOD maxsize;return(0); END ELSE return(-1); END ELSE return(-1); END 1:BEGIN IF(((Qu.end2-1)MOD maxsize)<>Qu.end1)THEN BEGIN i:=(Qu.end2-1)MOD maxsize; WHILE(I<>Qu.end1)AND(Qu.elem[Qu[i]]<>x)DO i:=(i-1)MOD maxsize;IF(Qu.elem[i]=x AND i<>Qu.end1)THEN BEGIN j:=i; WHILE((j+1)MOD maxsize<>Qu.end2)DO BEGIN Qu.elem[j]:=Qu.elem[(j+1)MOD maxsize]; j:=(j+1)MOD maxsize; END Qu.end1:=(Qu.end2-1)MOD maxsize; return(0); END ELSE return(-1); END{if} ELSE return(-1); END{case 1} ENDCASE;END;{delete}
举一反三
- 双端队列可以在队列的两端进行插入和删除操作，既可在队尾进行插入/删除，又可在队头进行插入/删除。现有4个不同的元素顺序输入到双端队列，那么可以得到_____种不同的排列
- 若将一个双端队列顺序表示在一维数组V[m]中，两个端点设为end1和end2，并组织成一个循环队列。试写出双端队列所用指针endl和end2的初始化条件及队空与队满条件, .并编写基于此结构的相应的插入(enqueue)新元素和删除(dlqueue)算法。
- 双端队列是一种特殊的线性表, 对它所有的插入和删除都限制在表的两端进行。 现有 4 个元素对空双端队列执行插入, 问可以得到多少种不同的双端队列状态？如果是 5 个元素，情况又是怎样？如果有[tex=0.643x0.786]/he/ol8BkDuTTL9yMPtH4Q==[/tex]个元素呢?
- 超队列是一种输出受限的双端队列，即插入限制在一端（例如end1）进行，而删除仍允许在两端进行。
- 超栈是一种输入受限的双端队列，即插入限制在一端（例如end2）进行，而删除仍允许在两端进行。
内容
- 0
关于数据结构队列的描述正确的是哪些（） A: 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作 B: 进行插入操作的端称为队尾，进行删除操作的端称为队头 C: 队列中没有元素时，称为空队列 D: 队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出
- 1
循环队列放在一维数组A[0…M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）。
- 2
队列的插入操作在()____()端进行,删除操作在()____()端进行。栈的插入操作在()____()端进行,删除操作在()____()端进行
- 3
所有插入和删除都限定在表的同一端进行的线性表称为 A: 单链表 B: 栈 C: 队列 D: 双端队列
- 4
【判断题】栈和队列的不同点是栈只能在一端进行插入删除操作,而队列在不同端进行插入删除操作。