线性表之堆栈

发表于 | 分类于 | | 浏览 次
字数统计: 1,766 字 | 阅读时长 ≈ 7 分钟

本文重温一种常见的线性表—-堆栈。
主要包含如下内容:

  • 问题引入
  • 堆栈的抽象数据类型描述
  • 堆栈的顺序存储实现
  • 堆栈的链式存储实现
  • 堆栈的应用

注意:虽然我们堆栈堆栈的叫，但是要注意不要混淆堆和栈，从其英文名字Stack可以看出这里的堆栈其实是栈，本文中的堆栈均指的是栈。

问题引入

计算机如何进行表达式求值？
例如：算术表达式5+6/2-3 * 4 。
正确理解：
5+6/2-3*4 = 5+3-3 * 4 = 8-3*4 = 8-12 = -4
 由两类对象构成的：
 运算数，如2、3、4
 运算符号，如+、-、*、/
 不同运算符号优先级不一样

中缀表达式 : 运算符号位于两个运算数之间。如 如 ，a + b c - d / e
后缀表达式 : 运算符号位于两个运算数之后。如， a b c + d e / -

后缀表达式求值策略：从左向右“扫描”，逐个处理运算数和运算符号

  1. 遇到运算数怎么办？如何“记住”目前还不未参与运算的数？
  2. 遇到运算符号怎么办？对应的运算数是什么？

启示： 要是有种数据结构，能顺序存储运算数，
并在需要时“倒序”输出就好了，还真有，那就是堆栈！

堆栈的抽象数据类型描述

堆栈(Stack) ： 具有一定操作约束的线性表
只在一端（栈顶，Top）做插入、删除操作

 插入数据 ： 入栈（Push ）
 删除 数据 ： 出栈（Pop ）
 后入先出： ：Last In First Out （LIFO）

类型名称: 堆栈（Stack ）
数据对象集： 一个有0 个或多个元素的有穷线性表。
操作集： 长度为MaxSize 的堆栈S ∈ Stack ，堆栈元素item ∈ ElementType
1 、Stack CreateStack( int MaxSize ) ： 生成空堆栈，其最大长度为MaxSize ；
2 、int IsFull( Stack S, int MaxSize ) ：判断堆栈S 是否已满；
3 、void Push( Stack S, ElementType item ) ：将元素item 压入堆栈；
4 、int IsEmpty ( Stack S ) ：判断堆栈S 是否为空；
5 、ElementType Pop( Stack S ) ：删除并返回栈顶元素；

Push 和 Pop 可以穿插 交替 进行；
按照操作系列
(1)Push(S,A), Push(S,B),Push((S,C),Pop(S),Pop(S),Pop(S)
堆栈输出是？
(2) 而Push(S,A), Pop(S),Push(S,B),Push((S,C),Pop(S),Pop(S)
堆栈输出是?

答案：（1）CBA （2）ACB

思考：如果三个字符按ABC顺序压入堆栈
• ABC 的所有排列都可能是出栈的序列 吗？
• 可以产生CAB这样的序列吗？

栈的顺序存储实现

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

1
2
3
4
5
6
7
#define MaxSize < 储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode
{
    ElementType Data[MaxSize];
    int Top;
};

  • 入栈
1
2
3
4
5
6
7
8
9
10
11
12
void Push(Stack PtrS, ElementType item)
{
    if(Ptrs->Top == MaxSize-1)
    {
        printf("Stack is full!");
        return;
    }
    else
    {
        PtrS->Data[++(PtrS->Top)] = item;
    }
}
  • 出栈
1
2
3
4
5
6
7
8
9
10
11
12
ElementType Pop( Stack PtrS )
{
    if ( PtrS->Top == -1 )
    {
        printf(“ 堆栈空”);
        return ERROR; /* ERROR 是ElementType 的特殊值，标志错误*/
    }
    else
    {
        return (PtrS->Data[(PtrS->Top)--]);
    }
}

[练习]
请用一个数组实现两个堆栈，要求最大地利用数组空间，使
数组只要有空间入栈操作就可以成功。

【分析】 一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#define MaxSize < 存储数据元素的最大个数>
struct DStack
{
    ElementType Data[MaxSize];
    int Top1; /*  堆栈１的栈顶指针 */
    int Top2; /*  堆栈２的栈顶指针 */
} S;
S.Top1 = -1;
S.Top2 = MaxSize;

void Push( struct DStack *PtrS, ElementType item, int Tag )
{
    /* Tag作为区分两个堆栈的标志，取值为1和2 */
    if ( PtrS->Top2 – PtrS->Top1 == 1)
    { /*堆栈满*/
        printf(“ 堆栈满”); return ;
    }
    if ( Tag == 1 ) /* 对第一个堆栈操作 */
        PtrS->Data[++(PtrS->Top1)] = item;
    else /* 对第二个堆栈操作 */
        PtrS->Data[--(PtrS->Top2)] = item;
}


ElementType Pop( struct DStack *PtrS, int Tag )
{
    /* Tag作为区分两个堆栈的标志，取值为1和2 */
    if ( Tag == 1 )
    {
        /* 对第一个堆栈操作 */
        if ( PtrS->Top1 == -1 )
        {
            /*堆栈1空 */
            printf(“ 堆栈1 空”); return NULL;
        }
        else
            return PtrS->Data[(PtrS->Top1)--];
    }
    else
    { /* 对第二个堆栈操作 */
        if ( PtrS->Top2 == MaxSize )
        { /*堆栈2空 */
            printf(“ 堆栈2 空”);
            return NULL;
        }
        else
            return PtrS->Data[(PtrS->Top2)++];
    }
}

堆栈的链式存储实现

栈的链式存储结构 实际上就是一个单链表，叫做链栈 。插入和删
除操作只能在链栈的栈顶进行。 那栈顶指针Top应该在链表的哪一头呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
typedef struct SNode *Stack;
struct SNode
{
    ElementType Data;
    struct SNode *Next;
};


Stack CreateStack()
{
    /*  构建一个堆栈的头结点，返回指针 */
    Stack S;
    S =(Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

int IsEmpty(Stack S)
{
    /* 判断堆栈S 是否为空 ， 若为空函数返回整数1 ， 否则返回0 */
    return ( S->Next == NULL );
}


void Push( ElementType item, Stack S)
{
    /*  将元素item 压入堆栈S */
    struct SNode *TmpCell;
    TmpCell= (struct SNode *)malloc(sizeof(struct SNode));
    TmpCell->Element = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}



ElementType Pop(Stack S)
{
    /*  删除并返回堆栈S 的栈顶元素 */
    struct SNode *FirstCell;
    ElementType TopElem;
    if( IsEmpty( S )
    {
        printf(“ 堆栈空”); return NULL;
    }
    else
    {
        FirstCell = S->Next;
        S->Next = FirstCell->Next;
        TopElem = FirstCell ->Element;
        free(FirstCell);
        return TopElem;
    }
}

堆栈的应用

中缀表达式求值

基本策略：将中缀表达式转换为后缀表达式，然后求值
如何将中缀表达式转换为后缀？
观察一个简单例子： 2+9/3-5 -> 2 9 3 / + 5 -

  1. 运算数相对顺序不变
  2. 运算符号顺序发生改变
     需要存储“等待中”的运算符号
     要将当前运算符号与“等待中”的最后一个运算符号比较

中缀表达式如何转换为后缀表达式

从头到尾读取中缀表达式的每个对象 ，对不同对象按不同的情况处理。
① 运算数：直接输出；
② 左括号：压入堆栈；
③ 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（ 出栈，不输出）；
④ 运算符：
• 若优先级大于栈顶运算符时，则把它压栈；
• 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比
较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
⑤ 若各对象处理完毕，则把堆栈中存留的运算符一并输出。

堆栈的其他应用：

 函数调用及递归实现
 深度优先搜索
 回溯算法
…

参考资料

[浙江大学PTA]

[浙江大学数据结构公开课]

如果你觉得本文对你有帮助，欢迎打赏