数据结构与算法之堆栈

it2023-09-25 78

数据结构与算法之堆栈

文章目录

数据结构与算法之堆栈一、堆栈是什么二、堆栈的操作1、Stack CreateStack( int MaxSize )：生成空堆栈，其最大长度为MaxSize；2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；3、void Push( Stack S, ElementType item )：将元素item压入堆栈；4、int IsEmpty ( Stack S )：判断堆栈S是否为空；5、ElementType Pop( Stack S )：删除并返回栈顶元素；总结

目前正自学数据结构，于此记录学习历程，方便复习。同时为后来者提供帮助。

一、堆栈是什么

堆栈是线性表存储结构的一种，是人们自主的在链表或数组的基础上增加一些限制而形成的。我们可以将它类比为盘子，盘子在堆叠时是一个一个往上面摞。堆栈亦是如此，当你想要在堆栈中存储元素（俗称“入栈”），你只能将其放在前一个元素的后面。而取盘子也只能从最上面一个一个向下取。同理，在堆栈中如果你想删除一个元素（俗称“出栈”），只能从最后面的元素一个一个向前取。如下图所示：入栈：B比A后入，则必须插在A之后出栈，B在A之后，B先出。因此，堆栈的出入栈操作也叫做后进后出

二、堆栈的操作

1、Stack CreateStack( int MaxSize )：生成空堆栈，其最大长度为MaxSize；

代码如下：

struct SNode { ElementType Data; PtrToSNode Next; }; typedef PtrToSNode Stack; Stack CreateStack( ) { /* 构建一个堆栈的头结点，返回该结点指针 */ Stack S; S = (Stack)malloc(sizeof(struct SNode)); S->Next = NULL; return S; }`

2、int IsFull( Stack S, int MaxSize )：判断堆栈S是否已满；

代码如下：

int IsFull( Stack S ) { if(S->Top == S->MaxSize-1) return 1; else return 0; }

3、void Push( Stack S, ElementType item )：将元素item压入堆栈；

代码如下：

void Push( Stack S, ElementType X ) { /* 将元素X压入堆栈S */ PtrToSNode TmpCell; TmpCell = (PtrToSNode)malloc(sizeof(struct SNode)); TmpCell->Data = X; TmpCell->Next = S->Next; S->Next = TmpCell; }

4、int IsEmpty ( Stack S )：判断堆栈S是否为空；

代码如下：

int IsEmpty ( Stack S ) { /* 判断堆栈S是否为空，若是返回true；否则返回false */ if ( S->Next == NULL ){ return 1; }; else return 0; }

5、ElementType Pop( Stack S )：删除并返回栈顶元素；

代码如下：

ElementType Pop( Stack S ) { /* 删除并返回堆栈S的栈顶元素 */ PtrToSNode FirstCell; ElementType TopElem; if( IsEmpty(S) ) { printf("堆栈空"); return ERROR; } else { FirstCell = S->Next; TopElem = FirstCell->Data; S->Next = FirstCell->Next; free(FirstCell); return TopElem; } }

总结

以上就是堆栈的基础操作，如果觉得有帮助，请点赞支持，谢谢！！！（注：部分内容参考自中国大学mooc)

最新回复(0)

数据结构与算法之堆栈