栈的顺序存储及运算

栈的顺序存储及运算

1．栈的顺序存储

　　栈的顺序存储可用向量来实现，即利用一组地址连续的存储单元依次存放栈中的各个数据元素，又可称为顺序栈。最先 入栈的数据元素为栈底，最后入栈的数据元素为栈顶。一般将向量的低下标位置作为栈底，并保持不变，栈顶位置随着元素的进栈和出栈操作而变化。为了方便操 作，通常设一个标记top标出栈顶元素所在的位置。使用C语言，我们可将顺序栈的数据类型描述如下：

结构3-1 顺序栈

#define Maxsize 100     //假设栈空间最多为100个元素

typedef char Datatype;  //假设栈元素的数据类型为字符

typedef struct

{ Datatype data[Stacksize];

    int top;

  }Seqstack;

　　该类型包含两部分内容：一是存放栈中数据元素的data数组，另一个是标记栈顶位置的top。在C语言的描述 中，我们可约定data数组中的data[0]单元不用，并用top=0表示栈空，这也是初始化栈的状态。在实际应用时，需声明一个属于上述类型的栈变 量，即可对此变量进行栈的有关操作。

　　现假设有一个栈类型，其最大存储空间Maxsize为6，s为指向该类型的栈指针，按照约定，栈中可存放的数据 元素最多为5个，可存放在s->data[1]至s->data[5]中。初始状态下s->top=0，表示栈空，如图3-2（a）所 示。当栈不满时，可进行进栈操作，当栈不空时，可进行出栈操作。若有数据元素（A，B，C，D，E）依次进栈，则s->top每次加1，并将元素存 入s->top所标记的位置，栈的状态如图3-2（b）、3-2（c）所示。若有数据元素出栈，则删除s->top标记位置的数据元 素，s->top每次减1，如图3-2（d）所示。

（a）空栈            （b）A进栈           （c）栈满         （d）E、D出栈

图3-2 顺序栈的状态及进栈、出栈操作

　　可见栈空和栈满是进行栈操作的两个限制条件：

　　栈空条件：s->top = 0，此时不能进行出栈操作

　　栈满条件：s->top = Maxsize -1，此时不能进行进栈操作

2．栈的基本运算的实现

　　算法3-1 初始化

　　栈的初始化即创建一个空栈。可通过指针变量获取该空栈。算法描述如下： 

void init_seqstack(Seqstack *s)

 { s->top = 0;

 }

　　算法3-2 判栈空

　　对一个已创建的栈判断其是否为空。若为空，则返回1，否则，返回0，函数的返回值为整型，参数为指向已知栈的指针。算法描述如下：

int empty_seqstack (Seqstack *s)

 { if(s->top == 0)

     return 1;

   else 

return 0;

 }

　　算法3-3 判栈满

　　　对一个已创建的栈判断其是否为满。若为满，则返回1，否则，返回0，函数的返回值为整型，参数为指向已知栈的指针。算法描述如下：

int full_seqstack (Seqstack *s)

 { if(s->top == Maxsize-1)

     return 1;

   else 

return 0;

 }

　　算法3-4 进栈

　　将一个新的数据元素插入到栈中作为新的栈顶元素。注意插入前首先要判断栈是否已满，若栈满，则不能插入，函数返回0值，表示插入不成功；若不满，移动栈顶标记，插入新的数据元素，函数返回1，表示插入成功。算法描述如下：

int push_seqstack(Seqstack *s, Datatype x)

 { if(full_seqstack(s))            //判栈是否为满

   { printf(″Overflow＼n″);

     return 0;}

  else

   { s->top++;

     (s->data)［s->top］ = x;

     return 1;}

}

　　算法3-5 出栈

　　在已知栈中删除栈顶元素并将栈顶元素作为返回值。注意在删除操作之前首先要判断栈是否为为空，若为空，则不能删除；若不为空，则返回栈顶元素，移动栈顶标记。算法描述如下：

Datatype pop_seqstack(Seqstack *s,Datatype *x)

 { if(empty_seqstack(s))         //判栈是否为空

     { printf(″Underflow＼n″);     return 0;}

    else

     { &x = (s->data)［s->top］;

s->top--;}

    return  x;

   }

　　算法3-6 取栈顶元素

　　在已知栈中取出栈顶元素并将栈顶元素作为返回值。注意在取出操作之前首先要判断栈是否为为空，若为空，则无元素可取；若不为空，则返回栈顶元素。算法描述如下：

Datatype gettop_seqstack(Seqstack *s)

 { Datatype  x;

   if(empty_seqstack(s))        //判栈是否为空

     {printf(″Stack is empty.＼n″);

      x = NULL;}

   else

      x = (s->data)［s->top］;

   return x;

}

　　算法3-7 置空

　　将栈的栈顶标记置为初始状态，成为空栈。算法描述如下： 

void clear_seqstack(Seqstack *s)

 { s->top = 0;

 }