第四章、栈和队列、堆
4.1、栈和队列的定义和特点
1、栈和队列是两种常用的、重要的数据结构
2、栈和队列是限定插入和删除只能在表的“端点”进行的线性表
3、栈和队列是线性表的子集合（是插入和删除位置受限的线性表）
4.1.1、栈（stack）定义和特点
1、栈：特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表
2、又称为后进先出的线性表，简称LIFO
3、相关概念
（1）栈是在表尾进行插入、删除操作的线性表
（2）表尾（an）称为栈顶（top），表头（a1）称为栈地Base
（3）插入栈顶（表尾），入栈
（4）栈顶（表尾）删除，出栈
（5）逻辑结构：和线性表一样，一对一关系
（6）存储结构：顺序或链式都可以，顺序更为常见
（7）运算规则：后进先出
4、入栈示意图
5、出栈示意图
6、栈和一般线性表区别：仅在运算规则不同
4.1.2、队列的定义和特点
1、队列的定义：只能在表的一端进行插入运算，在另一端进行删除运算的线性表
2、特点：先进先出
3、逻辑结构：和线性表一样，一对一关系
4、存储结构：顺序或链式都可以，循环顺序更为常见
5、运算规则：队首和队尾运算，且先进先出原则
4.2、顺序表栈的表示和实现
4.2.1、顺序栈的初始化
1、定义数组
2、进行判断数组是否合法
3、栈顶和栈底相等，表示空
4、java代码实现
private int maxSize=100;//栈的最大值
private int top=-1;//栈顶
private int bottom = maxSize-1;
private int [] stack;
public Status_init(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
public Status_init(){
stack = new int[maxSize];
}4.2.2、顺序栈是否为空/满
1、如果栈顶=栈底，则为空
2、java代码实现
// 判断栈是否空了
public boolean isEmpty(){
return top==-1;
}
// 判断栈是否满了
public boolean isFull(){
return top == bottom;
}4.2.3、求顺序栈长度
1、栈顶-栈底
2、java代码实现
// 栈的长度
public int statusLength(){
return top+1;
}4.2.4、顺序栈入栈
1.判断是否栈满，满则错误
2、添加元素
3、栈顶++
4、java代码
// 入栈
public void push(int value){
// 先判断是否为满
if(isFull()){
System.out.println("入栈失败，栈满咯");
}else {
top++;
stack[top] = value;//入栈操作
System.out.println(stack[top]+"入栈成功~~~");
}
}4.2.5、顺序栈出栈
1、先判断是否为空，为空则错误
2、选取需要删除的元素
3、栈顶--
4、java代码实现
// 出栈
public int pop(){
if(isEmpty()){
System.out.println("栈为空，无法出栈");
}
int value = stack[top];
top--;
System.out.println("出栈成功");
return value;
}4.2.6、循环遍历栈
// 循环遍历栈
public void outputStatus(){
if(isEmpty()){
System.out.println("栈为空，没有数据");
}
for(int i =top;i>=0;i--){
System.out.println("stat[]=:"+stack[i]+"\t");
}
}4.3、链式栈的表示和实现
4.3.1、链栈的表示
1、链栈是运算受限的单链表，只能在链表头部进行操作。
2、注意：链栈中指针的方向是指向链表前驱的。an—>an-1
（1）图示
3、链表的头结点就是栈顶
4、不需要头结点
5、基本不存在栈满的情况
6、空栈下相当于指针指向空
7、插入和删除仅在栈顶处执行
4.3.2、链栈的初始化
2、JAVA代码实现
// 定义栈顶和栈底元素
private Element base;//栈底
private Element top;//栈顶
//链栈的数据模型
class Element {
public Object data;//存储数据
Element next;//指针
}
// 初始化栈
public void init() {
Element elem = new Element();//初始化一个空间
base = elem;
top = elem;
base.data = null;
System.out.println("栈成功初始化");
}4.3.3、链栈的入栈
1、相当于单链表的头插法
2、java代码实现
// 入栈操作
public void push(Object obj) {
Element elem = new Element();
elem.data = obj;
elem.next = top;
top = elem;//修改栈顶为入栈的元素
System.out.println("链栈元素成功加入");
}4.3.4、链栈的出栈
1、
2、java代码实现
// 退栈操作
public Object pops() {
if (isEmpty()) {
System.out.println("退栈失败，栈为空");
}
Object object = top.data;
top = top.next;//修改指针
System.out.println(object+"退栈成功");
return object;
}4.3.5、取出链栈顶/底的值
1、就是取出头结点的值
2、java代码实现
// 取出栈底的值
public Element getBase() {
return base;
}
// 获取栈顶
public Element getTop() {
return top;
}4.3.6、遍历链栈
1、while判断，base==top//表示为空
2、java代码实现
// 遍历栈
public void printLinkStatus(){
if (isEmpty()) {
System.out.println("栈为空");
}
Element temp = top;
while (temp!=base){
System.out.println("数据——》"+temp.data);
temp = temp.next;
}
}4.3.7、获取链栈大小
1、和遍历链栈相似
// 获取栈大小
public String getSize(){
int size = 0;
Element temp = top;
while (temp!=base){
temp =temp.next;
size++;
}
return "该栈大小为："+size;
}4.4、栈与递归
4.4.1、递归的定义
1、若是对象部分地包含自己，或用它自己给自己定义，则称为递归。
2、一个过程直接或简介地调用自己也是递归。
4.4.2、递归常见用途
1、递归定义的数学函数
2、具有递归特性的数据结构
3、可递归求解问题
（1）分治法、迷宫问题、汉诺塔等
4、递归要使用的三个条件
（1）能将一个问题转变为一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的。
（2）可以通过上述转化而使问题简化。
（3）必须有一个明确的递归出口，或称递归的边界。
4.4.3、分治法求解递归问题算法一般格式
4.4.4、函数调用过程（递归）
4.4.5、例子
4.4.6、递归函数调用的实现
4.4.7、进行fact（4）调用的系统栈的变化状态
1、先进后出
2、递归到可以计算才能调回
4.4.8、递归的优缺点
1、优点
（1）结构清晰，程序易读
2、缺点
（1)每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，时间开销大。
4.4.9、递归—>非递归
1、方法一、尾递归、单向递归—>循环结构。
2、借用栈模拟系统的运行栈
4.5、顺序队列
4.5.1、相关术语
1、表头删除，表尾插入
2、a1表头，an表尾
3、先进先出的线性表
4、插入称为入队，删除称为出队
5、队列的存储结构为链队、或顺序队（常用循环顺序队）
4.5.2、队列的相关概念
4.5.3、队列的常见应用
4.5.4、队列的顺序表示—初始化
1、头指针==尾指针
2、图例
3、java代码实现
private int maxSize;//最大尺寸
private int front;//头
private int rear;//尾
Object data [] ;//数组模拟队列
public int count ;
// 初始化
public arrqueue(int maxSize){
if(maxSize<1){
maxSize=1;
}
this.maxSize=maxSize;
data = new Object[maxSize];
front = 0;//第一个元素的
rear = 0;//最后一个元素
count=0;
}4.5.5、队列的顺序表示—入队
1、尾指针++，头指针不变
2、数据放入数组中
3、图例
4、java代码实现
// 加入数据
public void addQueue( Object obj){
if(isFull()){
System.out.println("数据队列已满~");
}
rear++;
data [rear] = obj;
count++;
}4.5.6、队列的顺序表示—出队
1、头指针++
2、空队标志：front==rear
3、图例
4、java代码实现
// 删除队列
public void delQueue(){
if(isEmpty()){
System.out.println("队列为空~");
}
System.out.println(front+"删除成功");
front++;
count--;
}4.5.7、解决假上溢的方法
1、理解
2、引入循环队列
（1）利用rear+1%MaxSize
4.5.8、循环队列—初始化
1、base、front、rear
2、java代码实现
public class CircularQueue {
private int maxSize;//最大尺寸
private int front;//头
private int rear;//尾
Object data [] ;//数组模拟队列
// 初始化
public CircularQueue(int maxSize) {
this.maxSize=maxSize;
data = new Object[maxSize];
front = 0;//第一个元素的
rear = 0;//最后一个元素
}4.5.9、循环队列—插入
1、base[rear] = x; //x为插入的数据
2、rear = (rear+1)%MaxSize;
3、java代码实现
// 加入元素
public void addCirQueue(Object objData){
if(isFull()){
System.out.println("队列已满，无法添加");
return;
}
data[rear] = objData;
rear = (rear+1)%maxSize;//修改队尾指针
}4.5.10、循环队列—删除元素
1、x=base[front]
2、front = （front+1)%MaxSize;
3、java代码实现
// 删除元素并返回被删除元素
public Object delCirQueue(){
if(isEmpty()){
System.out.println("队列为空，无法删除");
return 0;
}
Object reX = data[front];//返回被删除的元素名称
front = (front+1)%maxSize;//重写判断front的位置
return reX+"被成功删除了";
}4.5.11、循环队列—判断队空，队满。
1、当(rear+1)%MaxSize==front时，队列空/满
（1）就是尾指针向后移动一位正好是front
2、解决方案
3、图解
4、java代码实现
// 判断是否为满
public boolean isFull(){
if((rear+1)%maxSize==front){
return true;
}else {
return false;
}
}
// 判断是否为满空
public boolean isEmpty(){
if(rear==front){//rear+1表示有一个空的作为分割
return true;
}else {
return false;
}
}4.5.12、循环队列—求队列的长度
1、理解
2、java代码实现
// 求队列的长度
public int getLength(){
return (rear-front+maxSize)%maxSize;
}4.5.13、循环队列—取队头元素
1、判断是否为空
2、data[front]
// 去队头元素
public Object getHead(){
if(isEmpty()){
System.out.println("队列为空，无数据");
return 0;
}
return data[front];
}4.5.14、循环队列—遍历队列
1、(i+maxSize)%maxSize!=rear
2、java代码实现
// 循环遍历队列
public void showCirQueue(){
int i = front;
while ((i+maxSize)%maxSize!=rear){
System.out.println(data[i]);
i++;
}
}4.6、链式队列
4.6.1、链队列类型定义（数据模型）
1、有data变量
2、有next指针
3、图示
4、java代码实现
public class LinkNode {
Object object;
LinkNode next;
public LinkNode(Object object) {
this.object = object;
}
}4.6.2、链队列—运算指针变化状况
4.6.2、链队列—初始化
1、开辟元素空间
2、初始化头指针和尾指针
3、数据初始化
4、java代码实现
// 初始化
LinkNode rear = null;
LinkNode head = null;4.6.3、链队列—销毁链队列
1、算法思路：从头结点开始，依次释放所有节点
2、利用循环
3、rear==front.next;
free(front);
front==rear;
4、java代码实现
4.6.4、链队列—入队列
1、利用尾插法
2、java代码实现
// 入队列
public void addLinkQueue(Object object){
LinkNode newNode = new LinkNode(object);
if(rear==null){//如果尾指针为空，设置头指针和尾指针
rear = newNode;
head = newNode;
return;
}
LinkNode temp = rear;
while (temp.next!=null){
temp = temp.next;
}
temp.next = newNode;//把新加入的元素放在最尾
System.out.println("加入成功");
}4.6.5、链队列—删除队列元素
1、指针绕过要删除的节点，直接跳转到被删除的下一个节点
2、java代码实现
// 删除队列元素
public boolean delLinkQueue(){
if(head.next!=rear){//如果不为空
head = head.next;//指针绕过要删除的节点，直接跳转到被删除的下一个节点
System.out.println("删除成功");
return true;
}
return false;
}4.6.6、取出队列首/尾元素
1、有瑕疵
2、java代码实现
/ 取出队列首值
public void getHead(){
if(isEmpty()){
System.out.println("队列为空");
}else {
System.out.println("队列首值为"+head.next.object);
}
}
// 取队列尾值
public void getRear(){
LinkNode temp = rear;//中间指针
while (temp.next!=null){//temp如果不是最后一个
temp = temp.next;
}
if(isEmpty()){
System.out.println("队列为空");
}else {
System.out.println("队尾的值是："+temp.object);
}
}4.6.7、链队列—求队列的长度
1、利用while循环
2、java代码实现
// 求队列的长度
public void Length(){
LinkNode temp = head;
int i=0;
if(isEmpty()){
System.out.println("队列为空");
}else {
while (temp.next!=null){
i++;
temp = temp.next;
}
}
System.out.println("队列的长度为"+i);
}4.6.8、链队列—展示队列
1、利用循环
2、java代码实现
// 展示队列
public void showLinkQueue(){
LinkNode temp = head;
int i=0;
if(isEmpty()){
System.out.println("队列为空");
}else {
while (temp.next!=null){
i++;
temp = temp.next;
System.out.println(temp.object);
}
}
}4.7、堆
