数据结构：栈和队列.pptVIP

练习题 设有4个元素1、2、3、4依次进栈，而出栈操作可随时进行（进出栈可任意交错进行，但要保证进栈次序不破坏1234的相对次序），请写出所有不可能的出栈次序和所有可能的出栈次序。 如入栈序列为123456,则能否得到出栈序列435612和135426 作 业 1. 试编写一个算法，判断依次读入的一个以@为结尾符的字母序列，是否为形如“序列1序列2”模式的字符序列，其中序列1和序列2中都不含字符，且序列2是序列1的逆序列。例如，‘a+bb+a’是属于该模式的字符序列，而‘1+33-1’则不是。（高教P102 5） 2.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、出队列、入队列的算法。（高教P102 7） 数 据 结 构 栈和队列 2 队列 ① 链队列 ——链式映象 ——顺序映象 ② 循环队列 数 据 结 构 栈和队列 2 队列 ① 链队列 a1 a2 ai-1 ai an ∧ … … rear front 非空的链队列 front 空的链队列 rear 数 据 结 构 栈和队列 2 队列 ① 链队列 typedef struct node { QueueElementType data; struct node *next; } LinkQueueNode; typedef struct { LinkQueueNode *front; LinkQueueNode *rear; } LinkQueue; LinkQueue *Q; 数据结构定义 数 据 结 构 栈和队列 2 队列 链队列 int InitQueue(LinkQueue *Q) { Q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(Q-front!=NULL) { Q-rear=Q-front; Q-front-next=NULL; return(TRUE); } else return(FALSE); } ①初始化 数 据 结 构 栈和队列 2 队列 链队列 int EnterQueue(LinkQueue *Q，QueueElementType x) { LinkQueueNode * NewNode； NewNode =(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL) { NewNode-data=x; NewNode-next=NULL; Q-rear-next=NewNode; Q-rear=NewNode; return(TRUE); } else return(FALSE); } ②入队 数 据 结 构 栈和队列 2 队列 链队列 int DeleteQueue(LinkQueue *Q，QueueElementType x) { LinkQueueNode * p； if(Q-front==Q-rear) return(FALSE); p=Q-front-next; Q-front-next=p-next; *x=p-data; free(p); return(TRUE); } ③出队 数 据 结 构 栈和队列 2 队列 ② 循环队列 0 1 2 3 4 6 5 7 rear front 空循环队列 0 1 2 3 4 6 5 7 rear front 满循环队列 a1 a7 a6 a5 a4 a3 a2 a8 0 1 2 3 4 6 5 7 rear front 一般循环队列 a1 a5 a4 a3 a2 数 据 结 构 栈和队列 2 队列 ② 循环队列 约定：头指针指示队列中队头元素的前一个位置。 数据结构定义 typedef struct { QueueElementType element[maxsize]; int front; int rear; }SeqQueue; SeqQueue *Q; 数 据 结 构 栈和队列 2 队列 循环队列: ①初始化 void InitQueue(