考研数据结构——

考研数据结构——,第1张

队列
  • 一、 顺序结构实现队列
    • 1.1 队列的结构体、初始化、判空
    • 1.2 入队 *** 作
      • 1.2.1 循环队列牺牲一个位置
      • 1.2.2 循坏队列不牺牲位置
    • 1.3 出队 *** 作与获取队头元素
    • 1.4 队列的rear指向 队尾元素时, 各种条件整理!
      • 1.4.1 牺牲一个元素位置的情况
      • 1.4.2 不牺牲一个元素的判断
    • 1.5 顺序结构思维导图
  • 二、 链式结构实现队列
    • 2.1 链式队列的实现
    • 2.2 初始化链式队列
      • 2.2.1 带头结点版本
      • 2.2.2 不带头结点的
    • 2.3 入队 *** 作
      • 2.3.1 带头结点的入队 *** 作
      • 2.3.2 不带头结点的入队 *** 作
    • 2.4 出队 *** 作
      • 2.4.1 带头结点的出队 *** 作
      • 2.4.2 不带头结点的出队 *** 作
    • 2.5 链式队列是否存在队满情况?
    • 2.6 链式队列知识框架
  • 三、双端队列
    • 3.1 双端队列的介绍
      • 3.1.1 限制只在一侧 *** 作
      • 3.1.2 输入受限或者输出受限的双端队列
    • 3.2 判断输出序列合法性
      • 3.2.1 判断栈的输出序列合法性(卡特兰数)
      • 3.2.2 判断输入受限的双端队列的合法性(容易考选择题)
      • 3.2.3 判断输出受限的双端队列

一、 顺序结构实现队列

(本文 涉及到的判断条件 基于默认 rear指向队尾元素的下一个)
如果是 rear指向队尾元素的话,特别注释了!

1.1 队列的结构体、初始化、判空
  • 队列的结构体, front队头和队尾
  • 初始化就是将队头和队尾都设置为 0
  • 判断队列空的条件是 队列的头和尾 相等即: front == rear

1.2 入队 *** 作
  • 先检查队列是否为满, 非循环队列的话如果一直没出过栈,队尾指针rear==最大长度就是满了,但是如果队头出过队了,这个条件就不成立,因此一般使用循环队列。

1.2.1 循环队列牺牲一个位置

⭐ 循环队列牺牲一个元素位置用来区别队满(front == (rear + 1)%MaxSize)与队空(front==rear)。

  • 当队满时,指的是队尾指针的下一个就是队头: (rear+1) % MaxSize == front


1.2.2 循坏队列不牺牲位置
  1. 方案一: 设置size记录队长

设置size用于记录队列的长长度

  • 初始化时: 将 front rear size都设置为 0;
  • 入队时:将size++;
  • 出队时:将size–
  • 判断队空时: size == 0
  • 判断队满时: size==MaxSize

  1. 方案二: 设置tag表示最近一次 *** 作是入队还是出队

我们指定tag=1表示 最近一次 *** 作为入队, tag = 0 表示最近一次 *** 作为出队。初始时我们指定 tag为0; 当rear = front的时候 如果时 tag为1表示 入队导致 队头队尾位置相同即是队满,如果tag为0表示 出队导致队头队尾位置相同即是队空。

  • 初始化时: rear = front = tag = 0;
  • 入队时: 设置 tag = 1;
  • 出队时: 设置tag = 0;
  • 判断队满: rear == front && tag ==1
  • 判断队空: rear == front && tag ==0

1.3 出队 *** 作与获取队头元素
  • 出队 *** 作与取得队友元素的唯一区别就是, 出队在读取完队头后,自己要移动位置(自增一)
  • 首先判断 队列是否为空: rear == front
  • 取除队头后,队头像队尾移动。移动条件: front = (front + 1) % MaxSize

1.4 队列的rear指向 队尾元素时, 各种条件整理!
  • 初始化时: front指向0, rear指向 MaxSize-1;
  • 入队时: 先自增再赋值 rear = (rear + 1) % MaxSize 再 data[rear] = x;

1.4.1 牺牲一个元素位置的情况
  • 判断队满 : (rear + 2) % MaxSize == front
  • 判断队空: (rear + 1) % MaxSize == front

1.4.2 不牺牲一个元素的判断
  1. 添加一个size记录队长siz
  • 初始化: size=0 front = 1 rear = MaxSize -1;
  • 进队:先自增再赋值: rear = (rear + 1) % MaxSize ; data[rear] = x; size++;
  • 出队:先获取值再自减: x = data[rear] ; rear = (rear - 1) % MaxSize ; size–;
  • 判断空: size ==0;
  • 判断满: size == MaxSize
  1. 添加一个表示 tar(1:表示最近一次 *** 作为入队;0表示最近一次 *** 作为出队)
  • 初始化 :front = 0; rear = MaxSize-1; tar = 0; (因为tag==0 也可以表示为出队导致的队空也可以表示初始为空)
  • 进队:先自增再赋值: rear = (rear + 1) % MaxSize ; data[rear] = x; tar=1;
  • 出队:先获取值再自减: x = data[rear] ; rear = (rear - 1) % MaxSize ; tar=0;
  • 判断空: rear == front && tar ==0; (指的是出队导致的队头队尾重合,队空)
  • 判断满: rear == front && tar ==1; (指的是入队导致的队头队尾重合,队满)
1.5 顺序结构思维导图

二、 链式结构实现队列 2.1 链式队列的实现
  • LinkQueue指的是队列
  • LinkNode是队列中的结点

2.2 初始化链式队列 2.2.1 带头结点版本
  • 开辟空间,并将开辟空间的地址赋值给 front与rear,也就是让队头队尾都指向这个空间
  • 让front指向null(front->next == NULL)表示队列为空, 当然 front==rear也表示队列为空
  • ⭐ 个人理解: front指针就类似于头指针,而front->next就是指向的队列的第一个元素!

2.2.2 不带头结点的
  • 初始化的时候直接让 rear与front指向 null即可。
  • 当frontnull 或者 frontrear的时候表示 链式队列为空

2.3 入队 *** 作 2.3.1 带头结点的入队 *** 作
  • 首先要开创一个新的结点空间,并为它赋值;
  • 要将新的结点的next指向为 null;
  • 队尾标志rear下一个为新结点: Q.rear->next = s; (白话意思就是将新元素添加到最后一个元素后面)
  • 队尾标志后移 Q.rear = s;

2.3.2 不带头结点的入队 *** 作
  • 开始依旧是 初始一个新元素空间 1.赋值 2.新元素指向null;
  • ⭐ 不带头结点的要注意第一次插入 *** 作时, 要将Q.front与Q.rear都指向 第一个元素!!!(这是带头结点和不带头结点的区别);判断的条件是: Q.front==NULL 或者 Q.front == Q.rear;
  • 不是第一个元素的话, Q.rear->next = s; (也就是将最后一个元素指向 新元素位置)
  • Q.rear = s; (也就是标识最后一个元素为队尾);

2.4 出队 *** 作 2.4.1 带头结点的出队 *** 作
  • 首先判断是否队空: Q.rear == Q.front
  • 使用临时变量 p 接收 暂存队头结点: p = Q.front->next;
  • ⭐ 判断是不是最后一个元素, 如果是最后一个元素,应当让Q.rear指向和Q.front一致:
  1. 判断 Q.rear = p (因为p = Q.front->next);
  2. 让队尾和队头指向一致: Q.rear = Q.front;
  • 最后free掉结点就行;

2.4.2 不带头结点的出队 *** 作
  • 判断队空: Q.front == NULL;
  • p临时是存储队头结点: p=Q.front;
  • 获取队头元素: x = p->data;
  • 队头后移: Q.front = p->next;
    -⭐ 关键一步判断是否为最后一个元素:如果是将 队头队尾指向都设置为NULL: Q.rear = NULL;Q.front = NULL;
  • 释放p即可;

2.5 链式队列是否存在队满情况?

jzq回答: 不会,除非内存满了!

2.6 链式队列知识框架

三、双端队列 3.1 双端队列的介绍
  • 栈: 只能在一端(栈顶)进行插入删除的线性表
  • 队列: 只能在一端(队尾)进行插入,另一端(队头)进行删除的线性表;
  • 双端队列: 只允许从两端进行插入以及删除的线性表;

3.1.1 限制只在一侧 *** 作
  • 如果限制双端队列只能在一侧进行插入删除,就是栈的功能了。

3.1.2 输入受限或者输出受限的双端队列

3.2 判断输出序列合法性 3.2.1 判断栈的输出序列合法性(卡特兰数)

3.2.2 判断输入受限的双端队列的合法性(容易考选择题)

3.2.3 判断输出受限的双端队列

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/789684.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-05
下一篇 2022-05-05

发表评论

登录后才能评论

评论列表(0条)

保存