数据结构——堆栈

后入先出

顺序存储实现

Top指向带有数据的栈顶

代码：

#include <stdio.h>

typedef int Position;
typedef struct SNode * PtrToSNode;
struct SNode{
	ElementType * Data;
	Position Top;// 指向栈顶，有元素
	int MaxSize;
};
typedef PtrToSNode Stack;

// 创建空栈
Stack CreateStack(int MaxSize){
	Stack S=(Stack)malloc(sizeof(struct SNode));
	S->Data = (ElementType *)malloc(MaxSize*sizeof(ElementType));
	S->Top=-1;
	S->MaxSize=MaxSize;

	return S;
}

// 是否满了
bool IsFull(Stack S){
	return (S->Top == MaxSize-1);
}

// 入栈
bool Push(Stack S, ElementType X){
	if(IsFull(S)){
		printf("已经满了");
		return false;
	}

	else{
		S->Data[++(S->Top)] = X;
		return true;
	}
}

// 是否为空栈
bool IsEmpty(Stack S){
	return (S->Top==-1);
}

// 出栈
ElementType Pop(Stack S){
	if(IsEmpty){
		printf("堆栈空");
		return ERROR;
	}
	else
		return (S->Data[(S->Top)--]);
}

int main(){

	return 0;
}

堆栈链式实现

在链表头进行入栈和出栈

#include <stdio.h>

typedef struct SNode * PtrToSNode;

struct Node{
	ElementType Data;
	PtrToSNode Next;
};

typedef PtrToSNode Stack;

Stack CreateStack(){
	Stack S;

	S=malloc(sizeof(struct SNode));
	S->Next=NULL;

	return S;
}

bool IsEmpty(Stack S){
	return S->Next==NULL;
}

bool Push(Stack S, ElementType X){
	Stack tmp;

	tmp = (Stack)malloc(sizeof(struct SNode));
	tmp->Data = X;
	tmp->Next = S->Next;
	S->Next = tmp;

	return true;
}

ElementType Pop(Stack S){
	Stack tmp;
	ElementType X;

	if(IsEmpty(S)){
		printf("堆栈空");
		return ERROR;
	}
	else{
		tmp = S->Next;
		X=tmp->Data;
		S->Next = tmp->Next;
		free(tmp);
		return X;
	}
}

int main(){

	return 0;
}

堆栈实现中缀表达式变后缀

1. 遇到运算符直接输出；
2. 遇到左括号入栈；
3. 遇到右括号将栈顶的运算符输出直至栈顶为左括号；
4. 遇到运算符，如果此运算符大于栈顶运算符，则入栈；如果此运算符优先级小于或等于栈顶运算符，则出栈，再与栈顶相比，直至遇到大的。

赏

谢谢你请我吃糖果

支付宝

微信

• 本文作者： Doted Wood
• 本文链接： http://example.com/2022/01/12/数据结构/数据结构堆栈/
• 版权声明： 版权归博主所有，转载请说明来源