数据结构之栈和队列（C语言版）

    数据结构学习继续向前推进，之前对线性表进行了学习，现在我们进入栈和队列的学习。同样我们先学习一些基本概念以及堆栈的ADT.

创新互联公司专注于岚山网站建设服务及定制，我们拥有丰富的企业做网站经验。 热诚为您提供岚山营销型网站建设，岚山网站制作、岚山网页设计、岚山网站官网定制、重庆小程序开发公司服务，打造岚山网络公司原创品牌,更为您提供岚山网站排名全网营销落地服务。

栈和队列是两种中重要的线性结构。从数据结构角度看，栈和队列也是线性表，只不过是受限的线性表。因此可以称为限定性数据结构。但从数据类型来看，他们是和线性表大不相同的两类重要的抽象数据类型。

栈：（stack）是限定仅在表尾进行相应插入和删除操作的线性表。因此，对栈来说，表尾有其特殊含义，称为栈顶，表头称为栈底，不含元素的空表称为空栈。栈一个重要特性就是后进先出.OK,我们来看一下栈的结构：

ADT Stack

{

数据对象：D = {ai| ai属于ElemSet，i = 1，2，……，n， n >= 0 }

约定an端为栈顶，a1端为栈底。

基本操作：

                Status Init_SeqStack(SeqStack *s)

                    初始化栈，构造一个空栈。

                Status Destory(SeqStack *s)

                    摧毁栈

                Status Clear(SeqStack *s)

                    清空栈                 

                int IsEmpty(SeqStack *s)

                判断是否为空栈，是空栈返回1，不是空栈返回0

               int IsFull(SeqStack *s )

                判断栈是否满，栈满返回1，没有满返回0

                int  GetLength(SeqStack s)

                返回栈中元素的个数

                Status PushStack(SeqStack *s,ElemType x)

                插入元素e为新的栈顶元素

                Status GetTop(SeqStack *s,ElemType *value)

                获取栈顶元素，用value带回

                Status  PopStack(SeqStack *s)

                删除栈顶元素              

                Status Show_Stack(SeqStack s)

                打印输出栈中元素

}

    以上就是栈的抽象数据类型，好了我们接下来用C语言实现栈结构，既然栈受限的线性表，线性表有链式存储结构和顺序存储结构，那么栈也同样有两种，顺序栈和链栈。依然沿袭过去先弄清结构再通过代码解释。开篇已经讲了栈是受限的线性表，那么我们就要类比着看栈的操作：顺序栈，就类比顺序表。链栈就类比单链表。ok，我们先来看顺序栈：

顺序栈

    顺序栈，即就是栈的顺序存储结构，是利用一组连续的存储单元一次依次存放自栈底到栈顶的数据元素，同时附设top指示栈顶元素在顺序表中的位置，通常的习惯做法以top=0表示空栈，鉴于以C语言作为描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需的最大空间大小无法估计。因此一般来说，先为初始化空栈时不应设定栈的最大空间容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够时再逐段扩大。为此，可以设定两个常 STACK_INIT_SIZE(存储空间初始分配量)和STACK_INC_SIZE(存储空间分配增量)

 ok我们先定义顺序栈的结构：

#define ElemType char

#define Status    int 

#define FALSE     0

#define TRUE      1

#define STACK_INIT_SIZE  8               存储空间初始分配量

#define STACK_INC_SIZE   20              存储空间分配增量

typedef struct  SeqStack

{

ElemType *bace;

int capacity;

int top;

}SeqStack;

//判断是否为空栈，栈结构中的top也就记录了顺序栈中的状态，栈空返回1，非空返回0

int  IsEmpty(SeqStack *s)

{

return s->top == 0;

}

//判断是否栈满，栈满返回1，非满返回0

int  IsFull(SeqStack *s )

{

return s->top >= s->capacity; 

}

//此函数解决，上面提到的，当基空间不够时，增加空间。增加成功放回TRUE,也就是1，增加失败返回FALSE

Status IncSize(SeqStack *s)

{

ElemType *newbase = (ElemType *)realloc(s->bace,sizeof(ElemType) * (s->capacity + STACK_INC_SIZE));

if(NULL == newbase)

{

printf("out of memory\n");

return FALSE;

}

s->bace = newbase;

s->capacity += STACK_INC_SIZE;

return TRUE;

}

顺序栈的初始化

//初始化栈，就是为栈分配一个基空间，修改结构中top让其等于0，表示空栈。

//初始化成功返回TRUE，初始化失败返回FALSE;

Status Init_SeqStack(SeqStack *s)

{

s->bace = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);

if(NULL == s->bace )

{

printf("out of memory,filed Init_SeqStack\n");

return FALSE;

}

s->top = 0;

s->capacity = STACK_INIT_SIZE;

return TRUE;

}

   顺序栈的压栈出栈

    这里一直强调栈是受限的线性表，那么，初始化，等其他的基本类同，主要区别就是在栈中的压栈和出栈，压栈出栈，对顺序栈就是对顺序表的尾插、尾删，ok我们继续用图理一下结构。

//入栈（压栈）成功返回TRUE,失败返回FALSE

Status PushStack(SeqStack *s,ElemType x)

{

 /*

    这里就是解决栈的基空间不够会满的情况，需要调用前边定义的函数再次为其增加空间。这里的 

    if条件需要注意，IsFull(s) 函数，当栈已满是返回1结果为真，IncSize(s)函数返回值，当开辟

    成功后返回1结果为真，所以当开辟成功后取反就为价所以&&操作后为假，if模块就不执

    行了，就继续执行后边的代码模块

*/

if(IsFull(s) && !IncSize(s))            

{

printf("栈空间已满,%d不能入栈\n",x);

return FALSE;

}

s->bace[s->top++] = x;

//s->top++;                         简化代码

return TRUE;

}

//出栈

Status  PopStack(SeqStack *s)

{

if(IsEmpty(s))

{

printf("栈已空,不能出栈\n");

return FALSE;

}

s->top--;

return TRUE;

}

    顺序栈的获取栈顶元素

    继续看上一张图，中的那段话，在C语言中，由于数组下标是从0开始的，top中保存栈中元素个数，所以base[top]是指向栈顶元素的上一个空间，所以获取栈顶元素时就需要减去1.

//获取栈顶元素，

Status GetTop(SeqStack *s,ElemType *value)

{

if(IsEmpty(s))

{

printf("栈空间已空,不能取栈顶元素\n");

return FALSE;

}

*value = s->bace[s->top - 1];

return TRUE;

}

   顺序栈的的长度

     top中保存的就是栈中的元素个数，所以获取栈中元素个数直接返回top的值就可以。

//获取栈长度

int  GetLength(SeqStack s)

{

return s.top;

}

顺序栈的清空栈

//清空栈，清空栈就是让栈为空，所以只需要把top修改为0即可。

Status Clear(SeqStack *s)

{

s->top = 0;

return TRUE;

}

顺序栈的摧毁栈

//摧毁栈，摧毁栈，意味着，不仅要top修改为0，更要释放掉栈的空间。

Status Destory(SeqStack *s)

{

        free(s->bace);

s->bace = NULL;

s->top = 0;

return TRUE;

}

顺序栈的输出

//输出栈中的元素，既然栈是从栈顶出，那么全部打印的输出的时候，就需要从数组的尾输出。

Status Show_Stack(SeqStack s)

{

if(s.top == 0)

{

printf("栈已空\n");

return FALSE;

}

for(int i = s.top-1; i >= 0; i--)

{

printf("%d",s.bace[i]);

}

printf("\n");

return TRUE;

}

顺序栈的操作的基本操作就总结到这里，我们接着看栈的另一种存储结构——链栈。

栈之链栈

    链栈也是栈,所以就不在介绍它的ADT，我们直接看链栈的结构。顺序栈我们类比顺序表，那么链栈我们类比链表，链表的种类那么多，我们选用那种呢？看栈的定义，我们不难得出是单链表，至于是带头结点还是不带头结点，由于栈操作是从栈顶操作也就是线性表的表尾，所以这里也不用考虑带头结点或者不带头结点，都一样，也就不需要用带头结点了。

之前说顺序栈的时候我们谈到，栈会满，我们采用了一种结构处理这种情况，为其增开辟空间，解决栈满的情况。那么对于链栈，只要内存不满，就可以一直压栈存储元素。（系统内存耗尽除外，当发生这种情况时，系统已经瘫痪，所以程序的崩溃也已经无所谓了。），所以也不需要顺序栈中判断栈是否为满的情况这个函数。

ok我们继续先看一下链栈的结构和结构定义：

栈的结构

#define ElemType int

#define TRUE     1

#define FALSE    0

#define Status   int

typedef struct StackNode

{

    ElemType data;

    struct StackNode *next;

}StackNode;

typedef StackNode* LinkStack;   // 这里需要注意后边LinkStack  定义的变量就是指针类型的。

Status InitLinkStack(LinkStack *ls)

{

    *ls = NULL;

    return TRUE;

}

  链栈的压栈出栈

  顺序栈时已经说过，压栈出栈对于栈是最重要的结构，那么其他操作类比一下不带头结点单链表的操作，OK,压栈就是对不带头结点的头插，头插！对就是头插，不再是顺序表中说的尾插，没有搞错，我们退回去看链栈的结构图，当插入元素时，指向栈顶的指针指向新的元素，那么当通过指向栈顶的指针访问链表的时候，不就是后进先出，不就是符合栈的定义吗？其实顺序表也一定意义上头插，我们通过栈顶看，不就是头插吗？说顺序栈是尾插，是由于顺序栈是通过数组实现的，数组名是指向数组的第一个元素的，我们要通过数组名操作存储数据，所以才说是尾插。我们继续看结构图:

   结构弄清了链栈的压栈只是一个没有不带头结点的头插；ok我们看具体C语言代码实现：

压栈

//压栈，压栈成功返回TRUE,失败返回FALSE; 

Status PushStack(LinkStack *ls,ElemType x)

{

StackNode  *s = (StackNode *)malloc(sizeof(StackNode));

if(NULL == s)

{

printf("out of memory\n");

return FALSE;

}

s->data = x; 

if(NULL == *ls)

{

*ls = s;

s->next = NULL;

}

else

{

s->next = *ls;

*ls = s;

}

return TRUE;

}

出栈

    对于链栈的出栈要注意释放结点空间，防止内存泄露

//出栈,出栈成功返回TRUE，失败返回FALSE

Status PopLinkStack(LinkStack *ls)

{

StackNode *p = *ls;

if(NULL == p)

{

printf("栈已空,出栈失败\n");

return FALSE;

}

*ls = p->next;

free(p);

p = NULL;

return TRUE;

}   

链栈的清空

    这里由于不带头结点，所以这里只给出了清空链栈的操作，但是，需要强调意义不一样。

//清空链表，清空成功返回TRUE,失败返回FALSE

Status ClearLinkStack(LinkStack *ls)

{

StackNode *p = *ls;

while(NULL != p)

{

*ls = p->next;

free(p);

p = *ls;

}

*ls = NULL;

return TRUE;

}

链栈的获取栈顶元素

//获取栈顶元素，即就是栈不空的条件下，获取栈的首元素。

Status GetTop(LinkStack *ls,ElemType *value)

{

StackNode *p = *ls;

if(NULL == p)

{

printf("栈已空,获取栈顶元素失败\n");

return FALSE;

}

*value = p->data;

return TRUE;

}

链栈的获取栈的长度

    链栈不像顺序栈，通过top可以直接获得栈中元素个数，需要遍历所以元素统计栈的元素个数。

//获取链表长度

int  GetLength(LinkStack *ls)

{

StackNode *p = *ls;

int length = 0;

while(NULL != p)

{

length++;

p = p->next;

}

return p;

}

链栈的输出

Status  Show_LinkStack(LinkStack *s)

{

StackNode *p = *s; 

if(NULL == s)

{

printf("栈已空\n");

return FALSE;

}

while(NULL != p->next)

{

printf("%d  ",p->data);

p = p->next;

}

printf("\n");

}

    ok栈的基本操作就总结到这里，写道这里线性表，栈的基本操作我们都讲完了，会有人说，堆，线性表就只能进行这些基本操作吗？那岂不是很没有用，下一篇我将对线性表的应用简单总结一下。