首页 > 代码库 > 数据结构学习(三)、栈

数据结构学习(三)、栈

2024-08-14 10:39:38   230人阅读

栈是一种特殊的线性表。大家可能会有疑问，竟然栈是一种线性表，那为什么还要定义栈呢？因为栈的引入简化了程序设计的问题，

使我们思考范围更小，只需关注top位置。线性表分为顺序存储和链式存储，栈是线性表，所以也有这两种存储方式。同样，

栈作为一种特殊的线性表，也同样存在这两种存储方式。我们先来看栈的顺序存储结构。

顺序栈结构体如下：

#define MAXSIZE /*存储空间初始分配量*/typedef int ElemType;/*存放的数据类型*/typedef struct{   ElemType data[MAXSIZE];   int top;  } SqStack;

现在有一个栈，MAXSIZE为5，则栈普通情况，空栈，满栈的情况如下图所示

技术分享

顺序栈初始化操作

顺序栈初始化操作实际就是将top指向-1操作

Status InitStack(SqStack *S){    S->top = -1;    return OK;}

顺序栈入栈操作

技术分享

入栈操作实际就是将top增加一，讲新元素赋值给栈顶空间

 

Status Push(SqStack *S,ElemType e){    if(S->top == MAXSIZE-1)        return ERROR;    S->top++;    S->data[S->top] = e;    return OK;}

 

顺序栈出栈操作

技术分享

出栈的操作实际就是将栈顶元素辅助给e,栈顶指针减一

Status Pop(SqStack *S,ElemType *e){    if(S->top == NULL)        return ERROR;    *e = S->data[S->top];    S->top--;    return OK;}

顺序栈（两栈共享空间）

思路：两栈别人处于数组二端，向中间靠拢。可以想象，只要他们指针不相遇，二个栈就能一直使用。

 

技术分享

 

其结构体如下：

 

#define MAXSIZE 10typedef struct{    ElemType data[MAXSIZE];    int top1;    int top2;}DuStack;

 

 

 

两栈初始化操作

两栈初始化操作实际就是将top1指向-1，top2指向MAXSIZE操作

 

Status InitStack(DuStack *S){    S->top1 =-1;    S->top2 =MAXSIZE;    return OK;}

 

两栈入栈操作

对于双栈的入栈操作，我们除了要插入元素值外，还需要判断是栈1还是栈2的栈号参数。

/**    入栈操作    @params S 共享空间指针变量    @params e 入栈数据    @params stackNumber 栈号 1为一号栈 2为二号栈*/Status Push(DuStack *S,ElemType e,int stackNumber){    if(S->top1+1 == S->top2)        return ERROR;    if(stackNumber == 1)    {        S->top1++;        S->data[S->top1] = e;    }else if(stackNumber==2){        S->top2--;        S->data[S->top2] = e;    }    return OK;}

两栈出栈操作

对于双栈的入栈操作，我们除了要一个接收出栈的值，同样还需要判断是栈1还是栈2的栈号参数。

 

/**    出栈操作    @params S 共享空间指针变量    @params e 出栈数据存放指针变量    @params stackNumber 栈号 1为一号栈 2为二号栈*/Status Pop(DuStack *S,ElemType *e,int stackNumber){    if(stackNumber == 1){        if(S->top1 == NULL)            return ERROR;        *e = S->data[S->top1];        S->top1--;    }    if(stackNumber == 2){        if(S->top2 == MAXSIZE)            return ERROR;        *e = S->data[S->top2];        S->top2++;    }    return OK;}

 

双栈应用

适合二个栈空间需求有相反关系时。

 

链栈

链栈结构体如下：

 

typedef struct Node{    ElemType data;    struct Node * next;}Node,*LinkStackPtr;typedef struct LinkStack{    int count;    LinkStackPtr top;}LinkStack;

 

链栈初始化

初始化操作实际就是将top指针指空，链表计数为零。

 

/*    初始化共享空间栈,无头结点    @params LinkStack S 栈指针变量*/Status InitStack(LinkStack * S){/*    S->top = (LinkStackPtr *)malloc(sizeof(Node));    if(!S->top)        return ERROR;*/    S->count = 0;    S->top=NULL;    return OK;}

 

链栈进栈操作

进栈操作先分配一个结点，并为结点赋值，把当前栈顶元素赋值给新结点的直接后继，将新的结点赋值给栈顶指针,链表计数加一。

/*    入栈操作    @params LinkStack S  栈指针变量    @params ElemType e  入栈值*/Status Push(LinkStack * S,ElemType e){    LinkStackPtr r;    r = (LinkStackPtr)malloc(sizeof(Node));    if(!r)        return ERROR;    r->data =http://www.mamicode.com/e;    r->next = S->top;    S->top = r;    S->count ++;    return OK;}

链栈出栈操作

出栈操作需先判断是否为空栈，若否，则将栈顶结点值赋给e,将栈顶结点赋值给p,使栈顶指针指向后一个结点，释放p,链表计数减一。

/*    出栈操作    @params LinkStack S  栈指针变量    @params ElemType *e  出栈保存地址*/Status Pop(LinkStack * S,ElemType *e){    LinkStackPtr p;    if(S->top==NULL)        return ERROR;    p  = S->top;    *e = p->data;    S->top = p->next;    S->count --;    free(p);    return OK;}

 

数据结构学习(三)、栈


联系
我们