栈的顺序存储结构及及其实现

   由于栈是线性结构的一种,所以,栈也可以通过顺序存储结构实现。

网站建设哪家好,找成都创新互联!专注于网页设计、网站建设、微信开发、成都微信小程序、集团企业网站建设等服务项目。为回馈新老客户创新互联还提供了铜川免费建站欢迎大家使用!

   因为,线性表的顺序存储结构是通过数组实现的,所以,栈的顺序存储结构也通过数组实现。不可避免的,要设置栈的最大存储空间。因为,栈只允许在栈顶进行元素的插入与删除操作,所以需要一个指向栈顶的变量top。那么栈的存储结构:

typedef int SElemType;

typedef struct{

    SElemType data[MAXSIZE];
    int top;
}SqStack;

接着,就是插入一个新的元素e,也就是进栈操作push。向栈顶插入一个元素,首先要判断栈的存储空间是否充足,如果以已经没有存储空间了,则入栈失败。代码如下:

Status Push ( SqStack *S, SElemType e )
{
    if ( S->top == MAXSIZE - 1 )
        return ERROR;
    
    S->top++;
    S->data[S->top] = e;

}

如果要删除一个操作,首先要判断栈是否为空,如果不为空,则删除有效,若为空,则删除失败。接着,只要top--就行了。代码如下:

Status Pop ( SqStack *S, SElemType *e )
{
    if ( S->top == -1 )
    return ERROR;
    
    *e = S->data[S->top];
    S->top--;

    return OK;
}

   因为没有涉及到循环,所以,时间复杂度均为O(1)。


文章名称:栈的顺序存储结构及及其实现
本文来源:http://myzitong.com/article/jpjsos.html