当前位置：首页 > 资讯 > 技术文档

浅析顺序结构存储的栈

时间：2021-04-10 16:36 编辑：来源：阅读：
扫一扫，手机访问

摘要：浅析顺序结构存储的栈

栈定义：仅限在表尾进行插入和删除的线性表栈的特点： 1）一般来说能在表尾进行进栈和出栈的数据 2）先进后出（last in first out ） 3）栈会有栈顶，栈底，通常栈底为高地址，栈顶为高地址，如下图所示 [img]http://files.jb51.net/file_images/article/201401/201419151956087.jpg[/img] 操作系统一般会在内存划出一块，专门用于栈操作，当然这个跟普通的操作有些区别：比如存放数组，地址是增加的；但是在存入数据到栈，地址则是不断减小的栈的存储结构：

[u]复制代码[/u] 代码如下:

typedef struct _SQSTACK
{
 SElemType* base;
 SElemType* top;
 int stacksize;
}
SqStack;

数据定义：

[u]复制代码[/u] 代码如下:

//默认的存储空间的大小和空间增长大小
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
//存储数据的类型定义
#ifndef INT_TYPE
#define INT_TYPE
#endif // INT_TYPE

#ifdef INT_TYPE
typedef  int  SElemType;
#elif defined FLOAT_TYPE
typedef  float SElemType;
#elif defined STRING_TYPE
typedef  char* SElemType;
#elif defined STRUCT_TYPE
typedef  void* SElemType;
#endif

栈的操作，会涉及到初始化栈，销毁栈，进栈（入栈），出栈，还有判断栈空，栈大小，以及清空栈，如下：栈的初始化：

[u]复制代码[/u] 代码如下:

//初始化栈
int InitStack(SqStack *S)
{
 S->base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
 if (!S->base)
 {
  return -1;
 }
 S->top = S->base;
 S->stacksize = STACK_INIT_SIZE;
 return 0;
}

栈才初始化，里面还没有数据，这时候top，base都指向分配空间的基地址，表示栈空销毁栈：

[u]复制代码[/u] 代码如下:

//销毁栈
int DestroyStack(SqStack *S)
{
 if (S->base)
 {
  free(S->base);
  S->base = NULL;
  S->top = NULL;
  S->stacksize = 0;
 }
 return 0;
}

如果栈存在，就销毁地址空间，将栈尺寸置0 进栈：

[u]复制代码[/u] 代码如下:

int Push(SqStack *S, const SElemType data)
{
 assert(S->base != NULL);
 if (S->top - S->base >= STACK_INIT_SIZE)
 {
  S->base = (SElemType*)realloc(S->base,
   (STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SElemType));
  if (!S->base)
  {
   return -1;
  }
  S->top = S->base + S->stacksize;
  S->stacksize += STACK_INCREMENT;
 }
 *S->top++ = data;
 return 0;
}

如果栈存在，就销毁地址空间，将栈尺寸置0 进栈：

[u]复制代码[/u] 代码如下:

int Push(SqStack *S, const SElemType data)
{
 assert(S->base != NULL);
 if (S->top - S->base >= STACK_INIT_SIZE)
 {
  S->base = (SElemType*)realloc(S->base,
   (STACK_INIT_SIZE + STACK_INCREMENT) * sizeof(SElemType));
  if (!S->base)
  {
   return -1;
  }
  S->top = S->base + S->stacksize;
  S->stacksize += STACK_INCREMENT;
 }
 *S->top++ = data;
 return 0;
}

如果栈的大小大于已分配长度，重新分配空间，并使栈顶重新指向新的位置，之后就将数据存入当前栈顶指向的位置，然后栈顶+1 出栈：

[u]复制代码[/u] 代码如下:

//出栈
int Pop(SqStack *S, SElemType *data)
{
 assert(S->base != NULL);
 if (S->base == S->top)
 {
  return -1;
 }
 *data = *(--S->top);

 return 0;
}

首先将栈顶位置-1，然后取得当前位置的值以下为辅助函数，如下：

[u]复制代码[/u] 代码如下:

//栈是否为空
int IsStackEmpty(const SqStack &S)
{
 return ((S.base == S.top) ? true:false);
}

[u]复制代码[/u] 代码如下:

//得到栈的长度
int GetStackLength(const SqStack &S)
{
 assert(S.base != NULL);
 return S.stacksize;
}

[u]复制代码[/u] 代码如下:

//清空栈
int ClearStack(SqStack *S)
{
 assert(S->base != NULL);
 if (S->base != S->top)
 {
  S->top = S->base;
 }
 S->stacksize = 0;
 return 0;
}

全部评论(0)

上一篇：C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法
下一篇：深入遍历二叉树的各种操作详解（非递归遍历）

资讯排行榜
更多>>