网站开发的需求分析书,如何韩国视频网站模板下载 迅雷下载地址,深圳西乡固戍招聘信息,建设银行苏州网站三、栈、队列和数组
3.1 栈
3.1.1 栈的基本概念
线性表是具有相同数据类型的n#xff08;n≥0#xff09;个数据元素的有限 序列#xff0c;其中n为表长#xff0c;当n 0时线 性表是一个空表。若用L命名线性表#xff0c;则其一般表示为 L (a1, a2, … , ai , ai1, ……三、栈、队列和数组
3.1 栈
3.1.1 栈的基本概念
线性表是具有相同数据类型的nn≥0个数据元素的有限 序列其中n为表长当n 0时线 性表是一个空表。若用L命名线性表则其一般表示为 L (a1, a2, … , ai , ai1, … , an)
栈Stack是只允许在一端进行插入或删除操作的线性表 逻辑结构与普通线性表相同 数据的运算插入、删除操作有区别
重要术语栈顶、栈底、空栈 栈顶允许插入 和删除的一端 (最后进的即最上面的为栈顶元素) 栈底不允许插 入和删除的一端(最先进的即最下面的为栈底元素) 空栈不含任何元素的栈
特点后进先出(后进栈的元素先出栈) 记为LIFO (Last In First Out)
栈的基本操作
InitStack(S)初始化栈。构造一个空栈 S分配内存空间。DestroyStack(S)销毁栈。销毁并释放栈 S 所占用的内存空间。Push(S,x)进栈若栈S未满则将x加入使之成为新栈顶。Pop(S,x)出栈若栈S非空则弹出栈顶元素并用x返回。GetTop(S, x)读栈顶元素。若栈 S 非空则用 x 返回栈顶元素
其他常用操作
StackEmpty(S)判断一个栈 S 是否为空。若S为空则返回true否则返回false
栈的常考题型 进栈顺序为 a à b à c à d à e 有哪些合法的出栈顺序
3.1.2 栈的顺序存储实现
顺序栈的定义
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ ElemType data[MaxSize]; //静态数组存放栈中元素 int top; //栈顶指针 用于指向此时栈中的栈顶元素 一般用来记录数组的下标
}SqStack;void testStack(){ SqStack S; //声明一个顺序栈(分配空间)
}顺序存储给各个数据元素分配连续的存储空间大小为MaxSize*sizeof(ElemType)
初始化操作
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ ElemType data[MaxSize]; //静态数组存放栈中元素int top; //栈顶指针
}SqStack;// 初始化栈
void InitStack(SqStack S){ S.top -1; //初始化栈顶指针
}void testStack(){SqStack S; //声明一个顺序栈(分配空间)InitStack(S);//...后续操作...
}// 判断栈是否为空
bool StackEmpty(SqStack S){ if(S.top -1) //栈空return true; else //不空return false;
}进栈操作
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize]; //静态数组存放栈中元素int top; //栈顶指针
}SqStack; // 新元素进栈
bool Push(SqStack S, ElemType x){ // 判断栈是否已满 满了报错 if(S.top MaxSize - 1) return false; S.top S.top1; //指针先加1S.data[S.top]x; //新元素入栈 把x存到top指针所在的位置return true;
}S.top S.top1; //指针先加1S.data[S.top]x; //新元素入栈 把x存到top指针所在的位置上面两句代码等价于S.data[S.top]x; //top表示先让top的值加1 再来使用top 出栈操作
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ElemType data[MaxSize]; //静态数组存放栈中元素int top; //栈顶指针
}SqStack; // 出栈
bool Pop(SqStack x, ElemType x){ // 判断栈是否为空 if(S.top -1) //栈空报错return false; x S.data[S.top--]; return true;
}x S.data[S.top--]; 等价于xS.data[S.top]; //栈顶元素先出栈S.topS.top-1; //指针再减1top指针减1 数据还残留在内存中指示逻辑上被删除了
栈顶指针S.top,初始化时设置S.top-1;栈顶元素S.data[S.top] 进栈操作栈不满时栈顶指针先加1再送值到栈顶 出栈操作栈非空时先取栈顶元素再将栈顶指针减1 栈空条件S.top-1,栈满条件S.topMaxSize-1栈长S.top1
读取栈顶元素
// 读栈顶元素
bool GetTop(SqStack S, ElemType x){ if(S.top -1) //栈空 报错 return false; x S.data[S.top]; //x记录栈顶元素 和出栈操作基本一样唯一区别是这里top不需要-- return true;
}仅为读取栈顶元素并没有出栈操作因此原栈顶元素依然保留在栈中共享栈利用栈底位置相对不变的特性让两个顺序栈共享一个一维数组空间 将两个栈的栈底分别设置在共享空间的两端两个栈顶向共享空间的中间延伸
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{ ElemType data[MaxSize]; //静态数组存放栈中元素 int top0; //0号栈栈顶指针 int top1; //1号栈栈顶指针
}ShStack;// 初始化栈
void InitSqStack(ShStack S){ S.top0 -1; //初始化栈顶指针S.top1 MaxSize;
}/*仅当两个栈顶指针相邻(top1-top01)时判断为栈满
0号栈进栈时top0先加1再赋值
1号栈进栈时top1先减1再赋值
出栈时则相反*/
栈满的条件top0 1 top1
共享栈是为了更有效地利用存储空间两个栈的空间相互调剂只有在整个存储空间被占满时才发生上溢其存取数据的时间复杂度为O(1)所以对存取效率没有什么影响
3.1.3 栈的链式存储实现
采用链式存储的栈称为链栈链栈的优点是便于多个栈共享存储空间和提高其效率且不存在栈满上溢的情况通常采用单链表实现并规定所有操作都是在单链表的表头进行的
链栈的定义 和单链表的定义几乎没差别
typedef struct Linknode{ ElemType data; //数据域 Linknode *next; //指针域
}*LiStack;void testStack(){ LiStack L; //声明一个链栈
}采用链式存储便于结点的插入与删除。链栈的操作与链表类似入栈和出栈的操作都在链的表头进行。需要注意的是对于带头结点和不带头结点的链栈具体的实现会有所不同。
链栈的初始化
typedef struct Linknode{ ElemType data; Linknode *next;
}*LiStack;// 初始化栈
bool InitStack(LiStack L){ L (Linknode *)malloc(sizeof(Linknode)); if(L NULL) return false; L-next NULL; return true;
}// 判断栈是否为空
bool isEmpty(LiStack L){ if(L-next NULL) return true; else return false;
}入栈出栈
// 新元素入栈
bool pushStack(LiStack L,ElemType e){ Linknode *s (Linknode *)malloc(sizeof(Linknode)); if(s NULL) //内存分配失败 return false; s-data e; //用结点s保存数据元素es-next L-next; //头插法 L-next s; //把s结点连到L后return true;
}// 出栈
bool popStack(LiStack L, int e){ if(L-next NULL) // 栈空不能出栈 return false; Linknode *s L-next; x s-data; L-next s-next;free(s); return true;
}
