

首页  思维导图  详情



栈和队列

2019-03-21 17:13:59   0  举报





仅支持查看

AI智能生成

数据结构-栈和队列

栈和队列

模版推荐

作者其他创作

大纲/内容

栈

定义

栈是一种只允许在表的一端进行插入操作和删除操作的线性表。允许操作的一端称为栈顶，栈顶元素的位置由栈顶指针给出

运算规则

先进后出

逻辑结构

线性结构，特殊的线性表： 1. 其操作仅是一般线性表的操作的一个子集。 2. 插入、删除操作的位置受到限制。

存储结构

顺序存储结构

用一维数组STACK[0..M–1]来表示栈，并定义一个整形变量top指向当前栈顶元素。栈为空时，top=-1

类型定义

#define M 1000 SElemType STACK[M]; int top = -1;  //初始为空栈

判断栈空

int EMPTYS( int top ) { return top==–1; }

判断栈满

int FULLS( int top ) { return top==M–1; }

插入（入栈）

要先判断是否栈满，再STACK[++top]=item；

删除（出栈）

要先判断是否栈空，再item=STACK[top--]; （item用来保存删掉的元素，只需将top指针下移，就算删除了）

两栈共享连续空间（数组）问题

数组STACK[0..M-1] top[0]、 top[1] 分别为第1个与第2个栈的栈顶元素指针

栈满：top[0]=top[1]–1

栈空： 第1个栈空 top[0]=–1 第2个栈空 top[1]=M

链式存储结构

用一个线性链表来实现一个堆栈结构, 同时设置一个指针变量top指出栈顶元素所在链结点的位置。栈为空时，有top=NULL （链栈是运算是受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针）

类型定义

typedef struct node { SElmeType data; struct node *link; } STNode, *STLink;

判断栈空

int EMPTYS( STLink top ) { return top==NULL; }

插入（入栈）

不必判断是否栈满，在链表最前面插入一个新结点即可（头插法）

删除（出栈）

先判断是否栈空，再删掉第一个结点（删前先保存以便free）

取栈顶元素

先判空，再返回头指针（top）所指元素  if (S==NULL) exit(1)；  else return S–>data;

栈与递归

递归是自己调用自己，当多个函数构成嵌套调用时, 遵循后调用的先返回，即后进先出

具有递归定义的数据结构

树、广义表

可递归求解的问题

迷宫问题、hanoi塔问题

递归算法效率分析

空间效率：与递归树的深度成正比 O(n） 时间效率：与递归树的结点数成正比  O(2^n)

递归优缺点

优点：结构清晰，程序易读 缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大 。 为克服缺点：尾递归、单向递归——>循环结构

队列

定义

队列是一种只允许在表的一端进行插入操作（队尾），而在表的另一端进行删除操作（队头）的线性表。队头由front指出，队尾由rear指出。

运算规则

先进先出

逻辑结构

线性结构，特殊的线性表： 1. 其操作仅是一般线性表的操作的一个子集。 2. 插入、删除操作的位置受到限制。

约定

rear 指出实际队尾元素所在的位置, front 指出实际队头元素所在位置的前一个位置。

存储结构

顺序存储结构

用一维数组QUEUE[0..M–1]来表示队列，设置两个变量 front与rear指出当前队头元素与队尾元素的位置

初始化

初始时，队列为空，有front=rear=-1

判断队空

return  front==rear

插入（入队）

先判断是否队满 if(rear==M-1)，再插入QUEUE[++rear]=item;

删除（出队）

先判断是否队空，再删除item=QUEUE[++front];（只需将front指针后移，就算删除了）

假溢出

rear==M-1了，但front前面还有空位

循环队列（解决假溢出）

把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为循环队列

链式存储结构

用一个线性链表表示一个队列，指针front与rear指向实际队头元素与实际队尾元素所在的结点

初始化

front=rear=NULL

判断队空

return  front==NULL;

插入（入队）

分两种情况：（因为没给链表设头结点，如果有头结点就不用分情况） 1、将元素插入插入空队 if(front==NULL) front=p; 2、插入非空队 rear->link=p;  rear=p;

删除（出队）

先判断队列是否为空，再删除队头结点

销毁一个队列

一个一个删除队头结点： while(front){ /* 队列非空时 */ rear=front->link; free(front); /* 释放一个结点空间 */ front=rear; }

 Collect

Get Started

消息队列

 Collect

Get Started

后端技术栈全景

 Collect

Get Started

栈帧图

 Collect

Get Started

问题举例_重计算队列





0 条评论

下一页