AYZP
0%

数据结构笔记-4-栈和队列

Posted on
Symbols count in article: 3.7k Reading time ≈ 3 mins.

四 栈和队

4.1 栈

4.1.1 简介

栈是一种后进先出的表结构；

栈在软件中的应用：word的撤销功能

image-20200406104212565

栈的后进先出的思想在生活中的应用有：火车道岔；子弹夹

image-20200406103757816

image-20200406104528824

4.1.2 概念

A 定义

只允许在同一个端点处进行插入或删除的表结构称为栈(stack)

image-20200406104827724

  • 栈顶(top)
  • 栈底(bottom)
  • 进栈(push)
  • 出栈(pop)

B 特点

后进先出表、LIFO表

栈结构，像开口向上的圆桶

结点像编了号的木块

C 作用

辅助存储机构：用来存储程序运行期间临时保存的信息。

D 分类

顺序栈

链式栈

4.1.3 顺序栈

A 定义

栈空指针-1，栈空间、数组

1
2
3
#define EMPTY -1	//空栈的栈顶指针
const int m = 1000;	//预定的栈空间大小
int s[m]; //定义顺序栈

程序执行期间，将不定期的进栈、出栈

开始时，栈空，指针top的值等于EMPTY

进出栈算法需能够配合

B 顺序栈的进栈算法

1
2
3
4
5
6
7
8
int push(int s[], int &top, int x) //进栈函数
{
    if (top == m-1) //表示栈满，不能进栈
        return 0;
    s[top] = x;
    top++;
    return 1; //表示进栈成功
}

image-20200406110228651

C 顺序栈的出栈算法

1
2
3
4
5
6
7
8
int pop(int s[], int &top, int &x) //退栈函数
{
    if (top == EMPTY)
        return 0; //表示栈空，不能出栈
    x = [top];
    top--;
    return 1;	//表示出栈成功
}

image-20200406111125503

D 性能分析

时间复杂性：T(n) = O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int push(int s[], int &top, int x)
{// 进栈函数
    if (top == m-1) return FALL;
    s[top] = x;
    top++;
    return SUCC;
}

int pop(int s[], int &top, int &x)
{// 出栈函数
    if (top == EMPTY) return FALL;
    x = s[top];
    top--;
    return SUCC;
}

image-20200406112743880

E 两个堆栈利用空间

1
2
3
4
5
6
typedef strcut stack
{
    int a[N];
    int top1, top2;
}stack;
stack s;

image-20200406115526138

image-20200406115603285

4.1.4 链式栈

链式栈实质就是在头指针处插入删除

A 链式栈入栈出栈算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int push(ptr &top, int x)
{// 进栈
    ptr p;
    p = new snode; //【技巧】申请结点[申请结点后，判断申请的结点的有效性]
    if (p == NULL) return 0; //申请失败
    p->data = x;	//x进栈
    p->next = top; //表头插入法
    top = p;	//修改表头指针
    return 1; //进栈成功
}

int pop(ptr &top, int &x)
{// 退栈
    ptr p;
    if (top == NULL) return 0; //退栈失败
	x = top->data;
    p = top; //表头删除法
    top = top->next;
    free(p);
    return 1; //退栈成功  
}

4.1.5 栈的应用

A 栈在中断中作用

  • 中断：一个程序执行期间，被其他程序所打断
  • 断点：被打断的地方
  • 现场：被打断的程序当前执行情况

保护现场和恢复现场

嵌套中断的现场需要蹭蹭保护，必须“后进先出”——栈

一个现场——栈架（stack frame）

image-20200406114312505

image-20200406114409288

B 简单算术表达式计算

算术表达式的组成：操作符、操作数、运算规则（算符优先级）

B.1 题目

image-20200406114806631

B.2 规则

image-20200406114840999

注：优先级必须高于顶符才能进栈，等于和小于，都是做出栈操作。

B.3 解答步骤（未设置栈底符号）

image-20200406114946653

B.5 符号优先级比较

image-20200406115014481

4.1.6 小结

  • 栈是最常用的表结构
  • 从根本上认识栈的基本原理和操作方法，对于认识程序的嵌套和递归调用，在程序设计中自觉地使用栈具有重要的意义
  • 在应用方面，借助中缀表达式求值算法的原理，进一步理解栈在算法设计中的应用，是非常必要的。

4.2 队列

4.2.1 简介

队列是常用的数据结构，常用来辅助

先进先出

队列常采用循环队列的形式

生活中的例子：

  • 排队打饭：站在队伍头的人先打饭走人，新来的站在队伍最后

4.2.2 概念

A 术语和图示

  • 插入端，队尾(rear)
  • 删除端，对头(front)
  • first和last：分别指向队头元素和队尾元素
  • 进队和出队
    • 出队，首指针往后移
    • 进队，尾指针往后移

image-20200407113821849

B 特点

  • 先进先出
  • 需要考虑的因素
    • 队头、队尾指针
    • 队空队满
    • 如何充分利用已出队元素所占存储单元等诸多因素

4.2.3 顺序队

顺序队的基本用法：收尾指针用法

空队

A 用法[1]，last指向实际队尾、first指向实际队头（麻烦）

麻烦的用法1

B 用法[2]，尾指针last前置

尾指针指向的是下一个元素要进的位置（尾是前移），不是当前队列实际最后一个元素。

image-20200407114815446

C 用法[3]，头指针first后置

头指针指向当前队列最前一个元素的后一位（头是后移）

image-20200407114854455

D 判断队空

first = last=i（i是0~m-1之间的任一值）

E 判断队满

  • 情况1：在程序执行期间，如果要求进队的元素总量不超过数组长度m，不会出现队满情况
  • 情况2：在程序执行期间，需要进队处理的元素总量多于m个，但任何时刻，队中的元素数量始终小于m，仍可使用长度为m的数组存储（不会发生队满）

image-20200407115450196

4.2.4 循环队（环形队，cyclic queue）

A 定义

特点：重复使用已退队元素所占存储单元！

循环队

注意，队尾指针和队头指针其实是对队列总数m取模操作。本质上物理存储还是一个数组。

B 举个栗子

以队尾指针前置环形队为例

image-20200407120438340

1
2
3
4
5
6
7
//元素x进队
q[last] = x;
last = (last+1) % m;

//元素x出队
x=q[first];
first = (first+1) % m;

image-20200407121332112

C 队空队满状态

C.1 判断空

在队列王国里，大家判空都一样

​ first == last

C.2 判断满

image-20200407122239300

开始时，队空，指针first=last=0

若一段时间捏，只进不出，last赶上first，满

若一段时间内，只出不进，first赶上last，空

当first等于last时，无所适从

解决方法：少用一个单元：

因此，常用的计算队列长度公式为：

(last - first + m) % m //m为表长

  • 队空状态：first = last
  • 队满状态：(last+1)%m == first

image-20200407135324816

D 循环对进队出队程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 循环对进队程序
int addq(int q[], int first, int &last, int x)
{
    if ( (last+1)%m == first)
        return 0; //队满
    q[last] = m;
    last = (last+1) % m;
    return 1; //成功
}

// 循环出队程序
int delq(int q[], int &first, int last, int &x)
{
    if ( first == last )
        return 0; //队空
    x = q[first]; //q[first]其实就是q+first的指针
    first = (first+1) % m;
    return 1; //出队成功
}

4.2.5 链式队列

A 概念

链式队可采用单向加头链表结构

first为首指针，last为尾指针

  • 进队：将新结点插在表尾处，last移向新结点

  • 出队：将头结点后的第一个元素出队，删除头结点（头结点不固定）保证尾结点不被删除

  • 判断空：first和last同时执行头结点。first = last

image-20200407142104292

B 进队算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 进队算法
// 没有判断满的指令
// 【技巧】任何算法，都要做好初始化操作：创建单元、判断边界条件
int saddq(prt &last, intx)
{
    p = (ptr)malloc(sizeof(snode));
    if (p == NULL)
        return 0;	//空间分配失败【容易忘】
    p->data = x;
    last->next = p;
    last = p;
    last->next = NULL; //【指针】记得最后一个指针最后赋值为空
    return 1; //进队成功
}

C 出队算法

1
2
3
4
5
6
7
8
9
10
11
12
13
// 出队算法
// 要变的注意取其地址，不需要变得不需要取地址
int sdelq(ptr &first, ptr last, int &x)
{
    ptr p; //用完就删的东西，没必要给他分内存
    if (first == last)
        return 0;	//失败，空队列
    p = first;//表头删除法
    first = p->next; //移动后，first所指为加的头
    x = first->data; //有加头，数据实际在第二个结点
    free(p);
    return 1; //出队成功
}

image-20200407142156917

4.2.6 小结

  • 特点：先进先出
  • 队列通常采用循环队列形式（以尾指针前置为例）
    • 循环队列判空：first == last
    • 循环队列满：(first+1)%m == last

参考文献

[1] 数据结构 – 中国人民解放军陆军工程大学 –陈卫卫、李清等 – 公开课 – 中国大学MOOC

https://www.icourse163.org/course/PAEU-1001660013#/info