聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

顺序栈:栈的顺序存储结构

2013-01-05 09:00 浏览: 3164723 次 我要评论(0 条) 字号:


既然栈是线性表的特例,那么栈的顺序存储其实也是线性表顺序存储的简化,我们将其简称为顺序栈

  • 线性表是用数组来实现的,对于栈这种只能一头插入删除的线性表来说,用数组哪一端来作为栈顶和栈底比较好?
  • 下标为0的一端作为栈底比较好,因为首元素都存在栈底,变化最小,所以让它作栈底。

我们定义一个top变量来指示栈顶元素在数组中的位置,这top就如同中学物理学过的游标卡尺的游标,如上图所示,它可以来回移动,意味着栈顶的top可以变大变小,但无论如何游标不能超出尺的长度。同理,若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判定条件定为top等于-1。

下面看看栈的结构体定义:


#include "stdio.h"

/* 存储空间初始分配量 */
#define MAXSIZE 20

/* SElemType类型根据实际情况而定,这里假设为int */
typedef int SElemType;

/* 顺序栈结构 */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用于栈顶指针 */
}SqStack;

int main()
{
}

若现在有一个栈,StackSize是5,则栈普通情况、空栈和栈满的情况示意图可以从下图清楚看出。



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复