数据结构-栈

栈是一种基本的数据结构

基本概念

栈(Stack)：具有一定操作约束的线性表。

只在一端(栈顶，Top)做插入、删除操作
插入数据：入栈(Push)
删除数据：出栈(Pop)
后入先出：Last In First Out(LIFO)

抽象数据类型描述

类型名称：栈
数据对象集：一个有0个或多个元素的有穷线性表
操作集：长度为MaxSize的堆栈属于Stack，堆栈元素X属于ElementType

• Stack CreateStack(int MaxSize)：生成空栈，其最大长度为MaxSize
• bool IsFull(Stack S)：判断栈S是否已满
• void Push(Stack S, ElementType X)：将元素X压入栈
• bool IsEmpty(Stack S)：判断栈S是否为空
• ElementType Pop(Stack S)：删除并返回栈顶元素

顺序存储实现

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

结构体定义

typedef int Position;
struct SNode{
    ElementType *Data;		//存储元素的数组
    Position Top;		//栈顶位置
    int MaxSize;		//最大容量
};
typedef struct SNode *Stack;

初始化栈

Stack CreateStack(int MaxSize){			//初始化最大容量为MaxSize的空栈
    Stack S=(Stack)malloc(sizeof(struct SNode));
    S->Data=(ElementType *)malloc(MaxSize*sizeof(ElementType));			//分配内存
    S->Top=-1;			//空栈栈顶位置为-1
    S->MaxSize=MaxSize;
    return S;
}

是否满栈

判断栈是否满了，可以根据栈顶位置与最大容量的关系。

bool IsFull(Stack S){
	return (S->Top==S->MaxSize-1);
}

入栈

void Push(Stack S, ElementType X){
	if(IsFull(S))		//先判断栈是否已满
		printf("栈已满");
	else{
		S->Data[++(S->Top)]=X;		//先把栈顶位置加1，再入栈
		return true;
	}
}

是否空栈

判断栈是否是空栈，可以根据栈顶位置是否为-1来判断。

bool IsEmpty(Stack S){
	return (S->Top==-1);
}

出栈

ElementType Pop(Stack S){
	if(IsEmpty(S)){				//先判断栈是否已空
		printf("栈已空");
		return ERROR;		//define ERROR -1
	}
	else
		return S->Data[(S->Top)--];			//先出栈，再栈顶位置减1
}

链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在链栈的栈顶进行，因为确定单链表的表尾比较耗费时间，我们一般把栈顶指针Top放在表头，也就是在链栈的头部进行插入和删除操作。因为是链式结构，也就不存在栈满这种情况。

结构体定义

typedef struct SNode *PtrToSNode;
struct SNode{
	ElementType Data;
	PtrToSNode Next;
};
typedef PtrToSNode Stack;

初始化栈

在初始化的时候，一般先定义一个头结点Head，这个头结点不存放数据，只是作为链表的起始。

Stack CreateStack(){
	Stack S;
	S=(Stack)malloc(sizeof(struct SNode));		//内存分配
	S->Next=NULL;
	return S;
}

是否空栈

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

入栈

void Push(Stack S, ElementType X){
	PtrToSNode tmp;
	tmp=(PtrToSNode)malloc(sizeof(struct SNode));
	tmp->Data=X;
	tmp->Next=S->Next;
	S->Next=tmp;
}

出栈

ElementType Pop(Stack S){
	PtrToSNode FirstCell;
	ElementType TopElem;
	if(IsEmpty(S)){
		printf("栈已空\n");
		return ERROR;		//define ERROR -1
	}
	else{
		FirstCell=S->Next;
		TopElem=FirstCell->Data;
		S->Next=FirstCell->Next;
		free(FirstCell);
		return TopElem;
	}
}