在绪论中，我们介绍了数据结构三要素， 第1章中，讲解了逻辑结构分类中线性结构的第一个部分——一般线性表，这章开始讲解逻辑结构线性结构的第二个部分——受限的线性表。这里先巩固下逻辑结构的分类，如下图所示：

受限线性表最简单直白的理解便是插入，删除，查找等操作时，不能随心所欲的进行，必须遵循一定的限制（规则）。

一.栈

1.1定义

栈（stack）是一种只允许在一端进行插入或删除操作的线性表。
一般规定，栈只能在栈顶进行插入，删除操作。因此访问元素的顺序是先进后出。
如下图所示：

这里介绍几个重要的概念：

• 栈顶（top）：栈的操作中，仅允许插入和删除的那一端。
• 栈底（bottom）：固定的，不允许进行插入和删除操作的那一端。
• 空栈：不含有任何元素的空线性表。

1.2基本操作

InitStack(&S)   //初始化一个空栈S
StackEmpty(S)   //判断一个栈是否为空
Push(&S,x)      //入栈，若栈未满，则将x加入使之称为新栈顶
Pop(&S,x)       //出栈，若栈非空，则弹出栈顶元素，并用x返回
GetTop(S,&x)    //读取栈顶元素，若栈S非空，则用x返回栈顶元素
ClearStack(S)   //销毁栈，并释放栈S占用的存储空间

二.队列

2.1定义

队列（Queue）简称队，只允许在线性表的一端进行插入，另一端进行删除。
一般规定，只能在队尾进行插入操作，队头进行删除操作。因此访问时的顺序是先进先出。
如下图所示：

介绍几个重要的概念：

• 队头：允许删除的一端，又称为队首。
• 队尾：允许插入的一端。
• 空队列：不含任何元素的空表。

2.2基本操作

InitQueue(&Q)   //初始化队列，构造一个空队列
QueueEmpty(&Q)  //判断队列是否为空
EnQueue(&Q,x)   //入队，若队列Q未满，将x加入，使之称为新的队尾
DeQueue(&Q,&x)  //出队，若队列Q非空，删除队头元素，并用x返回
GetHead(Q,&x)   //读取队头元素，若队列非空，则将队头元素赋值给x

三.串

3.1定义

字符串（string）简称串，是由零个或多个字符组成的有穷序列。
介绍几个重要概念：

• 串长：串中所含字符的个数
• 子串：一个串中任意个连续字符组成的子序列(含空串,但不含串本身)
• 主串：包含子串的串
• 空串：含零个字符的串，通常用 Φ 表示。

3.2基本操作

StrAssign(&T,chars)     //由字符串常量chars生成字符串T的操作。
StrCopy(&T,S)           //由串S复制生成串T的操作。 
StrCompare(S,T)         //若S=T返回0，S>T返回正数，S<T返回负数。
StrLength(S)            //返回串S的长度。 
Concat(&T,S1,S2)        //将串S1和S2连接起来生成串T的操作。 
SubString(&Sub,S,pos,len)//以串S中pos位置开始的len个字符生成子串Sub的操作。 
Index(S,T,pos)          //返回子串T在S中pos个字符以后出现的位置。 
Replace(&S,T,V)         //将串S中所有不重叠子串T替换为串V的操作。
StrInsert(&S,pos,T)     //在串S中第pos个字符前插入串T的操作。 
StrDelete(&S,pos,len)   //删除串S中第pos个字符开始的len个字符的操作