栈的顺序存储实现

栈的顺序存储实现

通常由一个一维数组和一个记录栈顶元素位置的变量组成。

(1)顺序栈结构体的定义

当 Top = -1时,表示栈空;当Top = MaxSize -1 时,栈满!

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

(2)顺序栈的创建

Stack CreateStack(int MaxSize) /*顺序栈的创建*/ 
{
	Stack S = (Stack)malloc(sizeof(struct SNode));
	S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
	S->Top = -1;		       /*"-1"表示空栈  "MaxSize-1"表示满栈*/ 
	S->MaxSize = MaxSize;      /*指定栈的最大容量*/ 
	return S;
}

(3)判满

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

(4)判空

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

(5)入栈

在执行堆栈 Push 操作时,先判断栈是否满;

  • 若不满,Top 加1,并将新元素放入 Data数组的Top位置上
  • 若满,则返回错误标志
bool Push(Stack S, ElementType X)	/*顺序栈的 入栈 操作*/ 
{ 
	if(IsFull(S)) 
	{
		printf("堆栈满!");
		return false;
	}
	else
	{
		S->Data[++(S->Top)] = X;	/*若是栈不满,则Top加 1,并将新元素放入Data数组的Top位置中*/ 
		return true;
	}
}

(6)出栈

执行Pop操作时,首先判别栈是否为空;

  • 若不为空,返回Data[Top],同时将Top-1;
  • 否则要返回错误标志
ElementType Pop(Stack S) /*顺序栈 的 出栈 操作*/ 
{
	if(IsEmpty(S))		
	{
		printf("堆栈空!");
		return ERROR;					/*ERROR 是 ElementType 类型的特殊值,标志错误。必须是正常栈元素数据不可能取到的值 */ 
	}
	else
		return(S->Data[(S->Top)--]);	/*若不空,返回Data[Top],同时将Top减 1*/  
}
版权声明:本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
文章名称:《栈的顺序存储实现》
文章链接:https://zhuji.vsping.com/4492.html
本站资源仅供个人学习交流,请于下载后24小时内删除,不允许用于商业用途,否则法律问题自行承担。