20210410

恋词U7 | 数据结构-栈和队列（二）| 田静语法-C1-S2-1-2~5

Table of Contents

恋词U7

  • trigger n.扳机；触发 v.引发；发动
  • enforce v.强制实施；强制执行；强迫；即使
  • reinforce v.增援；加强
  • idle adj.空闲的，闲置的；无用的；无效的；懒散的 v.虚度
  • propaganda n.宣传；鼓吹
  • propagate v.传播；繁殖
  • resent v.对...愤怒
  • spite n.恶意；怨恨
  • postpone v.延迟；使延期
  • metaphor n.隐喻；暗喻
  • whip n.鞭子；党鞭

数据结构-栈和队列（一）

队列的逻辑结构（基本概念）

  • 队列是一种插入元素只能在一端能进，删除元素只能在另一端进行的线性表。
    • 线性表：队列的逻辑结构属于线性表，只不过在操作上加了一些约束。
    • 一端：可以插入元素的一端叫做队尾（Rear）。
    • 另一端：可以删除元素的一端叫队头（Front）。

由上面的逻辑特性图可以看出，先进来的容易先出去。即先进先出。

First In , First Out. （FIFO)。
与栈的先进后出做一下对比。

408真题

分析：题目如左图所示，而题目所要实现的就是先写入的数据先取出即右图效果，那么很明显队列的逻辑特性更加符号。

队列的存储结构

顺序队

  1. 定义
int queue[maxSize];

int front= 0,rear = 0;
  1. 入队
queue[++rear] = x;
  1. 出队
x = queur[++front];
  1. 但是！！！，当下图情况，即rear走到数组最后一个位置的时候，如果这时候要入队元素，岂不是会发生“数组越界”，但这也不是队满的情况，因为数组中还有很多空位置没有存储元素。所以并非队满，可是如果此时继续按照之前的操作入队元素，就会发生数组越界。我们把这种状态称之为假溢出。即虽然会造成数组越界，但数组内依然有空位置存在。其实是入队和出队方式不应该这么做。试着去掰弯。
  1. 改进：调整数组，掰成环。

要解决假溢出的问题，可以把数组弄成一个环，让rear和front沿着环走，这样就永远不会出现两者来到数组尽头无法继续往下走的情况，这样就产生了循环队列。循环队列是改进的顺序队列。如下图所示：

那么代码就变成：

  • 入队
rear = (rear + 1) % maxSize;

queue[rear] = x;
  • 出队
front = (front + 1) % maxSize;

x = queue[front];
  1. 特殊状态
  • 队空 front == rear
  • 队满
    • 假设队满时，即环中所有元素被填满，即还是rear == front时，显然是不行的。
    • 那么就可以退而求其次，当即将被填满即下图中所示即被为队满，但是显然写rear + 1 = front也是不行的，应该要这么写：front == (rear + 1) % maxSize。

链队

  1. 定义
typedef struct

{

    LNode* front;

    LNode* rear;

}queue;
  1. 入队

准备两个指针，一个是队头指针front指向头结点，另一个rear队尾指针，指向单链表最后一个结点。元素入队就是在rear指针所指指针的后面插入一个新结点，并让rear指针指向这个新结点。（标准单链表的插入）

  1. 出队

而元素出队操作，就是删除第一个数据结点就行了。（标准单链表的删除）。

  1. 特殊状态
  • 队空。什么时候是队空，显然为没有数据结点的时候即为队空即：头结点的next指针为NULL时为队空。
  • 队满。不存在队满的情况（假设内存无限大）。

田静语法

C1-S2-1-2 谓语动词的情态

  • 情态：顾名思义就是“情绪”和“态度”，比如：
    • 你必须把这件事情记牢了。
    • 你没必要这么做。
  • 情态动词用法：接动词原形
  • 情态动词时态：只有现在和过去两种时态。
  • could,would,should,might可以表过去；表委婉；表虚拟。
  • 只有must没有过去时。
  • 情态动词表情态，must语气非常强。
  • 情态动词表推测：可能性最高为must，表示肯定一定；最低为can't,couldn't，表示不可能；其他为可能。

C1-S2-1-3 谓语动词的语态

  • 主动语态，被动语态。主动不用特意学，只用学被动语态

  • 被动语态构成：be+done。

  • 被动语态与时态的结合。

  • 被动语态与情态的结合：情态动词+be done，表示被动的动作与“情态”或“推测”相结合。

C1-S2-1-4 谓语动词的否定

  • 实义动词变否定：前加助动词do/does/did，再加上not，最后加动词原形。
    • American professors did not possess one.
    • They did not fund peer-reviewed research.
  • 助动词和情态动词变否定：直接后加not。
    • To be sure, the future is not all rosy.
    • With other audiences you mustn't attempt to cut in with humor...
  • 如果一个谓语动词中包含多个助动词或情态动词，否定加在第一个后。
    • Such coooperation is likely to be stable only when each animal feel it is not being cheated.

此句中，谓语动词是现在进行时的被动语态is being cheated，其中包含了两个助动词is和being，变否定时，not要加在第一个助动词后，因此变为is not being cheated。

C1-S2-1-5 谓语动词的强调

  • do/does用来强调是现在的动作，did用来强调的是过去的动作。
  • 通常强调谓语动词不用将来时态。