【栈和队列】

一、栈

1.1、栈的基本概念

  1. 只允许在一端(栈顶top)进行插入和删除操作的受限的线性表;
  2. 遵循后进先出(last in first out)LIFO原则。
    在这里插入图片描述

1.2、栈的基本操作

1. InitStack(&S): 初始化栈,构造一个空栈,分配内存空间;
**2. DestroyStack(&S):**销毁栈,销毁并释放栈S所占用的空间
3. Push(&S, x): 进栈,若栈S未满,则将元素x加入其中使其成为新的栈顶元素;
4. Pop(&S, x): 出栈,若栈S非空,则弹出(删除)栈顶元素,并用x返回;
5. GetTop(S, &x): 读取栈顶元素,若栈S非空,则用x返回栈顶元素;
6. StackEmpty(S): 判空,判断栈S是否为空,若S为空,则返回true,否则返回false。

1.3、栈的顺序存储实现

1.3.1、顺序栈的定义

#define MaxSize 10;//定义栈内元素的最大个数

typedef struct{
    ElemType data[MaxSize];//静态数组存放栈的元素
    int top;//栈顶元素
}SqStack;

void testStack(){
    SqStack S;//声明一个顺序栈(分配空间)
}

1.3.2、顺序栈的初始化

#define MaxSize 10;

typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;

void initStack(SqStack &S){
    S.top = -1;//初始化栈顶指针
}

bool EmptyStack(SqStack S){
    if(S.top == -1)
        return true;
    else return false;
}

1.3.3、顺序栈的入栈和出栈

上溢:满栈时入栈
下溢:空栈时出栈

//进栈
bool Push(SqStack &S, ElemType x){
    if(S.top == MaxSize - 1)    //判断栈是否为满
        return false;
     S.data[++S.top] = x;      //栈顶指针先加1,再送值到栈顶元素
     return true;
}
//出栈
bool Pop(SqStack &S, ElemType x){
    if(S.top == -1)
        return false;
    x = data[S.top--];          //先取栈顶的值,再将栈顶指针减1
    return true;
}

1.3.4、读取栈顶元素

bool GetElem(SqStack S, ElemType x){
    if(S.top == -1)
        return false;
    x = data[S.top];
    return true;
}

1.3.5、共享栈(即两个栈共享同一片空间)

共享栈是特殊的顺序栈,将栈底设置在共享空间的两端,栈顶向中间靠拢。

#define MaxSize 10;

typedef struct{
    ElemType data[MaxSize];
    int top0;           //0号栈的栈顶指针
    int top1;           //1号栈的栈顶指针
}ShStack;

void initSqStack(ShStack &S){
    S.top0 = -1;
    S.top1 = MaxSzie;
}

1.4、栈的链式存储实现

1.4.1、链栈的定义

采用链式存储的栈被称为链栈。

优点:便于多个栈共享存储空间和提高效率,且不存在满栈上溢的情况。

链表的头部作为栈顶,意味着:

  1. 在实现数据入栈时,需要将数据从链表的头部插入(头插);
  2. 在实现数据的出栈时,需要删除链表头部的收元结点。
    因此,链栈就是一个只能采用头插法插入或删除数据的链表。
typedef struct{
    ElemType data;
    Linknode *next;
}Linknode, *LinkStack;

//初始化链栈
void initStack(LinkStack &L){
     L = (Linknode*)malloc(sizeof(Linknode));
     if(L == NULL)
         return false;
     L->next = NULL;
     return true;
}
//判断链栈是否为空
bool EmptyStack(LinkStack L){
    if(L->next == NULL)
        return true;
    else return false;
}

1.4.2、链栈的入栈和出栈

typedef struct{
    ElemType data;
    Linknode *next;
}Linknode, *LinkStack;

//入栈(头插)
bool pushStack(LinkStack &L, ElemType x){
   *s = (Linknode*)malloc(sizeof(Linknode));
   if(s == NULL)
       return false;
   s->next = x;
   s->next = L->next;
   L->next = s;
   return true;
}
//出栈
bool popStack(LinkStack &L, Elemtype x){
    if(L == NULL)
        return false;
    Linknode *s = L->next;
    x = L->next;
    L->next = s->next;
    free(s);
    return true;
}

二、队列

2.1、队列的基本概念

  1. 只允许在一端(队尾)进行插入操作,在另一端(队首)进行删除操作的受限的线性表。
  2. 遵循先进先出(first in first out)FIFO原则。

2.2、队列的基本操作

  1. initQueue(&Q):初始化队列,构造一个空队列Q;
  2. EmptyQueue(Q):判空,判断队列Q是否为空,若为空返回true,否则返回false;
  3. EnQueue(&Q, x):入队,若队列未满,则把元素x加入Q,使之成为新的队尾;
  4. DeQueue(&Q, x):出队,若队列非空,则删除队首元素,并用x返回元素值;
  5. GetQueue(Q,&x):读取队首元素,若队列非空,则用x返回队首元素;
  6. ClearQueue(&Q):销毁队列并释放队列Q所占用的空间。

2.3、队列的顺序存储实现

队首指针front:指向队首元素
队尾指针rear:指向队尾元素的下一个位置

2.3.1、顺序队列的定义

#define MaxSize 10;

typedef struct{
    ElemType data[MaxSize];//用静态数组存储队列元素
    int front;          //队首指针
    int rear;           //对尾指针
}SqQueue;

void test(){
    SqQueue Q;//声明一个队列
}

2.3.2、顺序队列的初始化

#define MaxSize 10;

typedef struct(){
     ElemType data[MaxSize];
     int front;
     int rear;
}SqQueue;

void initQueue(SqQueue &Q){
    //初始化时,队尾和队首指针都指向0
    Q.front = Q.rear = 0;
}
//判空
bool EmptyQueue(SqQueue){
    if(Q.front == Q.rear)
        return true;
    else return false;
}

2.3.3、入队出队(循环队列)

#define MaxSize 10;

typedef struct{
    ElemType data[MaxSize];
    int front;
    int rear;
}SqQueue;
//入队
bool EnQueue(SqQueue &Q, ElemType x){
    if((Q.rear+1)%MaxSize == Q.front)
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1)%MaxSize;//通过取余的方式实现循环队列
    return true;
}
//出队
bool DeQueue(SqQueue &Q, ElemType x){
    if(Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1)%MaxSize;
    return true;
}

注意判满和判空的条件!

2.3.4、获取队首元素

#define MaxSize 10;

typedef struct{
    ElemType data[MaxSize];
    int front;
    int rear;
}SqQueue;

//获取队首元素
void GetQueue(SqQueue Q, ElemType x){
    if(Q.rear == Q.front)
        return false;
    x = Q.data[Q.front]
    return true;
}

2.4、队列的链式存储实现

2.4.1、链队列的定义

//链式队列的结点

typedef struct{
    ElemType data;
    Linknode *next;
}Linknode;

//链式队列
typedef struct{
    //头尾指针
    Linknode *front, *rear;
}LinkQueue;

2.4.2、链式队列的初始化

带头结点的链式队列初始化:

typedef struct{
    ElemType data;
    Linknode *next;
}Linknode;

typedef struct{
    LinkQueue *front, *rear;
}LinkQueue;

void initLinkQueue(LinkQueue &O){
    //初始化时,头尾指针均指向头结点
    Q.front = Q.rear =(Linknode*)malloc(sizeof(Linknode));
    Q.front->next = NULL;
}
//判空
bool EmptyQueue(LinkQueue Q){
    if(Q.front == Q.rear)
        return true;
    else return false;
}

2.4.3、入队出队(带头结点)

typedef struct{
    ElemType data;
    Linknode *next;
}Linknode;
typedef struct{
    LinkQueue *front, *rear;
}LinkQueue;
//入队
void EnQueue(LinkQueue &Q, ElemType x){
    Linknode *s = (Linlnode*)malloc(sizeof(Linknode));
    if(s == NULL)
        return false;
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}
//出队
bool DeQueue(LinkQueue &Q, ElemType x){
    if(Q.front == Q.rear)
        return false;
    Linknode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if(Q.rear == p)
       Q.rear = Q.front;
    free(p);
    return true;
}

2.4.4、不带投结点的链式队列

typedef struct{
    ElemType data;
    Linknode *next;
}Linknode;
typedef struct{
    LinkQueue *front, *rear;
}LinkQueue;
//初始化
void initQueue(LinkQueue &Q){
    Q.front == NULL;
    Q.rear = NULL;
}
//判空
bool EmptyQueue(LinkQueue Q){
    if(Q.front == Q.rear)
        return true;
     else return false;
}
//入队
void EnQueue(LinkQueue &Q, ElemType x){
    Linknode *s =(Linknode*)malloc(sizeof(Linknode));
    s->data = x;
    s->next = NULL;
    //第一个元素入队时需要特殊处理
    if(Q.front == NULL){
        Q.front = s;
        Q.rear = s;
        }
        else{
            Q.rear->next = s;
            Q.rear = s;
        }
}
//出队
bool DeQueue(LinkQueue &Q, ElemType x){
    if(Q.front == NULL)
        return false;
    Linknode *s = Q.front;
    x = s->data;
    //队列只有一个结点
    if(Q.front == Q.rear){
        Q.front = Q.rear = NULL;
     }else{
         Q.front = Q.front->next;
     }
     free(s);
     return true;
}

2.5、双端队列

  1. 双端队列是允许从两端插入、删除的队列;
  2. 如果只使用其中一端的插入、删除操作,则等同于栈;
  3. 输入受限的双端队列:允许一段插入,两端删除的线性表;
  4. 输出受限的双端队列:允许两端插入,一端删除的线性表。
    考点:判断输出序列的合法化
    例题分析:数据元素输入序列为1,2,3,4,判断4!=24输出序列的合法化
    对于输入受限的双端队列:只有 4213 和 4231 不合法
    对于输出受限的双端队列:只有 4132 和 4231 不合法

三、栈与队列的应用

3.1、栈在括号匹配中的应用

用栈实现括号匹配:

  1. 最后遇到的左括号最先被匹配(栈的特性–LIFO)
  2. 遇到左括号就存一个左括号(入栈);
  3. 遇到右括号就消耗一个左括号(出栈)。

匹配失败的情况:

  1. 扫描到右括号且栈空,则该右括号单身;
  2. 扫描完所有括号后,栈非空,则该左括号单身;
  3. 左右括号不匹配。
#define MaxSize 10;

typedef struct{
    char data[MaxSize];
    int top;
}SqStack;

void initStack(SqStack &S);
bool EmptyStack(SqStack S);
bool PushStack(SqStack &S, char x);
bool PopStack(SqStack &S, char x);

//判断长度为length的字符串str中的括号是否匹配
bool bracketCheck(char str[], int length){
    SqStack S;
    initStack S;
    //遍历字符串str
    for(int i = 0;i<=length;i++){
        //扫描到左括号就入栈
        if(str[i] == '('||str[i] == '{'||str[i] == '['){
            pushStack(S, str[i]);
        }else{
            //扫描到右括号且栈空就直接返回
            if(EmptyStack(S))
                return false;
             char topElem;//用于接收栈顶元素
             PopStack(S,topElem);
             //括号不匹配
             if(str[i] == ')'&&topElem != '(')
                 return false;
             if(str[i] == '}'&&topElem != '{')
                 return false;
             if(str[i] == ']'&&topElem != '[')
                 return false;
        }
    }
    //扫描完成若栈空,则说明括号匹配
    return EmptyStack(S);
}

3.2、栈在表达求值中的应用

1. 中缀表达式: 中缀表达式是一种通用的算术或逻辑公式表示方法,运算符以中缀形式处于操作数的中间。对于计算机来说,中缀表达式是很复杂的,因此计算表达式的值时,通常需要将中缀表达式转换为前缀或者后缀表达式,然后再进行求值。
2. 前缀表达式(波兰表达式): 前缀表达式的运算符位于两个操作数之前;
3. 后缀表达式(逆波兰表达式): 后缀表达式的运算符位于两个操作数之后。

中缀表达式转后缀表达式-手算

步骤一: 确定中缀表达式中各个运算符的运算顺序;
步骤二: 选择下一个运算符,按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数;
步骤三: 如果还有运算符未被处理,继续步骤二。

遵循“左优先”原则;只要左边的运算符能先计算,就优先计算左边的。(保证运算顺序唯一)
示例:

中缀:A + B -C * D / E + F
后缀:A B + C D * E / - F + 

中缀表达式转后缀表达式-机算
初始化一个栈,用于保存暂时还不能确定运算顺序的运算符,从左到右处理各个元素,直至末尾,可能会遇到三种情况:

  1. 遇到操作数:直接加入后缀表达式;
  2. 遇到界限符:如遇到左括号"(“则直接入栈,遇到右括号”)“则依次弹出栈内运算符并加入后缀表达式,直到弹出”(“为止,注意左括号”("不加入后缀表达式;
  3. 遇到运算符:依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式,若碰到")"或栈空则停止,之后再把当前运算符入栈。
#define MaxSize 40 
typedef struct{     
    char data[MaxSize];   
    int top;
}SqStack;
 
typedef struct{  
    char data[MaxSize];  
    int front,rear;
}SqQueue;
 
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);
void InitQueue(SqQueue &Q);
bool EnQueue(LQueue &Q, char x);
bool DeQueue(LQueue &Q, char &x);
bool QueueEmpty(SqQueue Q);
 
// 判断元素ch是否入栈
int JudgeEnStack(SqStack &S, char ch){
    char tp = S.data[S->top];   
    // 如果ch是a~z则返回-1    
    if(ch >= 'a' && ch <= 'z')   
        return -1;    
    // 如果ch是+、-、*、/且栈顶元素优先级大于等于ch则返回0  
    else if(ch == '+' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))   
        return 0;     
    else if(ch == '-' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))   
        return 0;  
    else if(ch == '*' && (tp == '*' || tp == '/'))  
        return 0;    
    else if(ch == '/' && (tp == '*' || tp == '/'))     
        return 0;    
    // 如果ch是右括号则返回2   
    else if(ch == ')')      
        return 2;     
    // 其他情况ch入栈,返回1   
    else return 1;
}
 
// 中缀表达式转后缀表达式
int main(int argc, char const *argv[]) {  
    SqStack S;     
    SqQueue Q;	 
    InitStack(S); 
    InitQueue(Q);  
    char ch;	  
    printf("请输入表达式,以“#”结束:");  
    scanf("%c", &ch);   
    while (ch != '#'){  
        // 当栈为空时     
        if(StackEmpty(&S)){ 
            // 如果输入的是数即a~z,直接入队 
            if(ch >= 'a' && ch <= 'z')               
                EnQueue(Q, ch);      	
            // 如果输入的是运算符,直接入栈    
            else                      
                Puch(S, ch);       
        }else{                
            // 当栈非空时,判断ch是否需要入栈 
            int n = JudgeEnStack(S, ch);     
            // 当输入是数字时直接入队      	
            if(n == -1){        	    
                EnQueue(Q, ch);        
            }else if(n == 0){       
                // 当输入是运算符且运算符优先级不高于栈顶元素时    
                while (1){         
                    // 取栈顶元素入队    
                    char tp;        
                    Pop(S, tp);      
                    EnQueue(Q, tp);         
                    // 再次判断是否需要入栈     
                    n = JudgeEnStack(S, ch);
                    // 当栈头优先级低于输入运算符或者栈头为‘)’时,入栈并跳出循环  
                    if(n != 0){           
                        EnStack(S, ch);           
                        break;              
                    }                   
                }            
            }else if(n == 2){  
                // 当出现‘)’时 将()中间的运算符全部出栈入队   
                while(1){                
                    char tp;                
                    Pop(S, tp);             
                    if(tp == '(')          
                        break;        
                    else            
                        EnQueue(Q, tp);    
                }             
            }else{        
                // 当运算符优先级高于栈顶元素或出现‘(’时直接入栈     
                Push(S, ch);         
            }          
        }         
        scanf("%c", &ch);   
    }     
    // 将最后栈中剩余的运算符出栈入队 
    while (!StackEmpty(S)){	  
        char tp;            
        Pop(S, tp);      
        EnQueue(Q, tp);  
    }      
    // 输出队中元素 
    while (!QueueEmpety(Q)){    
        printf("%c ", DeQueue(Q));  
    }    
    return 0;
}

后缀表达式的计算–手算:
从左到右扫描,每遇到一个运算符,就让运算符前面最近的两个操作数执行相应运算,合体为一个新的操作数,再往后继续扫描。

后缀表达式的计算–机算:
用栈来实现后缀表达式的计算,栈内存放当前暂时不能确定运算次序的操作数

  1. 从左往右扫描元素,直到处理完所有元素;
  2. 若扫描到操作数,则压入栈,并回到步骤1;否则执行步骤3;
  3. 若扫描到运算符,则弹出两个栈顶元素,执行相应的运算,运算结果压回栈顶,回到步骤1。

实现中缀表达式的计算:

  1. 初始化两个栈,操作数栈和运算符栈;
  2. 若扫描到操作数,则压入操作数栈;
  3. 扫描到运算符,则按照“中缀转后缀”中相同的逻辑压入运算符栈(期间也会弹出运算符,每当弹出一个运算符时,就需要再弹出两个操作数栈的栈顶元素并执行相应运算,运算结果再压回操作数栈) 。

3.3、栈在递归中的应用

函数调用的特点:最后被调用的函数最先执行结束(LIFO)

函数调用时,需要用一个栈存储:

  1. 调用返回地址
  2. 实参
  3. 局部变量

递归调用时,函数调用栈称为“递归工作栈”:

  1. 每进入一层递归,就将递归调用所需信息压入栈顶;
  2. 每退出一层递归,就从栈顶弹出相应信息。
    缺点:太多层递归可能会导致栈溢出;适合用递归算法解决:可以把原始问题转换为属性相同,但规模较小的问题。

3.4、队列的应用

  1. 队列应用:树的层次遍历
  2. 队列应用:图的广度优先遍历
  3. 队列应用:操作系统中多个进程争抢使用有限资源时,先来先服务算法(First Come First Service)是一种常用的策略。

相关推荐

  1. c#队列

    2024-07-11 02:44:05       49 阅读
  2. Python队列

    2024-07-11 02:44:05       37 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-11 02:44:05       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-11 02:44:05       101 阅读
  3. 在Django里面运行非项目文件

    2024-07-11 02:44:05       82 阅读
  4. Python语言-面向对象

    2024-07-11 02:44:05       91 阅读

热门阅读

  1. 详解Go语言中的Goroutine组(Group)在项目中的使用

    2024-07-11 02:44:05       19 阅读
  2. numpy学习

    2024-07-11 02:44:05       22 阅读
  3. arm64架构下源码编译安装kafka —— 筑梦之路

    2024-07-11 02:44:05       27 阅读
  4. 在Ubuntu 14.04上安装和配置VNC的方法

    2024-07-11 02:44:05       31 阅读