1.堆栈的介绍
表达式求值
因为不同的符号优先级不同,所以计算起来相对困难一些
后缀表达式
这里后缀表达式就用到了堆栈。它先从左向右进行扫描,碰到运算数就记住,碰到运算符就将离着这个运算符最近的两个运算数进行运算…
堆栈是一种储存方法,能够按照所给的顺序记住运算数,当需要运算的时候,把排在最后的两个数进行运算,倒序输出。先放进去的后拿出来,后放进去的先拿出来——后入先出
时间复杂度是线性的O(N)
生活中,一堆放在一起的碗就是堆栈,在栈顶top拿碗,最后放的碗先拿出来使用。top是随着栈中的元素进行变化的。
堆栈的相关操作
其中最重要的就是插入(入栈)和删除(出栈)操作。插入的时候要判断有没有满;出栈的时候要看是不是空。
图解
其中push和pop可以交替进行,由此出栈的顺序也会大有不同
注意并不是ABC所有的序列都可实现。
栈的顺序储存
#define MaxSize 最大个数
typedef struct SNode* Stack;
struct SNode{
int Top;
ElementType Data[MaxSize];
};
通常使用一个数组和指示Top来实现堆栈的顺序储存。其中Top是指一个整型变量,作为栈顶元素的下标[ ],记录栈顶的实时位置。
*
- 当栈空的时候,Top = -1,表示没有元素。Top
一直表示栈顶的下标,当有元素入栈,Top值要+1。
入栈
入栈操作需要先进行判断栈是否已满
void Push(Stack PtrS, int item)
{
if ( PtrS == NULL || PtrS->Top == MaxSize - 1)
{
printf("%s","栈已经满了,无法入栈");
}
else
{
PtrS->Data[++(PtrS->Top)] = item;//使用前自增运算符,简洁
}
}
出栈
返回下标为Top的元素的值,Top值-1。因为实现遍历数组等操作的时候,通常以Top为标准界限,Top-1就相当于删除了原来在栈顶的那个元素。出栈前要先检查堆栈空不空。
ElementType Pop(Stack PtrS)
{
if (PtrS->Top == -1)
{
printf("栈已经空了,无法再删除");
}
else
{
return PtrS->Data[(PtrS->Top)--];
}
}
一个数组实现两个堆栈
使用一个数组实现两个堆栈,要求最大可能的利用空间,只要数组还有空间就允许入栈操作:
最优解是两个栈从两头开始向中间入栈,两个栈共用空间,只要中间有空间就可以入栈。当两个栈的指针相遇的时候表示数组空间已经满了。
#define MaxSize 自定义最大数
struct DStack{
int Top1;
int Top2;
ElementType Data[MaxSize];
}S;
当Top1 = -1;Top2 = MaxSize
的时候表示两个栈都是空的
插入
将变量item放到某一个堆栈中去
void Push(struck DStack* PtrS,int item,int Tag)//如果Tag=1,放到第一个堆栈...
{//理解1:计算:(MaxSize - Top2) + (Top1 + 1) > MaxSize 时,堆栈就满了
//理解2:当两个Top挨在一起的时候堆栈就满了
if( (PtrS->Top1 + 1) > (PtrS->Top2) )
{
printf("堆栈已经满了,无法入栈");
}
else
{
if(Tag == 1)//插入哪个堆栈判断
PtrS->Data[++(PtrS->Top1)] = item;
else
PtrS->Data[--(PtrS->Top2)] = item;
}
}
删除
同样的首先要进行判断哪个堆栈,接下来判断对应的堆栈空不空。
ElementType Pop(int Tag,struct DStack PtrS)
{
if(Tag == 1)
{
if(PtrS->Top1 == -1)
printf("第一个堆栈是空的,无法Pop);
else
return PtrS->Data[(PtrS->Top1)--];//往左边挪
}
else
{
if(PtrS->Top2 == -1)
printf("第二个堆栈是空的,无法Pop);
else
return PtrS->Data[(PtrS->Top2)++];//往右边挪
}
}
栈的链式储存(链栈)
因为单链表只能从前向后进行检索,不能后退,所以应该将链表的头作为Top。
初始化
typedef struct SNode* Stack;
struct SNode{
ElementType Data;
Stack Next;
};
- 可以加一个栈头指针,它不代表任何一个元素,Data部分是空的,它的Next部分充当指示作用,使用这个节点可以找到链表中的具体某个元素,便于插入和删除。
Stack CreateStack()//建立一个空的堆栈,只是有个头
{
Stack S = malloc(sizeof(struct SNode));
S->Next = NULL;
return S;
}
插入
void Push(ElementType item,Stack S)
{//无需判断满不满,只要申请空间即可
Stack TmpCell = malloc(sizeof(struct SNode));
TmpCell->Data = item;
if(S->Next)//是得需要判断S之后有没有节点
TemCell->Next = S->Next;
S->Next = TmpCell;
}
图解:
关于链表指针的新思考:
这里的S是作为一个堆栈头结点,没有Data部分。其实可以把结构指针变量当做名字,它包括两部分:Data部分和Next部分。比如头指针(结构指针)S,可以认为S->Data
和 S->Next
属于性质不太一样的访问,一个是访问自己本身的储存,另一个是访问指向的下一个节点。S->Data
其实就是 结点1
,S->Next->Data = 节点1->Data
.
删除
删除并返回堆栈S的栈顶元素Data部分的值
ElementType Pop(Stack S)
{
if(!S->Next)//没有节点存在(判断空不空)
printf("堆栈为空,无法出栈");
Stack One = S->Next;//注意删除的节点一定要释放它的空间,所以要把他赋值给一个指针变量One
ElementType Copy = One->Data;
if(!One->Next)//只有一个节点存在
{
S->Next = NULL;
free(One);
}
else//至少存在两个节点
{
S->Next = One->Next;
free(One);
}
return Copy;
}
堆栈应用
表达式求值
根据后缀表达式求值更好地理解堆栈
堆栈的其他应用
-
函数的调用及递归实现
顺序储存,倒序返回 -
深度优先搜索
-
回溯算法
比如走迷宫,这一步进行到下一步有好多条路,当选择的路走不通的时候,需要返回上一步再进行试探。