线性结构--堆栈常用操作

水深无声 2022-02-02 11:49 231阅读 0赞

##### **一、后缀表达式求法** #####

例：`562/+34*-`  
中缀表达式：`5+6/2-3*4=-4`  
进行运算的时候先拿出来数的放运算符右边，后拿出来的放运算符左边

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]

--------------------

##### 二、栈的顺序存储实现 #####

###### 1、定义声明 ######

typedef struct SNode *Stack;
    struct SNode{ 
    	ElemenType Data[MAXSIZE];
    	int Top;
    };

--------------------

###### 2.顺序栈的创建 ######

Stack CreateStack()
    { 
    	Stack S=(Stack)malloc(sizeof(struct SNode));
    	S->Data=(ElemenType *)malloc(MAXSIZE*sizeof(ElemenType));
    	S->Top=-1;
    	return S;
    }

--------------------

###### 3、入栈 ######

void Push(Stack PtrS,ElemenType item)
    { 
    	if(PtrS->Top==MAXSIZE-1)
    	printf("堆栈满");
    	else
    	{ 
    		PtrS->Data[++(PtrS->Top)]=item;//堆栈为空时pop为-1 
    		return ;
    	 } 
    }

--------------------

###### 4、出栈 ######

ElemenType Pop(Stack PtrS)
    { 
    	if(PtrS->Top==-1)
    	printf("堆栈空");
    	else
    	return PtrS->Data[PtrS->Top--]; 
     }

--------------------

##### 三、栈的顺序存储实现（一个数组实现两个堆栈） #####

###### 1、定义声明和初始化Top1，Top2 ######

typedef struct SNode *Stack;
    
    struct SNode{ 
    	ElemenType Data[MAXSIZE];
    	int Top1;
    	int Top2;
    };
    
    Stack.Top1=-1;
    Stack.Top2=MAXSIZE;

--------------------

###### 2、入栈 ######

bool Push(Stack S,ElemetType X,int Tag)//Tag控制对第几个堆栈操作 
    { 
    	if(S->Top2-S->Top1==1 )
    	{ 
    		printf("堆栈满");
    		return false; 
    	}
    	else
    	{ 
    		if(Tag==1)
    		{ 
    			S->Data[++S->Top1=X];
    		}
    		else
    		{ 
    			S->Data[--S->Top2=X];
    		}
    		return true;
    	}
    }

--------------------

###### 3、出栈 ######

ElemenType Pop(Stack S,int Tag)
    { 
    	if(Tag==1)
    	{ 
    		if(S->Top1==-1)
    			printf("堆栈空"); 
    		else
    			return S->Data[(S->Top1)--];
    	}
    	else
    	{ 
    		if(S->Top2==MAXSIZE)
    		printf("堆栈空");
    		else
    		return S->Data[(S->Top2)++]; 
    	}
    }

--------------------

##### 四、栈的链式存储实现 #####

使用链表实现时，插入和删除操作只能在**链表的头部**进行，栈顶指针Top就是链表的头指针。如果在链表的尾部进行，插入时没有问题，可以连接一个新结点。如果删除，删除后不知道前一个结点是谁，再进行插入时就不知道向哪插入。

--------------------

###### 1、声明定义： ######

typedef struct SNode *Stack;
    struct SNode{ 
    	ElemenType Data;
    	Stack Next;
    };

--------------------

###### 2、创建一个堆栈的头结点 ######

![在这里插入图片描述][20190511192713521.PNG]

Stack CreatStack()
    { 
    	Stack S;
    	S=(Stack)malloc(sizeof(struct SNode));
    	S->Next=NULL;
    	return S;
    }

--------------------

###### 3、判断堆栈是否为空 ######

bool IsEmpty(Stack S)
    { 
    	if(S->Next==NULL)//插入的时候总是向头结点后插入 
    	return false;
    	else
    	return true;
    }

--------------------

###### 4、入栈 ######

bool Push(Stack S,ElemenType X)//插入的时候总是向头结点后插入 
    { 
    	Stack tmp;
    	tmp=(Stack)malloc(sizeof(struct SNode));
    	tmp->Data=X;
    	tmp->Next=NULL;
    	
    	tmp->Next=S->Next;
    	S->Next=tmp;
    	
    	return true;
     }

--------------------

###### 5、出栈 ######

ElemenType Pop(Stack S)
    { 
    	Stack tmp;
    	ElemenType back;
    	if(IsEmpty(S))
    	{ 
    		printf("stack empty");
    		return ; 
    	}
    	else
    	{ 
    		back=S->Next->Data;
    		tmp=S->Next;
    		S->Next=tmp->Next;
    		free(tmp);
    	}
    	return back;
    }

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MzIyMzU3_size_16_color_FFFFFF_t_70]: /images/20220202/90f38973f4834381bbe4568774f67d8b.png
[20190511192713521.PNG]: /images/20220202/5339201835e5478886e83c2ae0243654.png