利用两个栈sl■◆★,s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述这些运算的算法思想。

　　②每当删除一个队头元素时◆◆★■★,则依次移动队中的元素,始终使front指针指向队列中的第一个位置■◆■★◆◆。

　　若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构?为什么?

　　头指针是指在第一个结点之前的指针，它是一个链表存在的标志，是必须存在必不可少的★■■。头结点是第一个结点之前的结点★◆■■，它是为了方面在第一个结点之前进行元素的插入和删除操作，它不是必须的，并且数据域也可以不存放信息。

　　（3）优点是多个链栈一般不考虑栈的溢出。缺点是栈中元素要以指针相链接◆★■，比顺序存储多占用了存储空间。

　　（2）查找：如果是按值查找并且表无序时，顺序表和链表的时间复杂度都是O（n）◆■■，如果表有序，则可以用折半查找法■★■★◆■，时间复杂度是O（nlog2n）■■；如果是按序号查找，则顺序表支持随机查找，时间复杂度是O（1），而链表的时间复杂度是O（n）

　　应选用链式存储结构◆■◆★■★。由于链式存储结构可以用任意的存储空间来存储线性表中的各数据元素，且其存储空间可以是连续的,也可以不连续；此外，这种存储结构对元素进行插人和删除操作时都无须移动元素◆◆★■，修改指针即可，所以很适用于线性表容量变化的情况，这种动态存储结构适合于多个线性表同时共存。

　　在队列的顺序存储结构中★■◆,设队头指针为front,队尾指针rear,队的容量(存储空间的大小)为MaxSize。当有元素加入队列时■■■◆★★,若rear = MaxSize(初始时rear=0)则发生队列的上溢现象■◆■■★,不能再向队列中加入元素。所谓队列假溢出现象是指队列中还有剩余空间但元素却不能进人队列◆★◆■★■,这种现象是由于队列的设计不合理所致■◆◆。

　　若在一个函数、一个过程或者一个数据结构的定义中直接或者间接的调用了它自身，则这个函数、这个过程、这个数据结构称为是递定义的，简称为递归。

　　递归所用到的是系统管理栈★★★■◆◆，但是通常情况下★◆◆■◆，每次递归都要保留现场★★■◆◆■,空间复杂度为O(n),效率不高，当递归次数过深的时候，容易出现堆栈溢出的现象。

　　❷对于带头节点的链表，在表空时也存在一个头节点，因此空表与非空表的处理是一样的。

　　❶对于带头节点的单链表，在单链表的任何节点之前插入节点或删除都是修改前一个节点的指针域◆■■■，因为任何节点都有前驱节点（若单链表没有头节点，则首节点没有前驱节点，在其前插入节点和删除该节点时操作复杂些）

　　③采用环形队列方式■★★:把队列看成一个首尾相接的环形队列,在环形队列上进行插人或删除运算时仍然遵循■■◆◆★★“先进先出”的原则。

　　（3）插入和删除：顺序表插入和删除需要移动大量的元素，时间复杂度是O（n），链表的插入和删除只需要修改指针的位置■■■■，时间复杂度是O（1）

　　递归问题只需要少数的代码就能够描述出解题过程中所需要的多次重复计算◆◆★■,大大减少了程序的代码量，递归会让代码的结构简单、清晰，但是大量的递归调用会建立函数的副本，耗费大量的时间和内存。

　　（1）存取（读取）方式：顺序表能够随机读取和顺序读取◆★★，而链表只能按顺序读取

　　❸最终所有的元素都进栈和出栈完毕◆★，检查栈是否为空◆■★■，如果不为空，则说明还有多余的左括号没有匹配■■◆★■，因此括号匹配失败■■★★★，如果为空，则括号匹配成功。

　　（4）空间分配★★■◆★◆：顺序表的空间分配分为静态分配和动态分配，静态内存分配时，很容易导致内存溢出或者是浪费★◆，而动态内存分配时，有时候不存在一大块连续的存储空间■■★■◆，导致分配失败★◆★，并且需要移动大量的元素，效率低。而链表是直接在需要的时候申请内存，只要有内存就能够分配，操作灵活、高效◆◆。

　　（1）优点是每个栈仅用一个顺序存储空间时，操作简单。缺点是分配空间小了★★◆■，容易产生溢出，分配空间大了，容易造成浪费，各栈不能共享空间。

　　栈的特点是后进先出◆■◆★■，队列的特点是先进先出★◆★◆。所以，当用两个栈s1和s2模拟一个队列时，s1作为输入栈■■，逐个元素压栈，以此模拟队列元素的入队■◆。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。只有栈s2为空且s1也为空时，才算是队列空。

　　❷如果是右括号★■■■★■，则判断当前栈是否为空■◆■★■，如果为空，则不匹配，不为空，则看是否与栈顶的左括号匹配，如果匹配，则栈顶元素出栈

　　①采用平移元素的方法:每当队列中加入一个元素时,队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)★■■◆■◆。

　　（2）优点是多个栈仅用一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才会产生溢出★◆★。缺点是当一个栈满时要向左、右查询有无空闲单元则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时■◆◆◆★，要查询空闲单元◆★◆、移动元素和修改栈底、栈顶指针，这一过程计算复杂且十分耗时。