数据结构

（笔记）数据结构2.2-堆栈

陈越 何钦铭

Posted by 王晗 on November 7, 2017

2.2堆栈

计算机如何进行表达式求值？

【例】算术表达式5+6/2-3*4

  • 由两类对象构成：
  • 运算数 如2、3、4

  • 运算符号 如+、-、*、/

  • 不同运算符号优先级不一样

后缀表达式

  • 中缀表达式：运算符号位于两个运算数之间。如 a+b*c-d/e
  • 后缀表达式：运算符号位于两个运算时之后。如 abc*+de/-
  • 前缀表达式：运算符号位于连个运算数之前。如 -+a*bc/de

【例】6 2/3-4 2*+=? 后缀表达式求值策略：从做向右扫描，逐个处理运算数和运算符号

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

启示：需要有种存储方法，能顺序存储运算数，并在需要时“倒序”输出。

堆栈的抽象数据类型描述

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

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

堆栈的抽象数据类型描述

类型名称：堆栈（Stack） 数据对象集：一个有0个或多个元素的有穷线性表 操作集：长度为MaxSize的堆栈$S\in Stack,堆栈元素item\in 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)堆栈输出是 CBA
  2. Push（S,A）,Push（S,B）,Push（S,C）, Pop(S),Pop(S),Pop(S)堆栈输出是 CBA

栈的顺序存储实现

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

#define MaxSize<储存数据元素的最大个数>
typedef struct SNode *Stack;
struct SNode{
	ElementType Data[MaxSize];
    int Top;
    
}
  • 入栈
void Push(Stack PtrS,ElementType item){
	if(PtrS->Top==MaxSize-1){
    	printf("栈堆满");return;
    }else{
    	PtrS->Data[++(PtrS->Top)]=item;  //(PtrS->Top)++; PtrS->Data[++PtrS->Top]=item;
        return;
    }
}
  • 出栈
ElementType Pop(Stack PtrS){
	if(PtrS->Top==-1){
    	printf("栈堆空");
        return ERROR;    //ERROR是ElementType的特殊值，标志错误
    }else{
    	return(PtrS->Data[(PtrS->Top)--]);
    }
}

【例】请用一个数组实现两个堆栈，要求最大地利用数组空间，使数组只要有空间入栈操作就可以成功。 【分析】使两个栈分别从数组的两头开始向中间生长；当两个栈的栈顶指针相遇时，表示两个栈都满了。

#define MaxSize<储存数据元素的最大个数>
struct DStack{
	ElementType Data[MaxSize];
    int Top1;    //堆栈1的栈顶指针
    int Top2;    //堆栈2的栈顶指针
}S；
S.Top1=-1;
S.Top2=MaxSize;
  • 入栈
//Tag作为区分两个堆栈的标志，取值为1 2
void Push(struct DStack *PtrS,ElementType item,int Tag){
	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){
	if(Tag==1){
    	if(PtrS->Top1==-1){
        	printf("堆栈1空")； return NULL;
        }
        else return PtrS->Data[(PtrS->Top1)--];
    }else{
    	if(PtrS->Top2==MaxSize){
        	printf("堆栈2空")；  return NULL;
        }
        else return PtrS->Data[(PtrS->Top2)++];
    }
}

堆栈的链式存储实现

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

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;
}
  • 判断堆栈S是否为空
int IsEmpty(Stack S){
	return (S->Next==Null);
}
  • 入栈
void Push(Stack S,ElementType item){
	struct SNode *TmpCell;
    TmpCell=(struct SNode*)malloc(sizeof(struct SNode));
    TmpCell->Data=item;
    TmpCell->Next=S->Next;
    S->Next=TmpCell;
}
  • 出栈
ElementType Pop(Stack PtrS){
	struct SNode *FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)){
    	printf("堆栈空")； return NULL;
    }else{
    	FirstCell=S->Next;
        S->Next=FirstCell->Next;
        TopElem=FirstCell->Data;
        free(FisrtCell);
        return TopElem;
    }
}

堆栈应用：表达式求值

从左到右读入后缀表达式的各项（运算符或运算数）

中缀表达式求值

基本策略：将中缀表达式转换为后缀表达式，然后求值

【例】：2+9/3-5 -> 2 9 3/ + 5 -

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

【例】 a*(b+c)/d=?   a b c+ * d / 时间复杂度：T(N)=O(N)

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

从头到尾读取中缀表达式的每个对象，对不同对象按不同情况处理。

  1. 运算数：直接输出；
  2. 左括号：压入堆栈；
  3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（括号出栈不输出）；
  4. 运算符：
    • 若优先级大于栈顶运算符时，把它压栈；
    • 若优先级小于等于栈顶运算符，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈；
    • 若个对象处理完毕，则把栈中存留的运算符一并输出；

堆栈的其他应用

  • 函数调用及递归实现

  • 深度优先搜索

  • 回溯算法

  • …

FEATURED TAGS
数据结构
FRIENDS