逻辑结构之二受限线性表

与一般线性表不同，受限线性表指的是操作受限的线性表，比如：栈，栈是一种只允许在一端进行操作的线性表。

1.栈

栈是只允许在一端进行插入或删除操作的线性表。在栈顶是线性表允许进行插入删除操作的一端，栈底是固定的，不允许进行插入和删除操作的一端。

1.1栈的性质

性质一：后进先出（LIFO），栈中元素按照 "后进先出" 的顺序进行添加和删除。也就是说，最后压入栈的元素在栈顶，而最先压入栈的元素在栈底，只有栈顶元素可以进行访问和操作。

性质二：封闭性，由于每个栈在内存中都是独立的实体，因此栈s1内的操作不会影响栈s2，因此它们是封闭的。

性质三：限制性，即栈中元素的数量有一定的限制。当栈已满时，继续压入元素将导致栈溢出；当栈为空时，继续弹出元素将导致栈下溢。

性质四：两个基本操作，push和pop，即入栈和出栈。

除此之外，还有栈的卡特兰数等等，n个不同的元素进栈，出栈元素的排列个数为1/n*Cⁿ_2n，卡特兰数的递推式为C_n=C_n-1*(4n-2)/(n+1)，且C₁=1，可用数学归纳法证明。

思路如下：假设入栈标记为+1，出栈标记为-1，对于总的出栈数Cⁿ_2n(2n为n个元素出栈入栈的总次数，即从2n个位置中选n个出栈)；而对于非法出栈的序列个数Cⁿ⁺¹_2n，因为栈的合法出栈序列必须使得前缀和为0，例如三个元素+1+1+1-1-1-1，只有在所有-1之前有一个+1，才合法，即元素出栈之前必须有相应的元素入栈。所以当第一个前缀和为-1时，即为非法输出，例如：-1+1-1+1-1+1为序列a，对于每一种非法序列将第一个前缀和为-1对应为其相反序列，如+1+1-1+1-1+1为序列b。将三个元素放大到n个元素，可以看出来对于每种非法序列a都有一个一一对应的序列b，而序列b的个数为Cⁿ⁺¹_2n(即从2n个位置中找到n+1个位置)，所以非法的输出序列数为Cⁿ⁺¹_2n。所以总的合法序列数为总的出栈数减去非法出栈数：Cⁿ_2n-Cⁿ⁺¹_2n=1/n*Cⁿ_2n。

1.2栈的顺序存储结构

采用顺序存储的栈称为顺序栈，利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针top指示当前栈顶元素的位置。（根据定义可以看出，与顺序表不同的是，顺序表可在任意位置i处进行随机存取，而顺序栈只能在栈顶top处进行操作。）

因此栈的顺序存储类型描述类似

#define MaxSize 50	//定义栈中的最大元素个数
typedef struct{
	Elemtype data[MaxSize];	//存放栈中元素
  int top;								//栈顶指针
}SqStack;									//顺序栈的类型定义

1.2.1顺序栈的操作

由于顺序栈的操作受栈中存储单元的约束，可能发生栈的上溢，或下溢，所以必须对异常进行及时报告和处理。

1.初始化

void InitStack(SqStack &S){
	S.top = -1;		//指向当前栈顶元素的位置
 	//若初始化栈顶指针为0，则规定指针指向栈顶元素的下一个位置
  //不同栈顶指针初始化，对应有不同的操作
}

2.进栈

bool Push(SqStack &S, Elemtype x){
	if(S.top == MaxSize - 1)
  	return false;
  S.data[++S.top] = x;	//指针初始为-1，即指针先加1，再入栈
  //若指针初始为0，即先入栈，指针再加1：S.data[top++] = x;
	return true;
}

3.出栈

bool Push(SqStack &S, Elemtype &x){
	if(S.top == -1)
  	return false;
  x = S.data[S.top--];	//先出栈，指针再减1
	return true;
}

1.2.2共享栈

利用栈底位置相对不变的特性，可以让两个顺序栈共享一个连续的存储空间，将两个栈的栈底分别设置在共享空间的两端，而栈顶向共享空间的中间延伸。共享栈是为了更有效地占用存储空间，两个栈的空间相互调节，只有栈满时，才可能发生上溢。

设栈1的栈顶指针top=-1，栈2的栈顶指针top=MaxSize；仅当栈顶指针的差为1时栈满；对于栈1，栈顶指针先加1再入栈，对于栈2，栈顶指针先减1再入栈，对于出栈操作则相反。

1.3栈的链式存储结构

采用链式存储的栈叫作链栈，链栈的优点是便于多个栈共享存储空间和提高其效率(类似共享栈)，且不存在上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。类似的，链栈也有带头结点与不带头节点的操作区别，但只能用头插法，这是栈的特性。

栈的链式存储类型描述如下

typedef struct Linknode{
	ElemType data;					//数据域
  struct Linknode *next;	//指针域
}*LiStack;

2.队列

队列也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除，即入队和出队。

2.1队列的性质

性质一：先进先出（FIFO），这意味着最先插入的元素是第一个被删除的元素。与日常生活的排队相同，先排先得。

性质二：封闭性，由于每个队列在内存中都是独立的实体，因此队列q1内的操作不会影响队列q2，因此它们是封闭的。

性质三：队列具有一个max-size属性，用来限制队列的最大容量，防止内存泄漏。

性质四：两个基本操作，enqueue和dequeue，即入队和出队。

2.2队列的顺序存储结构

队列的顺序存储是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front，指向队头元素；队尾指针rear，指向队尾元素的下一个位置(为了操作与队头指针front一致，当然也可以指向队尾元素)。

队列的顺序存储可描述为(与顺序表类似)

#define MaxSize 50	//定义队列中的最大元素个数
typedef struct{
	Elemtype data[MaxSize];	//存放队列元素
  int front, rear;				//队头指针，队尾指针
}SqQueue;									//顺序队列的类型定义

初始时：Q.front==Q.rear==0；进队操作：队不满Q.rear<MaxSize，先送元素进队，再将队尾指针加1；出队操作：队不空Q.rear>0，先送元素出队，再将队头指针加1。

由于队列的入队操作和出队操作都会导致队列指针加1，无法回到初始状态，即Q.front==Q.rear==0，所以会导致队列空间只能使用一次，此时再入队会出现溢出，但这是一种假溢出。

2.2.1循环队列

由于顺序队列假溢出的缺点，我们将顺序队列臆想成一个环状空间，把顺序队列成逻辑上视为一个环，称为循环队列。当队头指针front或队尾指针rear的值为MaxSize-1时，元素再出队或入队，就将其值设为0。

初始时：Q.front==Q.rear==0；进队操作：队不满，先送元素进队，再将Q.front=(Q.front+1)%MaxSize；出队操作：队不空，先送元素出队，再将Q.rear=(Q.rear+1)%MaxSize；队列长度为(Q.rear+MaxSize-Q.front)%MaxSize。显然，这是队空和队满的条件可能都是Q.front=Q.rear=0，我们考虑特殊情况没有出队只有入队，队满时Q.rear也为0，即(Q.rear+1)%MaxSize为0。

为了区分队空还是队满的情况，有以下几种处理方式：

1.牺牲一个存储单元，当队头指针在队尾指针的下一个位置时为队满的标志，即入队元素为MaxSize-1时队满，(Q.rear+1)%MaxSize==Q.front。初始条件和队列元素的个数求法不变。

2.在循环队列的类型描述中额外设置一个size以记录队列中元素个数，Q.size=0时队空，Q.size=MaxSize时队满，且此时都有Q.front==Q.rear。

2.2.3循环队列的操作

1.初始化

void InitQueue(SqQueue &Q){
	Q.front = Q.rear = 0;
}

2.入队

bool EnQueue(SqQueue &Q, Elemtype x){
	if( (Q.rear+1) % MaxSize == Q.front )		//队满
  	return false;
  Q.data[Q.rear] = x;
  Q.rear = (Q.rear + 1) % MaxSize;
	return true;
}

3.出队

bool DeQueue(SqQueue &Q, Elemtype &x){
	if(Q.rear == Q.front)	//队空
  	return false;
  x = Q.data[Q.front];
  Q.front = (Q.front + 1) % MaxSize;
	return true;
}

4.判队空

bool isEmpty(SqQueue &Q){
	if(Q.rear == Q.front)
  	return true;
  else
  	return false;
}

2.3队列的链式存储结构

队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。队头指针指向队头节点，队尾指针指向队尾节点(这里与顺序存储不同)。链队列通常为带头结点的单链表，这样是为了插入和删除操作的统一。

队列的链式存储代码描述如下

typedef struct LinkNode{	//定义链队列的节点类型
	ElemType data;					//数据域
  struct LinkNode *next;	//指针域
}LinkNode;

typedef struct{						//定义链式队列
	LinkNode *front, *rear;	//指向节点的队头指针和队尾指针
}LinkQueue;

2.3.1链式队列的操作

1.初始化

void InitQueue(LinkQueue &Q){
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
  Q.front->next = NULL;
}

2.判队空

bool isEmpty(LinkQueue &Q){
	if(Q.rear == Q.fron)
  	return true;
  else
  	return false;
}

3.入队

bool EnQueue(LinkQueue &Q, Elemtype x){
  LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
  s->data = x;
  s->next = NULL;			//创建新节点
  Q.rear->next = s;		//插入队尾
  Q.rear = s;					//将尾指针指向最后一个节点
	return true;
}

4.出队

bool DeQueue(SqQueue &Q, Elemtype &x){
	if(Q.rear == Q.front)	//队空，也可调用isEmpty();
  	return false;
  LinkNode *p = Q.front->next;
  x = p->data;
  Q.front->next = p->next;	//将头节点指向新的队头节点
  if(Q.rear == p)
  	Q.rear = Q.front;				//只有一个节点，删除后变空队列
  free(p);							//释放原来的队头节点
	return true;
}

2.4双端队列

双端队列是指允许双端都可以进行入队和出队操作的队列，其队列的两端分别称为前端和后端，两端都可以都可以入队和出队。

也有操作受限的双端队列，即在一端允许插入和删除，但另一端只允许删除的双端队列称为输入受限的双端队列，另一端只允许插入的双端队列称为输出受限的双端队列。若限定双端队列中的元素只能从插入的一端进行删除，则该双端队列就蜕变为两个栈底相邻接的栈。

双端队列进队时，前端进的元素在后端进的元素的前面；出队时，先出队的元素在后出队的元素前面。

3.栈和队列的应用

3.1栈的应用

3.1.1栈在括号匹配中的应用

括号匹配在编译原理中是一个基本问题。算法的基本思想如下：

1.初始设置一个空栈，顺序读入括号；

2.若是右括号，则读取栈顶元素，栈顶元素是左括号则匹配，否则属于不合法的情况，括号不匹配，退出程序。

3.若是左括号，则将其压入栈中。算法结束时，栈为空，则括号序列匹配成功，否则括号序列匹配失败。

3.1.2栈在表达式求值中的应用

表达式求值是编译原理中一个最基本的问题，它的实现是栈应用的一个典型范例。对于常规的中缀表达式而言，不仅要依赖于运算符的优先级，而且还有处理括号；而后缀表达式的运算符在操作数的后面，在后缀表达式中已考虑了运算符的优先级，没有括号，只有操作数和运算符。中缀表达式转换为后缀表达式，可以与原算式的表达式树的后序遍历来比较。

通过后缀表达式计算表达式值的过程：顺序扫描表达式的每一项，然后根据根据它的类型进行对应的操作：若该项是操作数，则将其压入栈中；若该项是操作符<op>，则连续从栈中退出两个操作数Y和X，形成运算指令X<op>Y，并将计算结果重新压入栈中。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。

3.1.3栈在递归中的应用

递归是一种重要的程序设计方法。若在函数、过程或数据结构的定义中又应用了它自身，则称这个函数、过程或数据结构是递归定义的，简称递归。它通常是把一个大型的复杂问题层层转换为一个与原问题相似的规模较小的问题来求解；递归策略只需少量的代码就可以描述出解题过程中所需要的多次重复计算，很大程度上减少的代码量，但是通常情况下的效率都不高。

递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题。在递归调用的过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，而其效率不高的原因就在于每一层的递归调用过程都包含了很多重复的计算。虽然递归效率低下，但是代码简单。

3.1队列的应用

3.1.1队列在层次遍历中的应用

该过程的简单描述如下：

1.根节点入队；

2.若队空(所有节点都处理完毕)，则结束遍历。否则重复3操作；

3.队列中第一个节点入队，并访问之。若其有左孩子，则将左孩子入队；若其有有孩子，则将有孩子入队，返回2操作。

3.1.2队列在计算机系统中的应用

队列在计算机系统中的应用非常广泛，如：解决主机与设备之间速度不匹配的问题；解决由多用户引起的资源竞争问题。