数据结构与算法--栈

知识回顾

• 顺序表：使用一组地址连续的存储单元依次存储线性表中的元素。
• 单链表：使用一组地址任意的存储单元依次存储线性表中的元素。

顺序存储结构的优缺点

优点：

• 比较简单。
• 随机存取，存取速度快。
• 每个结点只存储元素自身信息，不需额外空间。

缺点：

• 需占一片连续的存储空间，且需事先估计存储空间的大小。
• 插入和删除操作时，需移动大量的元素，效率较低。

链式存储结构的优缺点

优点：

• 不需占用连续存储空间，使用链表前不用事先估计存储空间大小。
• 插入和删除操作时，不需要移动大量元素。

缺点：

• 操作算法较复杂。
• 不能随机存取。
• 需要额外空间来表示元素间的关系，空间代价较高。

数据结构的三个方面

1. 数据的逻辑结构：线性结构、非线性结构。
2. 数据的存储结构（亦称物理结构）：顺序存储、链式存储。
3. 数据的运算：检索、排序、插入、删除、修改等。

栈的定义与特点

• 栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。

• 

• 允许插入和删除运算的一端称为栈顶（top），不允许插入和删除的另一端称为栈底（bottom）。

• 在栈顶进行的插入操作称为入栈或进栈(push),在栈顶进行的删除操作称为出栈或退栈(pop)

• 特点：后进先出（LIFO, Last In First Out）。

• 

栈的基本运算

• 栈抽象数据类型＝逻辑结构＋基本运算（运算描述）

• InitStack(&s)：初始化栈。构造一个空栈s。
  1

• DestroyStack(&s)：销毁栈。释放栈s占用的存储空间。
  1

• StackEmpty(s)：判断栈是否为空:若栈s为空，则返回真；否则返回假。
  1

• Push(&S，e)：进栈。将元素e插入到栈s中作为栈顶元素。
  1

• Pop(&s，&e)：出栈。从栈s中退出栈顶元素，并将其值赋给e。
  1

• GetTop(s，&e)：取栈顶元素。返回当前的栈顶元素，并将其值赋给e。
  1

• 入栈（push）：在栈顶进行的插入操作。
• 出栈（pop）：在栈顶进行的删除操作。

栈的存储结构与实现

顺序栈

• 栈中元素逻辑关系与线性表的相同，栈可以采用与线性表相同的存储结构。
• 使用数组表示栈。
• 栈顶通过下标指示。
• 如何用数组表示栈？
  • 存储栈元素
  • 栈的逻辑结构表示
  • 指示栈的栈顶
    

#define MaxSize 100 // 定义常量MaxSize为100，作为栈的最大容量

// 定义ElemType类型，这里假设ElemType是某种基本数据类型，比如int
typedef int ElemType;

// 定义顺序栈的结构体
typedef struct {
    ElemType data[MaxSize]; // 一个数组，用于存储栈中的元素，大小为MaxSize
    int top;                // 一个整型变量，用于指向栈顶元素的索引
} SqStack; // 用typedef为这个结构体定义一个新的类型名SqStack，代表顺序栈
1
2
3
4
5
6
7
8
9
10

MaxSize为顺序栈的最大容量；
top为栈顶元素的下标，0 <= top <= MaxSize-1
栈空：top = -1;
栈满：top = MaxSize-1

入栈操作

• 操作步骤：
  ①判断栈是否已满，若满则产生上溢出错误，退出算法，否则执行第②步；
  

②栈顶下标增一，指向新的栈顶位置；

③将新元素置于栈顶。

bool Push(SqStack &S, ElemType item)
{
  if (S.top == MaxSize - 1)
  {
    cout << "栈满" << endl;
    return false;
  }
  S.top++;
  S.data[S.top] = item;
  return true;
}
1
2
3
4
5
6
7
8
9
10
11

出栈操作

操作步骤：
①判断栈是否为空，若空则产生下溢出错误，退出算法，否则执行第②步；

②栈顶元素出栈；

③栈顶下标减一，指向新的栈顶位置；

bool Pop(SqStack &S, ElemType &item)
{
  if (S.top == -1)
  {
    cout << "栈空" << endl;
    return false;
  }
  item = S.data[S.top];
  S.top--;
  return true;
}
1
2
3
4
5
6
7
8
9
10
11

链栈

• 使用链式结构表示栈。
• 栈顶通过指向单链表第一个元素结点的位置指示。
• 如何用链式结构表示栈？
  如何存储栈元素
  怎样表示栈的逻辑结构
  怎样指示栈的栈顶
  

typedef struct LNode
{
  ElemType data;      //数据域
  struct LNode *next; //后继结点指针
} LinkStNode;         //链栈结点类型
1
2
3
4
5

• S：单链表头指针，指向头结点。
• 栈顶：单链表第一个元素结点的位置，即头结点的后一个位置。
• 

入栈操作

bool Push(LinkStNode *S, ElemType item)
{ //带头结点单链表的表头插入法
  LinkStNode *t = new LinkStNode; //①生成新结点
  if (t == NULL)
  {
    cout << "内存不足";
    return false;
  }
  t->data = item;
  //②在栈顶插入新结点
  t->next = S->next;
  S->next = t; //③
  return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

入栈操作

bool Pop(LinkStNode *S, ElemType &item)
{ //删除单链表的第一个元素结点
  //①判断栈是否为空
  if (S->next == NULL)
  {
    cout << "栈空";
    return false;
  }
  //②删除栈顶元素
  LinkStNode *t = S->next;
  S->next = t->next;
  item = t->data;
  delete t;
  return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

栈的应用

数制转换

• 原理：基于除留余数法。
  • 十进制数N和其他d进制数的转换基于下列原理：
  • N = (N div d)×d + N mod d (div 为整除，mod 为求余)
• 操作步骤：将数字除以进制数，取商和余数，直至商为零。
  • ① 将N除以d，取其商和余数；
  • ② 判断商是否为零；
  • 若商不为零，则将商赋值给N，并转向① ；
  • 若商为零，则转换结束。
    最先求得的余数是结果的最低位，最后求得的余数是结果的最高位，即运算顺序与结果的各位数字的次序相反，符合栈的特点。

void Convert(int num, int d)
{ //num为待转换数，d为进制
  SqStack S;  ElemType result;  int r; //余数
  char ch[] = "0123456789ABCDEF"; //进制所使用的字符
  InitStack(S);
  while (num != 0)
  { r = num % d;    //取余数r
    Push(S, ch[r]); //余数入栈
    num = num / d;  //利用商进行下一次运算
  }
  while (!StackEmpty(S))
  { Pop(S, result);
    cout << result;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

表达式求值

• 算术表达式的定义：任何一个表达式都是由操作数、运算符和界限符组成。

• 算术表达式的三种形式：前缀、中缀、后缀。

  • 前缀表达式=运算符＋操作数1＋操作数2
  • 中缀表达式=操作数1＋运算符＋操作数2
  • 后缀表达式=操作数1＋操作数2＋运算符

• 中缀表达式的运算规则和特点。

  • 先计算括弧内后计算括弧外；
  • 在无括号或同层括号内时，先乘除后加减；
  • 同一优先级运算，先左后右。
  • 示例：
    • 16-4×（2+1）
    • 结果：4
    • （110＋16）/（16-9×(4+3))
    • 结果：-2
    • 中缀表达式的运算不一定能按运算符出现的先后次序进行，它不仅要依赖运算符优先级,而且还要处理括号。
      因此，中缀表达式不方便计算机程序对表达式进行求值。

• 后缀表达式的特点与运算规则。

  • 后缀表达式没有括号，也无需考虑优先级，运算符在式中出现的顺序恰为表达式的运算顺序；方便程序进行求值。
  • 对比：
  • 中缀表达式：
  • a - b * ( c / d ) + e
  • 后缀表达式：
  • a b c d / * - e +

中缀表达式向后缀表达式的转换

• 转换思路：根据运算符的优先级决定运算顺序。
  • 对原表达式中出现的每一个运算符是否即刻进行运算取决于在它后面出现的运算符；
  • 如果它的优先级“高或等于”后面的运算，则它的运算先进行，否则就得等待在它之后出现的所有优先级高于它的“运算”都完成之后再进行。
• 使用栈存放运算符。
  • （ ）
  • × ÷
  • ＋ －

用到的数据结构：
char数组 str1：存放中缀表达式，以 # 结尾；
char数组 str2：存放转换后的后缀表达式；
char型栈 S：存放运算符，包括 * / + - （ #
其中，* / 优先级设为2，
+ - 优先级设为1，
为处理方便，将 ( 优先级设为3，# 优先级设为0

while(str1[i] != ‘\0’)

• 如果str1[i]是操作数，则将str1[i]存到str2中；
• 如果str1[i]是‘(’，则str1[i]入栈；
• 如果str1[i]是‘)’，则将栈S中‘(’之前的运算符依次出栈并存放到str2中,然后将栈S中‘(’出栈；
• 如果str1[i]是四则运算符，则还须比较str1[i]与栈顶运算符top的优先级，若str1[i] ≤ top (除栈顶- 运算符为“(”外)，则依次出栈并存入到str2中，然后将str1[i]进栈；
  str1扫描完毕后，将栈S中剩余运算符依次出栈并存入str2中。

后缀表达式的求值过程

• 从左向右扫描后缀表达式，操作数入栈，运算符出栈操作数并执行运算。
• 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式；
• 对后缀式从左向右“扫描”，若读入的是一个操作数，就将它入数值栈；
• 若读入的是一个运算符op，就从数值栈中连续出栈两个元素(两个操作数)，假设为x2和x1，计算x1 op x2之值，并将计算结果入数值栈；
• 对整个后缀表达式读入结束时，栈顶元素就是计算结果。

总结

• 栈的后进先出特性。
• 顺序栈和链栈的入栈、出栈操作。
• 栈在中缀表达式转换为后缀表达式中的应用。