一、栈先言栈遵循后进先出last in first outLIFO的原则。常见场景1.函数调用管理栈用于管理函数调用包括存储局部变量和返回地址。当一个函数调用另一个函数时当前函数的状态被推入栈中待调用的函数完成后从栈中弹出状态恢复执行。2.撤销操作在文本编辑器或其他应用程序中栈用于实现撤销操作。每次用户进行操作时操作会被推入栈中用户可以通过弹出栈中的操作来撤销最近的操作。3.浏览器历史管理栈可以用于管理浏览器的历史记录。当用户访问新页面时当前页面的地址被推入栈中用户按“后退”按钮时最近访问的页面被弹出并加载。4.字符串反转使用栈可以轻松地实现字符串的反转将字符串中的字符逐个推入栈中然后再依次弹出。5.深度优先搜索一个分支搜到底之后再进行下一个分支1.1 常见函数命名数据类型栈使用的数据类型为D{ai|ai∈ElemSet, i1,2,…,n,n ≥ 0}。•基本操作1.InitStack(*S)初始化一个空栈 S。2.DestroyStack(*S)销毁栈 S。3.ClearStack(*S)清空栈 S 中的所有元素。4.StackEmpty(S)检查栈 S 是否为空。如果为空返回 TRUE否则返回 FALSE。5.StackLength(S)返回栈 S 中元素的个数。6.GetTop(S, *e)返回栈 S 顶端的元素并将其赋值给 e。7.Push(*S, e)将元素 e 压入栈 S 的顶端。8.Pop(*S, *e)将栈 S 顶端的元素弹出并将其赋值给 e。9.StackTraverse(S, visit())从栈顶到底部遍历栈 S并对每个元素应用 visit() 函数。如果 visit() 函数失败则遍历停止。1.2 初始化栈Status I nitStack(SqStack *S){ //构造一个空栈 S-base(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S-base) exit(OVERFLOW); S-topS-base; S-stacksizeSTACK_INIT_SIZE; return OK; } Status GetToop(SqStack *S,SElemType *e){ //若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR if(S-topS-base) return ERROR; *e*(S-top-1); return OK;S-top S-base S-stacksize必须使用旧的stacksize因为realloc后top需要指向旧栈顶的下一个位置新空间的起点而S-stacksize更新后指向的是新空间的末尾会导致top定位错误*S-top e确实是先在旧的top指向的位置空闲位置赋值e然后将top后移一位使其指向新的栈顶下一个空闲位置。top是指向最后一个元素的最后一个位置也是下一个元素位置的起点1.3 出栈和入栈Status Push(SqStack *S,SElemType e){ //插入元素e为新的栈顶元素 if(S-top-S-baseS-stacksize){ S-base(SElemType *)realloc(S-base,(S-stacksizeSTACKINCREMENT)*sizeof(SElemType)); if(!S-base) exit(OVERFLOW); S-topS-baseS-stacksize; S-stacksizeSTACKINCREMENT; } *S-tope; return OK; } Status Pop(SqStack *S,SElemType *e){ //若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR if(S-topS-base) return ERROR; *e*--S-top; return OK; }1.4 获得栈顶元素Status GetToop(SqStack *S,SElemType *e){ //若栈不空则用e返回S的栈顶元素并返回OK 否则返回ERROR if(S-topS-base) return ERROR; *e*(S-top-1); return OK; }二、队列2.1 定义队列queue是一种先进先出的线性表它只允许在表的一端进行插入而在另一端删除元素。允许插入的一端叫做队尾rear允许删除的一端叫做队头front。2.2 常见函数命名InitQueue(*Q)初始化队列DestroyQueue(*Q)销毁队列ClearQueue(*Q)清空队列QueueEmpty(Q)判断队列是否为空QueueLength(Q)返回队列中的元素个数GetHead(Q,*e)返回队头元素EnQueue(*Q,e)入队元素DeQueue(*Q,*e)出队元素QueueTraverse(Q,visit())队列遍历2.3 运用场景任务调度操作系统的进程调度常常使用队列处理先到先处理的任务。打印任务管理多个打印任务可能进入队列按照顺序依次进行打印。消息队列在分布式系统中消息队列用于异步通信和任务分发。广度优先搜索BFS在图的广度优先搜索算法中队列用于存储待访问的节点。一层一层的搜注用顺序表实现队列使用循环的结构来的尾指针指向最后的一个空间后会重新指向第一个空间。三、链队列3.1 初始化typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; //创建节点结构 typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue //创建队头队尾指针 Status InitQueue(LinkQueue *Q){//构造一个空队列Q Q-frontQ-rear(QueuePtr)malloc(sizeof(QNode)); if(!Q-front) exit(OVERFLOW); Q-front-nextNULL; return OK; }3.2 出队和入队Status EnQueue(LinkQueue *Q,QElemType e){//插入元素e为Q的新的队尾元素 p(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p-datae; p-nextNULL; Q-rear-nextp; Q-rearp; return OK; } Status DeQueue(LinkQueue *Q,QElemType *e){//若队列不空则删除Q的队头元素用e返回其值并返回OK if(Q-frontQ-rear) return ERROR; pQ-front-next; *ep-data; Q-front-nextp-next; if(Q-rearp) Q-rearQ-front; free(p); return OK; }3.3 销毁队列Status DestroyQueue(LinkQueue *Q){//销毁队列QQ不再存在 while(Q-front){ pQ-front-next; free(Q-front); Q-frontp; } return OK; }四、循环队列先言队列的顺序表示类似于一个数组头尾是连接的对满的时候有两种表示方法1.对头和队尾指向同一个元素的时候但此时无法判断是满了还是空了2.对头和队尾差一个元素的时候但此时会浪费一个元素4.1 循环队列和链队列的区别特性循环队列链队列实现方式数组固定大小链表动态大小队列大小固定动态空间开销小无额外指针大每个节点需指针入队出队O(1)O(1)队列满有固定容量无可动态扩展适用场景容量可预估、缓冲区容量不确定、动态调度如果你知道队列的最大长度并且不需要频繁变化循环队列是一个理想选择因为它的空间利用效率高、实现简单。如果队列的大小不可预测且希望能根据需求动态扩展链队列是更好的选择虽然会有额外的内存开销和管理复杂度。4.2 初始化#define MAXQSIZE 100 typedef struct{ QElemType *base; int front; int rear; }SqQueue; Status InitQueue(SqQueue *Q){ Q-base(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q-base) exit(OVERFLOW); Q-frontQ-rear0; return OK; }4.3 出队和入队Status EnQueue(SqQueue *Q, QElemType e) { if (Q-front (Q-rear 1) % MAXSIZE) return ERROR; Q-base[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; return OK; } Status DeQueue(SqQueue *Q, QElemType *e) { if (Q-front Q-rear) return ERROR; *e Q-base[Q-front]; Q-front (Q-front 1) % MAXSIZE; return OK; }4.4 元素个数int QueueLength(SqQueue Q) { return (Q.rear - Q.front MAXSIZE) % MAXSIZE; }避免队尾小于对头的情况
数据结构栈和队列
一、栈先言栈遵循后进先出last in first outLIFO的原则。常见场景1.函数调用管理栈用于管理函数调用包括存储局部变量和返回地址。当一个函数调用另一个函数时当前函数的状态被推入栈中待调用的函数完成后从栈中弹出状态恢复执行。2.撤销操作在文本编辑器或其他应用程序中栈用于实现撤销操作。每次用户进行操作时操作会被推入栈中用户可以通过弹出栈中的操作来撤销最近的操作。3.浏览器历史管理栈可以用于管理浏览器的历史记录。当用户访问新页面时当前页面的地址被推入栈中用户按“后退”按钮时最近访问的页面被弹出并加载。4.字符串反转使用栈可以轻松地实现字符串的反转将字符串中的字符逐个推入栈中然后再依次弹出。5.深度优先搜索一个分支搜到底之后再进行下一个分支1.1 常见函数命名数据类型栈使用的数据类型为D{ai|ai∈ElemSet, i1,2,…,n,n ≥ 0}。•基本操作1.InitStack(*S)初始化一个空栈 S。2.DestroyStack(*S)销毁栈 S。3.ClearStack(*S)清空栈 S 中的所有元素。4.StackEmpty(S)检查栈 S 是否为空。如果为空返回 TRUE否则返回 FALSE。5.StackLength(S)返回栈 S 中元素的个数。6.GetTop(S, *e)返回栈 S 顶端的元素并将其赋值给 e。7.Push(*S, e)将元素 e 压入栈 S 的顶端。8.Pop(*S, *e)将栈 S 顶端的元素弹出并将其赋值给 e。9.StackTraverse(S, visit())从栈顶到底部遍历栈 S并对每个元素应用 visit() 函数。如果 visit() 函数失败则遍历停止。1.2 初始化栈Status I nitStack(SqStack *S){ //构造一个空栈 S-base(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S-base) exit(OVERFLOW); S-topS-base; S-stacksizeSTACK_INIT_SIZE; return OK; } Status GetToop(SqStack *S,SElemType *e){ //若栈不空则用e返回S的栈顶元素并返回OK否则返回ERROR if(S-topS-base) return ERROR; *e*(S-top-1); return OK;S-top S-base S-stacksize必须使用旧的stacksize因为realloc后top需要指向旧栈顶的下一个位置新空间的起点而S-stacksize更新后指向的是新空间的末尾会导致top定位错误*S-top e确实是先在旧的top指向的位置空闲位置赋值e然后将top后移一位使其指向新的栈顶下一个空闲位置。top是指向最后一个元素的最后一个位置也是下一个元素位置的起点1.3 出栈和入栈Status Push(SqStack *S,SElemType e){ //插入元素e为新的栈顶元素 if(S-top-S-baseS-stacksize){ S-base(SElemType *)realloc(S-base,(S-stacksizeSTACKINCREMENT)*sizeof(SElemType)); if(!S-base) exit(OVERFLOW); S-topS-baseS-stacksize; S-stacksizeSTACKINCREMENT; } *S-tope; return OK; } Status Pop(SqStack *S,SElemType *e){ //若栈不空则删除S的栈顶元素用e返回其值并返回OK否则返回ERROR if(S-topS-base) return ERROR; *e*--S-top; return OK; }1.4 获得栈顶元素Status GetToop(SqStack *S,SElemType *e){ //若栈不空则用e返回S的栈顶元素并返回OK 否则返回ERROR if(S-topS-base) return ERROR; *e*(S-top-1); return OK; }二、队列2.1 定义队列queue是一种先进先出的线性表它只允许在表的一端进行插入而在另一端删除元素。允许插入的一端叫做队尾rear允许删除的一端叫做队头front。2.2 常见函数命名InitQueue(*Q)初始化队列DestroyQueue(*Q)销毁队列ClearQueue(*Q)清空队列QueueEmpty(Q)判断队列是否为空QueueLength(Q)返回队列中的元素个数GetHead(Q,*e)返回队头元素EnQueue(*Q,e)入队元素DeQueue(*Q,*e)出队元素QueueTraverse(Q,visit())队列遍历2.3 运用场景任务调度操作系统的进程调度常常使用队列处理先到先处理的任务。打印任务管理多个打印任务可能进入队列按照顺序依次进行打印。消息队列在分布式系统中消息队列用于异步通信和任务分发。广度优先搜索BFS在图的广度优先搜索算法中队列用于存储待访问的节点。一层一层的搜注用顺序表实现队列使用循环的结构来的尾指针指向最后的一个空间后会重新指向第一个空间。三、链队列3.1 初始化typedef struct QNode{ QElemType data; struct QNode *next; }QNode,*QueuePtr; //创建节点结构 typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue //创建队头队尾指针 Status InitQueue(LinkQueue *Q){//构造一个空队列Q Q-frontQ-rear(QueuePtr)malloc(sizeof(QNode)); if(!Q-front) exit(OVERFLOW); Q-front-nextNULL; return OK; }3.2 出队和入队Status EnQueue(LinkQueue *Q,QElemType e){//插入元素e为Q的新的队尾元素 p(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p-datae; p-nextNULL; Q-rear-nextp; Q-rearp; return OK; } Status DeQueue(LinkQueue *Q,QElemType *e){//若队列不空则删除Q的队头元素用e返回其值并返回OK if(Q-frontQ-rear) return ERROR; pQ-front-next; *ep-data; Q-front-nextp-next; if(Q-rearp) Q-rearQ-front; free(p); return OK; }3.3 销毁队列Status DestroyQueue(LinkQueue *Q){//销毁队列QQ不再存在 while(Q-front){ pQ-front-next; free(Q-front); Q-frontp; } return OK; }四、循环队列先言队列的顺序表示类似于一个数组头尾是连接的对满的时候有两种表示方法1.对头和队尾指向同一个元素的时候但此时无法判断是满了还是空了2.对头和队尾差一个元素的时候但此时会浪费一个元素4.1 循环队列和链队列的区别特性循环队列链队列实现方式数组固定大小链表动态大小队列大小固定动态空间开销小无额外指针大每个节点需指针入队出队O(1)O(1)队列满有固定容量无可动态扩展适用场景容量可预估、缓冲区容量不确定、动态调度如果你知道队列的最大长度并且不需要频繁变化循环队列是一个理想选择因为它的空间利用效率高、实现简单。如果队列的大小不可预测且希望能根据需求动态扩展链队列是更好的选择虽然会有额外的内存开销和管理复杂度。4.2 初始化#define MAXQSIZE 100 typedef struct{ QElemType *base; int front; int rear; }SqQueue; Status InitQueue(SqQueue *Q){ Q-base(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q-base) exit(OVERFLOW); Q-frontQ-rear0; return OK; }4.3 出队和入队Status EnQueue(SqQueue *Q, QElemType e) { if (Q-front (Q-rear 1) % MAXSIZE) return ERROR; Q-base[Q-rear] e; Q-rear (Q-rear 1) % MAXSIZE; return OK; } Status DeQueue(SqQueue *Q, QElemType *e) { if (Q-front Q-rear) return ERROR; *e Q-base[Q-front]; Q-front (Q-front 1) % MAXSIZE; return OK; }4.4 元素个数int QueueLength(SqQueue Q) { return (Q.rear - Q.front MAXSIZE) % MAXSIZE; }避免队尾小于对头的情况
