栈的定义:其实就是线性表.只不过这个线性表遵循"后进先出"的原则.也就是我们插入和删除操作都动最后一个结点.同时我们在线性表中的插入和删除操作给换个一个马甲,它们额马甲号分别叫做push(压栈,进栈)和pop(出栈,弹栈).线性表弄懂了这个就很简单了.

当然了,栈也有顺序存储结构和链式结构.看下栈的顺序存储结构.

数据结构:

typedef struct{
    char Data[MAXSIZE];//用来存储数据
    int Top;//记录栈顶的下标
}SqStack;//栈顺序存储结构数据结构

1.初始化操作:

BOOL InitializeStack(SqStack *ST)
{
    ST->Top=-1;//初始化指定栈顶下标为-1,代表栈为空

    return true;
}

2.销毁操作:

BOOL DestroyStack(SqStack *ST)
{
    if(-1!=ST->Top)//如果栈不为空栈,销毁这个栈
    {
        free(ST);
        return true;
    }

    return false;//如果栈为空站或者不可用,返回false
}

3.清空栈操作:

BOOL ClearStack(SqStack *ST)
{
    int temp;

    if(-1==ST->Top)//if the stack is empty,return false
        return false;

    for(temp=0;temp<=ST->Top;temp++)//free the space of the current node
    {
        ST->Data[temp]=0;
    }
    ST->Top=-1;//make the top value point to -1

    return true;
}

4.是否为空栈:

BOOL isStackEmpty(SqStack ST)
{
    if(-1==ST.Top)//if the top point to -1, the stack is empty,so return true
        return true;

    return false;//if the top is not point to 01,the stack store data, return false
}

5.取得栈顶元素操作:

BOOL GetTopValue(SqStack ST, char *TopValue)
{
    if(true==isStackEmpty(ST))// if the stack is empty,return false
        return false;

    *TopValue=ST.Data[ST.Top];//get the top stack node value

    return true;
}

6.进栈操作:

BOOL PushStack(SqStack *ST,char NewTopValue)
{
    if(MAXSIZE-1==ST->Top)//if the stack if full,return false
        return false;

    ST->Top++;//the top pointer move to the next node
    ST->Data[ST->Top]=NewTopValue;//push the stack

    return true;
}

7.出栈操作:

BOOL PopStatck(SqStack *ST,char *PopValue)
{
    if(true==isStackEmpty(*ST))//if the stack is empty,return false
        return false;

    *PopValue=ST->Data[ST->Top];//output the delete value
    ST->Data[ST->Top]=0;//pop the stack
    ST->Top--;//the top pointer move to the prior node

    return true;
}

8.返回栈的数据个数:

int StackLength(SqStack ST)
{
    return ST.Top+1;
}

老规矩,写个小程序跑一下,以下是代码:

#define MAXSIZE 26
#define true 1
#define false 0
#define error -1
#define BOOL int

#include <stdlib.h>
#include <stdio.h>

int main(void)
{
    SqStack SS;
    char Input='a',DeleteNode;
    int temp;

    if(false==InitializeStack(&SS))
    {
        printf("初始化栈失败,程序退出!\n");
        return -1;
    }
    printf("初始化栈成功!栈内数据有:%d个\n",StackLength(SS));

    printf("即将插入字符a-z,请稍后:\n");
    for(temp=0;temp<MAXSIZE;temp++)
    {
        if(false==PushStack(&SS,Input))
        {
            printf("插入字符%c失败!程序退出!\n",Input);
            return -1;
        }
        printf("插入字符%c成功!\n",Input);
        Input++;
    }
    printf("插入字符a-z成功!新的栈内数据有%d个!\n",StackLength(SS));

    if(false==PopStatck(&SS,&DeleteNode))
    {
        printf("出栈操作失败!程序退出!\n");
        return -1;
    }
    printf("出栈操作成功!出栈字符为:%c,新的栈数据长度为:%d\n",DeleteNode,StackLength(SS));

    return 0;
}

运行截图:

Capture.PNG

但是顺序存储有个坏处,准确说叫不足.就是要是数据没存满不是浪费了空间嘛,而另外一个相同元素性质的链表要是空间不够又不方便增长,能不能解决呢?答案就是共享栈空间.也就是在一个栈空间里面存放两个相同数据类型的栈.实现方法很简单,一个从下标0开始往MAXSIZE方向增长,而另一个栈则从下表MAXSIZE向0增长,这样两个栈不就共享了空间了嘛.这个可以用来那些此消彼长栈空间,比如从咱们每个月的生活费,假设一个月1000个大洋,这1000个大洋就是咱们共享栈的空间数,我们假设我们现在还有的大洋数为栈1,本月花费大洋数为栈2,当我们花了100个大洋,那么栈1的长度不是就减去100,而栈2则增加100了不是

数据结构:

typedef struct{
     char Data[MAXSIZE];
     int Top1;
     int Top2;
 }SqShareStock;

1.初始化操作:

BOOL InitializeShareStock(SqShareStock *SS)
 {
     SS->Top1=-1;//the first stock's top value point to -1
     SS->Top2=MAXSIZE;//the another stock's top value point to MAXSIZE
     //because the lenght of the Stock==-1+maxsize,so we assign these value to the Top1 and Top2
     return true;
 }

2.销毁操作:

BOOL DestoryStack(SqShareStock *SS,int WhichStack)
 {
     if(1==WhichStack)//if we want to destroy Stack one 
     {
         if(-1!=SS->Top1)//destroy
         {
             SS->Top1=-1;
         }
         else//stack one is empty,return false
             return false;
     }
     else//if we want to destroy stack two
     {
         if(MAXSIZE!=SS->Top2)//destroy
         {
             SS->Top2=MAXSIZE;
         }
         else
             return false;//stack two is empty,return false
     }

     return true;
 }

3.是否为空栈:

BOOL isStackeEmpty(SqShareStock SS,int WhichStack)//true indicate the stack is not empty, false is empty
{
    switch(WhichStack)
    {
    case 1:
        if(-1!=SS.Top1)
            return true;
        break;
    case 2:
        if(MAXSIZE!=SS.Top2)
            return true;
        break;
    default:
        return false;
    }

    return false;
}

4.取得栈顶元素操作:

BOOL GetStackTop(SqShareStock SS,int WhichStack,char *TopData)
{
    switch(WhichStack)
    {
    case 1:
        if(false==isStackeEmpty(SS,1))
            break;
        *TopData=SS.Data[SS.Top1];
        return true;
    case 2:
        if(false==isStackeEmpty(SS,2))
            break;
        *TopData=SS.Data[SS.Top2];
        return true;
    default:
        break;
    }

    return false;
}

5.进栈操作:

BOOL PushStack(SqShareStock *SS,int WhichStack,char NewTopData)
{
    switch(WhichStack)
    {
    case 1:
        if(SS->Top1+1==SS->Top2)//the stack have no any empty space
            break;

        SS->Top1++;
        SS->Data[SS->Top1]=NewTopData;//push
        return true;

    case 2:
        if(SS->Top1==SS->Top2)//the stack have no any empty space
            break;

        SS->Top2--;
        SS->Data[SS->Top2]=NewTopData;//push
        return true;

    default:
        break;
    }

    return false;
}

6.出栈操作:

BOOL PopStack(SqShareStock *SS,int WhichStack,char *PopData)
{
    switch(WhichStack)
    {
    case 1:
        if(false==isStackeEmpty(*SS,1))//if the stack is empty,return false
            break;

        *PopData=SS->Data[SS->Top1];//pop
        SS->Top1--;
        return true;

    case 2:
        if(false==isStackeEmpty(*SS,2))//if the stack is empty,return false
            break;

        *PopData=SS->Data[SS->Top2];//pop
        SS->Top2++;
        return true;

    default:
        break;
    }

    return true;
}

7.返回栈的数据个数:

int StackLength(SqShareStock SS,int WhichStack)
{
    switch(WhichStack)
    {
    case 1:
        return SS.Top1+1;
    case 2:
        return MAXSIZE-SS.Top2;
    default:
        break;
    }
    return error;
}

还是写个小程序跑一下,以下是代码:

#define MAXSIZE 52
#define true 1
#define false 0
#define error -1
#define BOOL int

#include <stdlib.h>
#include <stdio.h>

int main(void)
{
    SqShareStock SS;
    int temp;
    char Input1='a',Input2='z',Output;

    printf("初始化共享栈...!\n");
    if(false==InitializeShareStock(&SS))
    {
        printf("初始化共享栈失败,程序退出!\n");
        return -1;
    }
    printf("初始化共享栈成功!\n当前栈1的数据长度为%d,栈2的数据长度为%d",StackLength(SS,1),StackLength(SS,2));

    for(temp=0;temp<MAXSIZE/2;temp++)
    {
        if(false==PushStack(&SS,1,Input1))
            printf("Push栈1失败,Push值为%c:\n",Input1);
        printf("Push栈1成功,Push值为%c:\n",Input1);

        if(false==PushStack(&SS,1,Input2))
            printf("Push栈1失败,Push值为%c:\n",Input2);
        printf("Push栈1成功,Push值为%c:\n",Input2);

        Input1++;
        Input2++;
    }
    printf("栈1和栈2成功Push,新的栈1的长度为%d,栈2的长度为%d\n",StackLength(SS,1),StackLength(SS,2));

    printf("执行栈1和栈2的pop操作...\n");
    if(false==PopStack(&SS,1,&Output))
        printf("栈1pop操作失败!\n");
    printf("栈1pop操作成功!pop的数据为:%c\n",Output);
    if(false==PopStack(&SS,2,&Output))
        printf("栈2pop操作失败!\n");
    printf("栈2pop操作成功!pop的数据为:%c\n",Output);

    return 0;
}

运行截图:

share.PNG