数据结构与算法-栈和队列_如何判断栈中元素个数

数据结构与算法-栈和队列

栈的定义

-栈（Stack）是只允许在一端进行插入或删除操作的线性表.

• 栈顶：允许插入和删除的一端
  栈底：不允许插入和删除的一端
• 特点：后进先出 Last In First Out （LIFO）
• 基本操作

//创建，销毁
InitStack(&S);		//初始化栈。构造一个空栈 S，分配内存空间。
DestroyStack(&S);	//销毁栈。销毁并释放栈 S 所占用的内存空间。
//增删
Push(&S,x);			//进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(&S,&x);			//出栈，若栈S非空，则弹出栈顶元素，并用x返回。
//查，仅限栈顶元素
GetTop(S, &x);		//读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素
//其他常用操作
StackEmpty(S)：判断一个栈 S 是否为空。若S为空，则返回true，否则返回false。
1
2
3
4
5
6
7
8
9
10

用顺序表实现的栈（栈顶指针top指向栈顶元素）

定义

Tips: Sq：sequence —— 顺序

初始化栈

进栈操作

也可以写成：

出栈操作

也可以写成：

读栈顶元素

另一种实现：栈顶指针top指向下一个要插入的栈顶位置

• top 初始化时top=0;
• 基本操作相关代码也有区别
  
  
  

共享栈

• 两个栈共享同一片空间
  
• 栈满的条件：top0 + 1 == top1

用链表实现的栈

定义

• 用链式存储的方式实现的栈
  

基本操作

• 入栈和出战的操作都在链表的表头进行。这里讨论的是带头节点的链栈。

初始化栈

bool InitStack(LiStack *top){
     // 为头结点分配存储单元
     if((*top=(LiStack)malloc(sizeof(LiStack)))==NULL){
         return false; 
     }
     // 将头结点的指针域置为空
     (*top)->next = NULL;
}
// 判断栈是否为空
bool StackEmpty(LiStack top){
    if(top->next == NULL){
         return true;
    }else{
         return false;      
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

进栈操作

// 将元素入栈：需要为入栈的结点分配内存
bool PushStack(LiStack top,ElemType e){
    LiStack *p;
    if((p=(LiStack *)malloc(sizeof(LiStack)))==NULL){
         printf("内存分配失败\n");
         return false;
    }
    p->data = e;
    p->next = top->next;
    top->next = p;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

出栈操作

// 将元素出栈：需要释放结点空间
bool PopStack(LiStack top,ElemType *e){
    LiStack *p;
    p = top->next;
    if(!p){
         printf("栈已空\n");
         return false; 
    }
    top->next = p->next;
    *e = p->data;
    free(p);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

读栈顶元素

// 取栈顶元素：需要对边界做判断（栈是否为空）
bool GetTop(LiStack top,ElemType *e){
    LiStack *p;
    p = top->next;
    if(!p){
         printf("栈已空\n");
         return false; 
    }
    *e = p->data;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

队列的定义

-队列(Queue)是只允许在一端进行插入,在另一端删除的线性表

• 特点: 先进先出(FIFO)
• 基本操作

//创建销毁
InitQueue(&Q);		//初始化队列,构造一个空队列Q。
DestroyQueue(&Q);	//销毁队列。销毁并释放队列Q所占用的内存空间。
//增加删除
EnQueue(&Q,x);		//入队,若队列Q未满,将x加入,使之成为新的队尾。
//删除队头元素 
DeQueue(&Q,&x);		//出队,若队列Q非空,删除队头元素,并用x返回。
//查: 队列的使用场景中大多只访问队头元素
//不删除队头元素 
GetHead(Q,&x);		//读队头元素,若队列Q非空,则将队头元素赋值给x。
//其他常用操作:
QueueEmpty(Q);		//判队列空,若队列Q为空返回true,否则返回false。
1
2
3
4
5
6
7
8
9
10
11
12

队列的顺序实现(循环队列)

定义

• fron: 指向队头元素
• rear: 指向队尾元素的后一个位置(下一个应该插入的位置)

初始化

入队操作

• 普通队列的缺点:
  无法根据条件rear==MaxSize来判断队列已满,因为可能有队头的元素出栈,而此时空闲出来的控空间无法复用.
• 故使用循环队列,将存储空间在逻辑上变成了“环状”,配合模运算实现元素位置的映射:
  使用(Q.rear+1)%MaxSize==Q.front作为队列已满的条件.代价: 牺牲一个存储单元.
• 队列元素个数: rear+Maxsize-front
  

出队操作

查找

其他要点

• 若要求不牺牲一个任何单元.可以在队列定义时增加size字段.
  初始化时: size=0;
  插入成功: size++;
  删除成功时: size–;
  队满条件: size = MaxSize

• 或增加tag字段,每次只有删除操作,才可能导致队空;只有插入操作,才可能导致队满
  插入成功: tag=1;
  删除成功时: tag=0;
  初始化时: rear=front=0;tag = 0;
  队满条件: front==rear && tag == 1
  对空条件: front==rear && tag == 0

• 注意区分rear指向队尾元素的最后一个位置还是指向了队尾元素.
  Tips:
  指向队尾元素时,初始化可以让rear指向front的后一个元素位置.此时可以使用(Q.rear+1)%MaxSize==front来判空,而若想判满此时应该+2,仍然会空闲出来一个单元.当然也可以使用增加辅助变量的方法.

队列的链式存储实现

定义

初始化(带头节点)

初始化(不带头节点)

入队操作(带头节点)

入队操作(不带头节点)

出队操作(带头节点)

出队操作(不带头节点)

其他

• 链式存储——一般不会队满,除非内存不足

双端队列

• 栈 :只允许一端插入和删除的线性表删除
• 队列: 只允许从一端插入、另一端删除的线性表
• 双端队列 :只允许两端插入、两端删除的线性表
  • 输入受限的双端队列 :只允许从一端插入、两端删除的线性表
  • 输出受限的双端队列 :只允许从两端插入、一端删除的线性表

卡特兰数

用于算栈的合法输出序列的个数,n为元素个数.

注意

• 栈中合法的序列,双端队列中一定也合法

栈的应用

栈的应用-括号匹配

原理:
(1) 遇到左括号就入栈;
(2) 遇到右括号,就 “消耗”一个左括号(出栈),并比较左括号和右括号种类是否匹配;若不匹配,报错;
(3) 若左括号不足,报错;
(4) 遍历结束后,检查栈是否为空,不为空说明左括号多余,报错.

其中的基本操作如下,考试的时候仅做说明后直接使用即可.

栈的应用-表达式求值

• 中缀表达式: 运算符在两个操作数中间
  如: a+b-c* d

• 前缀表达式: 运算符在两个操作数前面
  如: -+ab* cd

• 后缀表达式: 运算符在两个操作数后面
  如: ab+cd* -

• 中缀表达式转后缀表达式(手算)
  (1) 确定中缀表达式中各个运算符的运算顺序
  (2) 选择下一个运算符,按照「左操作数 右操作数 运算符」的方式组合
  (3) 如果还有运算符没被处理,就继续(2)
  Tips:
  同一个中缀表达式的运算顺序可能不唯一,因此对应的后缀表达式也可能不唯一.但是为了保证手算和机算结果相同 应采取“左优先”原则:只要左边的运算符能先计算,就优先算左边的.如下所示的例子就使用了左优先.
  

• 中缀表达式转后缀表达式(机算)
  用栈实现中缀表达式转后缀表达式：
  初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
  从左到右处理各个元素，直到末尾。可能遇到三种情况：
  ① 遇到操作数。直接加入后缀表达式。
  ② 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹
  出“(”为止。注意：“(”不加入后缀表达式。
  ③ 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(” 或栈空则停止。之后再把当前运算符入栈。
  按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
  Tips:
  下面的代码中的操作符优先级通过巧妙的设置避免了"()"的特殊处理，但流程和原理和上述一致。

• 后缀表达式的计算（手算）
  从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，
  合体为一个操作数
  

• 后缀表达式的计算（机算）
  用栈实现后缀表达式的计算：
  ①从左往右扫描后缀表达式，直到处理完所有元素
  ②若扫描到操作数则压入栈，并回到①；否则执行③
  ③若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到①
  Tips:
  注意：先出栈的是“右操作数”

• 中缀表达式计算（计算）
  即中缀转后缀+后缀表达式求值两个算法的结合,代码如下：

#include<iostream>
#include <stack>
#include<map>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

using namespace std;

int Complete(int a,int b,char c){
    if(c=='+'){
        return a+b;
    }else if(c=='-'){
        return a-b;
    }else if(c=='*'){
        return a*b;
    }else
       return a/b;
}
//void InitS()；
//把中缀表达式转化为后缀表达式并计算  输入形如：1+2-3*((4+5)/3-6)+7e，e为表达式结束标志
//Tips: 仅支持10以内的加减乘除，因为输入以单字符为一个操作数
int main(){
    map<char,int> ispM;
    map<char,int> icpM;
    stack<int> s1;
    stack<char> s2;
    char res[20];
    ispM['#']=0;ispM['(']=1;ispM['*']=ispM['/']=5;ispM['+']=ispM['-']=3;ispM[')']=6;
    icpM['#']=0;icpM['(']=6;icpM['*']=icpM['/']=4;icpM['+']=icpM['-']=2;icpM[')']=1;

    s2.push('#');
    char c;
     //InitS();
     int coun=0;
    memset(res,0,sizeof(res));
    while(scanf("%c",&c)!=EOF)
    {
        if(c=='e') 
        {
            while (s2.top() != '#')
            {
                res[coun++]=s2.top();
                s2.pop();
            }
            break;
        }
        if(c>='0'&&c<='9')
        {
            res[coun++]=c;
        }
        else
        {
            if(ispM[s2.top()]>icpM[c])
            {
	            while(ispM[s2.top()]>icpM[c])
	            {
	                res[coun++]=s2.top();
	                s2.pop();
	            }
            }
            if(ispM[s2.top()]<icpM[c])
            {
                s2.push(c);
            }
            if(ispM[s2.top()]==icpM[c])
            {
                s2.pop();
            }
        }
    }
    //输出转化后的后缀表达式
    cout << res <<endl;
    //使用后缀表达式计算表达式的值
    for(int i=0;i<coun;i++){
        if(res[i]>='0'&&res[i]<='9'){
            s1.push(res[i]-'0');
        }else  {
            int t1=s1.top();
            s1.pop();
            int t2=s1.top();
            s1.pop();
            int newdata=Complete(t2,t1,res[i]);
            s1.push(newdata);
        }
    }
    cout<<s1.top()<<endl;
    s1.pop();


    return 0;
}

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94