顺序栈的实现和两栈共享空间

 以后慢慢启用个人博客：http://www.yuanrengu.com/

一.顺序栈的实现     

       栈(stack)是限定仅在表尾进行插入或删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

理解栈的定义需要注意：

1. 首先他是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过他是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
2. 他的特殊之处就在于限制了这个线性表的插入和删除位置，他始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。

      栈的插入操作，叫作进栈，也称压栈、入栈。栈的删除操作，叫出栈，也称弹栈。

     顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

顺序栈的定义：

typedef struct{
    ElemType *bottom;
    ElemType *top;
    int StackSize;
}SqStack;

其中，StackSize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始状态分配量进行第一次存储分配，bottom可称为栈底指针，在顺序栈中，他始终指向栈底的位置，如bottom的值为NULL，则表明栈结构不存在。称top为栈顶指针，其初值指向栈底，即top=bottom可作为栈空的标记，每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。如下图所示。

base = NULL;  //栈结构不存在
top = base;   //栈空

顺序栈的实现：

头文件stack.h

 stack.h

实现函数：stack.cpp

 stack.cpp

测试函数：

 test.cpp

二.两栈共享空间

      如果我们有两个相同类型的栈，我们为他们各自开辟了数组空间，极有可能第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。这时，我们完全可以用一个数组两存储两个栈。

      我们的做法如下图，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。

     其实关键思路是：他们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要他们两不见面，两个栈就可以一直使用。

     从这里也就可以分析出来，栈1为空时，就是top1等于-1时；而当top2等于n时，即是栈2为空时，那么什么时候栈满呢？

     想想极端的情况，若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。但更多的情况，其实就是刚才说的，两个栈见面之时，也就是两个指针之间相差1时，即top1+1==top2为栈满。

     两栈共享空间的结构的代码如下：

typedef struct
{
    ElemType data[MAXSIZE];
    int top1;  //栈1栈顶指针
    int top2;  //栈2栈顶指针
}SqDoubleStack;

      对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下：

 1 Status Push(SqDoubleStack *s , ElemType e , int stackNumber)
 2 {
 3     if(s->top1+1 == s->top2)       //栈已满，不能再push新元素了
 4         return ERROR;
 5     if(stackNumber == 1)           //栈1有元素进栈
 6         s->data[++s->top1] = e;    //若栈1则先top+1后给数组元素赋值
 7     else if(stackNumber == 2)      //栈2有元素进栈
 8         s->data[--s->top2] = e;    //若栈2则先top2-1后给数组元素赋值
 9     return OK;
10 
11 }

      因为在开始已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担心溢出问题的。

      对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber，代码如下：

 1 //若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
 2 Status Pop(SqDoubleStack *s , ElemType *e , int stackNumber)
 3 {
 4     if(stackNumber == 1)
 5     {
 6         if(s->top1 == 1)
 7             return ERROR;            //说明栈1已经是空栈，溢出
 8         *e = s->data[s->top1--];     //将栈1的栈顶元素出栈 
 9     }
10     else if(stackNumber == 2)
11     {
12         if(s->top2 == MAXSIZE)
13             return ERROR;            //说明栈2已经是空栈，溢出
14         *e = s->data[s->top2++];     //将栈2的栈顶元素出栈
15     }
16     return OK;
17 }

      事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。

      注意：这只是针对两个具有相同数据类型的栈。

本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3368379.html，如需转载请自行联系原作者