栈-大话数据结构版

1.栈的顺序存储及实现

我们定义一个top变量来指示栈顶元素在数组中的位置。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1。

1.栈的结构定义：

#define MAXSIZE 100
typedef struct
{
    int data[MAXSIZE];
    int top;    //标注栈顶元素在数组中的位置
}SqStack;

2.进栈插入元素e为新的栈顶元素

void Push(SqStack *s, int e)
{
    if (s->top == MAXSIZE - 1)    //栈满
        return;
    s->top++;    //栈顶指针加1
    s->data[s->top] = e;    //将新元素赋值给栈顶空间
}

3.出栈若栈不为空则删除s的栈顶元素用e返回

void Pop(SqStack *s, int *e)
{
    if (s->top == -1) //栈空
        return;
    *e = s->data[s->top];    //将要删除的栈顶元素赋给e
    s->top--;    //栈顶指针减1
}

2.两栈共享空间

　　两个相同类型的栈，为它们各自开辟了数组空间。数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端即下标为0处，另一个栈为栈的末端即下标为数组长度n-1处。这样两个栈如果增加元素，就是两端点向中间延伸。

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

从图中得知：栈1为空时即是top1等于-1。而当top2为n时即栈2为空。

极端情况下，若栈2是空栈，栈1的top等于n-1时即是栈1满了。把栈2的内存空间填满

　　　　　　若栈1是空栈，栈2的top等于0时即是栈2满了。把栈1的内存空间填满

　　　　　　两个栈见面时也就是两个指针之间相差1时，即top1 + 1 == top2为栈满。

入栈出栈

//对于共享空间的Push方法，除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的
//栈号参数stackNumber。
//插入元素e为新的栈顶元素
void Push(SqDoubleStack *s, int e, int stackNumber)
{
    if (s->top1 + 1 == s->top2)    //栈满 
        return;

    if (stackNumber == 1) //栈1有元素进栈
        s->data[++s->top1] = e; //先top+1后给数组元素赋值

    else if (stackNumber == 2) //栈2有元素进栈
        s->data[--s->top2] = e; //先将top2-1后给数组元素赋值
}

//两栈共享空间的Pop方法 参数就只是判断栈1栈2参数stackNumber
void Pop(SqDoubleStack *s, int *e, int stackNumber)
{
    if (stackNumber == 1)
    {
        if (s->top1 == -1) //栈1空栈 溢出
            return;
        *e = s->data[s->top1--]; //将栈1的栈顶元素出栈
    }
    if (stackNumber == 2)
    {
        if (s->top2 == MAXSIZE)    //栈2空栈 溢出
            return;
        *e = s->data[s->top2++]; //将栈2的栈顶元素出栈
    }
}

3.栈的链式存储

　　栈的链式存储结构简称链栈。

对于链栈来说，基本不存在栈满的情况，除非内存已经没有了可使用的空间。

对于空栈来说，链表原定义是头指针指向空，那么链栈的空就是top==NULL的时候。

链栈的插入删除

typedef struct StackNode
{
    int data;
    struct StackNode *next;
}StackNode;
typedef struct LinkStack
{
    StackNode *top;
    int count; //栈元素计数器
}LinkStack;
//插入元素e为新的栈顶元素
void Push(LinkStack *s, int e)
{
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    p->data = e;
    p->next = s->top; //将当前的栈顶元素赋给新结点的直接后继

    s->top = p; //将新的结点p赋给栈顶指针
    s->count++;
}
//若栈不空，则删除s的栈顶用e返回
void Pop(LinkStack *s, int *e)
{
    StackNode *p;
    if (s->top == NULL)
        return;
    *e = s->top->data;

    p = s->top; //将栈顶点指针赋给p
    s->top = s->top->next; //使栈顶点指针下移一位

    free(p);
    s->count--;
}