编辑
2022-09-29
数据结构
00
请注意,本文编写于 546 天前,最后修改于 500 天前,其中某些信息可能已经过时。

目录

第三章 栈和数列
3.1 栈
1. 定义
2. 栈的存储结构
3.2 队列
1. 定义
2. 队的存储结构

本章重点

栈和队列的特性和基本操作,出栈顺序,输出队列。

第三章 栈和数列

3.1 栈

1. 定义

  • 栈(stack:只允许在一端进行插入或删除操作的线性表;
  • 栈顶:线性表允许进行插入删除操作的一端,栈顶指针:S.top
  • 栈底:固定不允许进行插入删除操作的一端;
  • 空栈:为存储任何元素的栈。空栈条件:栈顶指针指向栈底;
  • 结构特性:先进后出(LIFO)。

2. 栈的存储结构

  1. 顺序栈:栈的顺序存储结构,运用一组地址连续的存储单元依次存储自栈底到栈顶的数据元素,指针top指示栈顶元素在顺序栈中的位置;
    1. 进栈:若栈不满,栈顶指针+1,赋值栈顶元素;
    2. 出栈:若栈非空,取出栈顶元素,栈顶指针-1;
  2. 链栈:采用链式存储,优点是便于多个栈共享存储空间和提高效率,避免栈上溢。通常采用单链表实现,在表头进行插入删除操作。

3.2 队列

1. 定义

  • 队列(queue:只允许在表的一端进行插入,在另一段删除;
  • 队尾(rear:允许插入的一端;
  • 队头(front:允许删除的一端;
  • 结构特性:先入先出(FIFO)。

2. 队的存储结构

  1. 顺序结构:用一组地址连续的存储单元依次存储从队头到队尾的元素,需要队头指针(front)和队尾指针(rear);
    1. 初始化空队列:front = rear = 0
    2. 插入新元素时队尾指针增一,删除队尾指针是队头指针增一;
    3. 头指针永远指向向头元素、尾指针永远指向向尾元素;
  2. 双端队列:两端都可以输入输出,实际使用中还有输出受限的双端队列,输入受限的双端队列(先指某一端只能输入或限制某一端只能输出);
  3. 链队列:用链表表示的队列,需要定义队头和队尾指针;
    1. 判空条件front == rear
  4. 循环队列:解决顺序队列假溢出,把存储队列从逻辑上视为环状。当队头指针Q.front = Maxsize - 1时,再前进一个位置自动到0,通过取余实现;
    1. 初始化Q.front = Q.rear = 0;
    2. 队头指针进1:Q.front = (Q.front + 1) % MaxSize;
    3. 队尾指针进1:Q.rear = (Q.rear + 1) % MaxSize;
    4. 判空
      1. 另设一个标志位区分空还是满;
      2. 少用一个空间元素,以“队头指针在队尾指针的下一个位置上”表示满状态
    5. 队满条件(Q.rear + 1) % MaxSize == Q.front;
    6. 队空条件Q.front == Q.rear;
    7. 队列中元素的个数(Q,rear - Q.front + MaxSize) % MaxSize;
如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:Handy Zhang

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!