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(&s，e)        栈S己存在，在S顶部插入新栈元X

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

9）遍历栈 StackTraverse(s，visit())  依次对栈调用visit()

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

#define  STACK_INIT_SIZE   100

#define  STACKINCREMENT  10

typedef   struct {                                          

    SElemType   *base;

    SElemType   *top ;

} sqstack;

说明

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

top= base 空栈

top=base+stacksize  栈满  补添存储

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

顺序栈 

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

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

typedef  struct{

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

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

}SqStack;

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

约定：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

• 数据结构知识点总结（一）2018-09-10 21:33
• 图的几个经典问题2018-09-03 23:09
• 数据结构相关基本概念2018-09-03 22:30
• 数据结构知识点总结（六）2018-09-10 21:21