数据结构之栈

   

    栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊的含义，称为栈顶，相应的，表头端称为栈底。不含元素的空表称为空栈。如下所示。

   

    从上图我们可以看出，栈的特点是：后进先出。

1、栈的表示和实现

    和线性表一样，栈也有两种存储表示方法：顺序存储结构和链式存储结构。

1.1 顺序存储结构

    顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放在栈底到栈顶的元素，同时附指针。一个较合理的做法是：先为栈分配一个基本容量，然后在应用的过程中，当栈的容量不够使用时，再逐渐扩大。为此，设定两个常量：STACK_INIT_SIZE（存储空间初始化分配量）和STACKINCREMENT（存储空间分配增量）。

    来看下顺序栈的结构定义，如下所示。

#define STACK_INIT_SIZE   100
#define STACKINCREMENT    10
typedef int ElemType //根据实际情况而定，假设为int
typedef struct
{
     ElemType *base; //在栈构造之前和销毁之后，base的值为NULL
     ElemType *top;  //栈顶指针
     int stacksize;  //当前已经分配的存储空间，以元素为单位
}SqStack;

 

1.1.1 顺序栈的基本操作

/*********************************************************/
/*********************一共六种基本操作**********************/
/*
 1、构造空栈：InitStack
 2、获取栈顶元素：GetTop
 3、弹出栈：Pop
 4、压入栈：Push
 5、判断栈是否为空：IsEmpty
 6、判断栈是否为满：IsFull
*/
/*********************************************************/
#include <stdio.h>
#include <stdlib.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define ElemType int

#define ERROR 0
#define OK 1

typedef struct
{
    ElemType *base;
    ElemType *top;
    int stacksize;
}SqStack;

//初始化栈
int InitStack(SqStack *s)
{
    s->base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
    if(s->base == NULL)
    {
        fprintf(stderr, "malloc error.\n");
        return ERROR;
    }

    s->top = s->base;
    s->stacksize = STACK_INIT_SIZE;

    return OK;
}

//如果栈不为空，栈顶元素，由e返回，并返回OK；否则，返回ERROR
int GetTop(SqStack s, ElemType *e)
{
    if(s.top == s.base)
    {
        fprintf(stderr, "stack is empty.\n");
        return ERROR;
    }

    *e = *(s.top - 1);

    return OK;
}

//如果栈不为空，插入元素e，返回OK；否则，返回ERROR
int Push(SqStack *s, ElemType e)
{
    if(s->top - s->base >= s->stacksize)
    {
        //栈满，追加元素
        s->base = (ElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT)*sizeof(ElemType));
        if(s->base == NULL)
        {
            return ERROR;
        }

        s->top = s->base + s->stacksize;
        s->stacksize += STACKINCREMENT;
    }
    *s->top = e;
    s->top++;

    return OK;
}

//若栈不空，则删除s栈顶元素，用e返回其值，并返回OK；否则返回ERROR
int Pop(SqStack *s, ElemType *e)
{
    if(s->base == s->top)
    {
        fprintf(stderr, "stack is empty.\n");
        return ERROR;
    }

    *e = *(s->top - 1);
    s->top--;

    return OK;
}

//判断栈是否为空
void IsEmpty(SqStack s)
{
    if(s.base == s.top)
    {
        fprintf(stdout, "the stack is empty.\n");
    }
    else
    {
        fprintf(stdout, "the stack is not empty.\n");
    }
}

//判断栈是否已经满
void IsFull(SqStack s)
{
    if(s.top - s.top >= s.stacksize)
    {
        fprintf(stdout, "the stack is full.\n");
    }
    else
    {
        fprintf(stdout, "the stack is not full.\n");
    }
}
//销毁栈_转
int DestroyStack(SqStack *s)
{
     free(s->base);
     s->base = NULL;
     s->top = NULL;
     s->stacksize = 0;
     return OK;
}
//把栈置空_转
int ClearStack(SqStack *s)
{
    s->top = s->base;
    return OK;
}
//返回栈元素的个数
int StackLength(SqStack s)
{
    return (s.top - s.base);
}

int main(int argc, char **argv)
{
    SqStack s;
    int i = 0;

    InitStack(&s);

    IsEmpty(s);
    IsFull(s);

    for(i = 0; i < 100; i++)
    {
        if(OK == Push(&s, i))
        {
            continue;
        }
        else
        {
            fprintf(stderr, "压栈错误.\n");
            exit(EXIT_FAILURE);
        }
    }

    int e;
    printf("栈顶元素为:\n");
    if(OK == GetTop(s, &e))
    {
        printf("%d\n", e);
    }
    else
    {
        fprintf(stderr, "栈为空.\n");
    }

    printf("压入栈的元素为:\n");
    for(i = 0; i < 7; i++)
    {
        if(OK == Pop(&s, &e))
        {
            printf("%d ", e);
        }
        else
        {
            fprintf(stderr, "栈为空.\n");
        }
    }
    printf("\n");

    IsEmpty(s);
    IsFull(s);


    return 0;
}

1.2 栈的链式存储结构

    对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那么此时的计算机操作已经面临死机崩溃的情况，而不是这个更链表是否溢出的问题。 但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

  

    链栈的结构代码如下：

#define ElemType int
typedef struct StackNode
{
   ElemType data;
   strcut StackNode *next;
}StackNode, *LinkStackPtr;

typedef strcut LinkStack
{
   LinkStackPtr top;
   int count;
}LinkStack;

1.2.1 栈的链式存储结构——进栈操作

    对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，示意图如图所示。

/*插入元素e为新的栈顶元素*/
int Push(LinkStack *s, ElemType e)
{
   LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode);
   if(s == NULL)
   {
      return ERROR;
   }
   s->data = e;
   s->next = s->top; //把当前的栈顶元素赋值给新结点的直接后继
   s->top = s; //将新的结点s赋值给栈顶指针
   s->count++;

   return OK;
}

1.2.2 栈的链式存储结构——出栈操作

    至于链栈的出栈pop操作，也是比较简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。如图所示。

/*若栈不空，则删除s的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/
int Pop(LinkStack *s, ElemType *e)
{
   LinkStackPtr p;
   if(StackEmpty(*s))
   {
      return ERROR;
   }
   p = s->top; //将栈顶结点赋值给p
   s->top = s->top->next; //使得栈顶指针下移一位，指向后一结点
   free(p); //释放结点p
   s->count--;

   return OK;
}

    栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。

1.2.3 链栈的其他一些操作

/*初始化操作*/
void InitStack(LinkStack &s)
{
   s->top = NULL;
   s->count = 0;
}
/*判断栈是否为空*/
int StackEmpty(LinkStack s)
{
   if(s.top == NULL && s.count == 0)
   {
        return OK;
   }
   return ERROR;
 }
/*获取栈顶元素*/
void GetTop(LinkStack s, ElemType *e)
{
   if(StackEmpty(s))
          return ERROR:
   *e = s.top->data;
}

    如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

   

   参考：严蔚敏老师之《数据结构》、《大话数据结构》

                                                                                                                                                   梦醒潇湘love 

                                                                                                                                              2013-01-10 20:15