数据结构--栈

栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表的子集，它们是操作受限的线性表，因此可称为限定性的数据结构。

1.栈和队列的定义和特点

1.1 栈的定义和特点

栈是限定

仅在表尾进行插入或删除操作

的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。

假设栈 S=(a1,a2,a3,…,an),则称a1为栈底元素，an为栈顶元素。进栈的第一个元素为栈底元素，退栈的第一个元素为栈顶元素。栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出的线性表。

在程序设计中，如果需要按照保存数据时相反的顺序来使用数据，则可以利用栈来实现。

1.2 队列的定义和特点

和栈相反，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。

2. 栈的表示和操作的实现

顺序栈的表示和实现

顺序栈是指利用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。另设指针base指示栈底元素在顺序栈中的位置。当top 和 base 的值相等时，表示空栈。顺序栈的定义如下:

//-------顺序栈的存储结构------
#define MAXSIZE 100                    //顺序栈存储空间的初始分配量
typedef struct
{
  SElemType *base;                    //栈底指针
  SElemType *top;                     //栈顶指针
  int stacksize;                      //栈可用的最大容量
}SqStack;

base为栈底指针，初始化完成后，栈底指针 base 始终指向栈底的位置，若base 的值为NULL，则表明栈结构不存在。 top 为栈顶指针，其初值指向栈底。每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针 top减1.因此，栈空时， top 和 base 的值相等，都指向栈底；栈非空时，top始终指向栈顶元素的上一个位置。

2.1 初始化

顺序栈的初始化操作就是为顺序栈动态分配一个预定义大小的数组空间。

算法2.1 顺序栈的初始化

[算法步骤]

为顺序栈动态分配一个最大容量为MAXSIZE的数组空间，使base指向这段空间的基地址，即栈底。
栈顶指针top 初始为 base，表示栈为空。
stacksize 置为栈的最大容量MAXSIZE

[算法描述]

Status InitStack(SqStack &S)
{//构造一个空栈S
  S.base=new SElemType[MAXSIZE];                               //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
  if(!S.base) exit(OVERFLOW);                                  //存储分配失败
  S.top=S.base;                                                // top初始为base,空栈
  S.stacksize=MAXSIZE;                                         //stacksize置为栈的最大容量MACSIZE
  return OK;
}

2.2 入栈

入栈操作是指在栈顶插入一个新的元素。

算法2.2 顺序栈的入栈

[算法步骤]

判断栈是否满，若满则返回ERROR。
将新元素压入栈顶，栈顶指针加1.

[算法描述]

Status Push(SqStack &S, SElemType e)
{//插入元素e为新的栈顶元素
  if (S.top-S.base==S.stacksize) return ERROR;    //栈满
  *S.top++=e;                                     //元素e压入栈顶，栈顶元素加1
  rturn OK;
}

2.3 出栈

出栈操作是将栈顶元素删除

算法2.3 顺序栈的出栈

[算法描述]

判断栈是否为空，若空则返回ERROR。
栈顶指针减1,栈顶元素出栈。

[算法描述]

Status Pop(SqStack &S,SElemType &e)
{// 删除S的栈顶元素，用e返回其值
  if(S.top==S.base) return ERROR;               //栈空
  e=*--S.top;                                   // 栈顶指针减1,将栈顶元素赋给e
  return OK;
}

2.3 取栈顶元素

当栈非空时，此操作返回当前栈顶元素的值，栈顶指针保持不变

算法2.4 取顺序栈的栈顶元素

[算法描述]

SElemType GetTop(SqStack S)
{//返回S的栈顶元素，不修改栈顶指针
  if(S.top!=S.base)                            //栈非空
    return *(S.top-1);                         //返回S的栈顶元素，不修改栈顶指针
}

3.链栈的表示和实现

链栈是指采用链式存储结构实现的栈。通常链栈用单链表来表示。链栈的结点结构与单链表的结构相同，定义如下：

//------链栈的存储结构--------
tyoedef struct StackNode
{
  ElemType data;
  struct StackNode *next;
}StackNode,*LinkStack;

由于栈的主要操作是在栈顶插入和删除，显然以链表的头部作为栈顶是最方便的。

3.1 初始化

链栈的初始化操作就是构造一个空栈，因为没必要设头结点，所以直接将栈顶指针置空即可。

算法 3.1 链栈的初始化

[算法描述]

Stack InitStack(LinkStack &S)
{//构造一个空栈，栈顶指针置空
  S=NULL;
  return OK;
}

3.2 入栈

链栈在入栈前不需要判断栈是否满，只需要为入栈元素动态分配一个结点空间

算法 3.2 链栈的入栈

[算法步骤]

为入栈元素e分配空间，用指针p指向
将新结点数据域置为e
将新结点插入栈顶
修改栈顶指针为p

[算法描述]

Status Push(LinkStack &S.SelemType e)
{//在栈顶插入元素e
  p=new StackNode;                    //生成新结点
  p->data=e;                          //将新结点数据域置为e
  p->next=S;                         //将新结点插入栈顶
  S=p;                               //修改栈顶指针为p
  return OK;
}

3.3 出栈

和顺序栈一样，链栈在出栈前也需要判断栈是否为空，不同的是，链栈在出栈后需要释放出栈元素的栈顶空间

算法 3.3 链栈的出栈

[算法步骤]

判断栈是否为空，若空则返回ERROR
将栈顶元素赋给e
临时保存栈顶元素的空间，以备释放
修改栈顶指针，指向新的栈顶元素
释放原栈顶元素的空间

[算法描述]

StATUS Pop(LinkSTack &S,SElemType &e)
{
  if (S==NULL) return ERROR;
  e=S->data;
  p=S;
  S=S->next;
  delete p;
  return OK;
}

算法 3.4 取链栈的栈顶元素

[算法描述]

SElemType GetTop(LinkStack S)
{
  if(S!=NULL)
    return S->data;
}