当前位置:首页 » 数据结构精品文章 » 正文

栈的相关定义

1699 人参与  2018年09月03日 22:34  分类 : 数据结构精品文章  评论

1、栈的定义和相关基本概念?

限定运算在线性表尾进行的线性表

允许插入、删除的返一端称为栈顶另一个固定端称为栈底。当表中没有元素时称为空栈定义仅是在线性表上规定了操作点,操作受限的、线性的后进先出线性表LIFO

2、对于栈,常做的基本运算有哪些?

1)栈初始化InitStack(s)  S不存在,构造一个空栈

2)销毁栈 DstoryStack(&s)  S存在,将S销毁

3)清为空栈 ClearStack(&s) S存在,将S清空

4)判栈空 StackEmpty(s)    S己存在,若S为空栈返回TRUE,否则返回FALSE

5)清空栈 Stacklength(s)   S存在,返回S的元素个数

6)读栈顶元素 GeTStack(s&e)  S存在且非窄,返回栈顶元素e

7)入栈 Push(&se)        S己存在,在S顶部插入新栈元X

8)出栈 Pop(&s&e)        S存在且非空,删除栈S顶元,用e返回其值

9)遍历栈 StackTraverse(svisit())  依次对栈调用visit()

3、栈的顺序存储结构的定义。

#define  STACK_INIT_SIZE   100

#define  STACKINCREMENT  10

typedef   struct {                                          

    SElemType   *base;

    SElemType   *top ;

} sqstack;

image.png 

说明

top指向栈顶元素的下一个位置,即待接收数据的位置

top= base 空栈

top=base+stacksize  栈满  补添存储

由于栈是运算受限的线性表,因此线性表的存储体结构对栈也是适用的,只是操作点不同而己。顺序栈的置空首先建立栈空间,然后初始化栈顶指针。

顺序栈 

约定与类型定义:top的含义

#define  STACK_INIT_SIZE  100// 存储空间的初始分配量

typedef  struct{

ElemType base[100];  // 栈底指针  

int top; // 栈顶指针(栈顶元素的下一个位置)

}SqStack;

4、栈的顺序存储结构及其基本操作的实现。

image.png 

约定:top指向栈顶元素的下一个位置

顺序栈的初始化 首先建立栈空间,然后初始化栈顶指针。

status InitStack(SqStack &s )  {

  s.base=(SElemtype*)malloc(STACK_INIT_SIZE*

                               sizeof(SElemtype));

  if  (!s.base) exit (OVERFLOW)

  s.top=s.base ;

  s.stacksize=STACK-INIT-SIZE ;

  return  Ok;

   } // InitStack

顺序栈的取栈顶元

status GetTop(SqStack s,SElemType &e )  {

   if  (s.top==s.base) return  ERROR;

   e=*(S.top-1);

   return  Ok;

} // GetTop

出栈和取栈顶元,先判栈是否为空,为空时不能操作,否则产生错误。通常栈空作为一种控制转移的条件

顺序栈入栈 

status Push (SqStack &s, SElemType e)  {

    if (s.top-s.base >= s.stacksize) {

    s.base=(SElemType*)realloc(s.base,(s.stacksize

                         +STACKINCREMENT)*sizeof(SElemType));

    if (!s.base) exit (OVERFLOW)

    s.top=s.base+ s.stacksize;

    s.stacksize+= STACKINCREMENT ;

  }

  *s.top++=e ;

  return OK;

} //Push}

对于顺序栈,入栈时先判栈是否满了,栈满时不能入栈; 否则出现空间溢出,引起错误,这种现象称为上溢。

顺序栈出栈

status Pop (SqStack &s, SElemType e)  {

    if (s.top==s.base) return ERROR ;

    e=*--s.top ;

    return OK ;

 } //Pop

顺序栈判空

status StackEmpty(SqStack s )  {

   if (s.top= =s.base)  return  1;

   else  return  0;

}

5、栈与单链表的关系?

单链表仅在一端操作。用链式存储结构实现的栈称为链栈。通常链栈用单链表表示,其结点结构与单链表的结构相同

typedef   struct  Node {

    datatype         data ;

    struct  Node   *next ;

} StackNode, *LinkStack ;

因为栈中的主要运算是在栈顶插入、删除,显然在链表的头部做栈顶是最方便的,而且没有必要象单链表那样为了运算方便附加一个头结点。

 


来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=196

数据结构  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!