数据结构初体验——笔记整理#2 栈

栈（stack）是一种先进后出的存储结构，只能在其一端进行操作 插入数据：入栈（push） 删除数据：出栈（pop）

栈的数组存储实现

typedef int Position struct SNode//定义栈体 { ElementType *Data;//数组类型 栈中数据 Position Top;//栈顶指针，指向栈顶元素的索引 int MaxSize;//最大容量 }; typedef struct SNode *Stack; Stack CreateStack(int 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); } bool isEmpty(Stack s)//判断栈是否已满 { return (s->Top == -1); } bool push(Stack s,ElementType x)//压栈 { if(isFull(s)) { return false; } else { s->Data[++(s->Top)] = x; return true; } } ElementType pop(Stack s)//出栈 { if(isEmpty) { return ERROE;//ERROR设置为ElementType的特殊值，用以标识错误 } else { return s->Data[(s->Top)--]; } }

栈的链表存储实现

typedef struct SNode *PtrToSNode;//定义栈节点指针 struct SNode//定义栈节点 { ElementType Data;//栈节点存储数据 PtrToSNode Next;//指向下个数据节点 }; typedef PtrToSNode Stack;//定义栈头指针 Stack createStack()//创建头节点 { Stack s = (Stack)malloc(sizeof(struct SNode)); s->Next = NULL; return s; } bool isEmpty(Stack s) { return (s->Next == NULL); } //bool isFull(Stack s)//以链表为存储方式的栈没有存储上限 bool push(Stack s,ElementType x) { PtrToSNode = temp; temp = (PrtToSNode)malloc(sizeof(struct SNode)); temp->Data = x; temp->Next = s->Next;//注意头节点不存储数据 s->Next = temp; return true; } ElementType pop(Stack s) { PtrToSNode temp; ElementType data; if(isEmpty(s)) { return ERROR; } else { temp = s->Next; data = temp->Data; s->Next = temp->Next; free(temp);//释放空间时数据会丢失，因此要先取出来 return data; } }