在我们日常软件操作中，经常遇到“撤消”、“后退”，在网页浏览时，也遇到“后退‘，“上一步“等操作，类似这样的代码是如何实现呢？这里其实就是用到栈的方式来实现的。

1、栈的定义

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶(top)，相对地，把另一端称为栈底(bottom)。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。所以：

栈是限定仅在表尾进行插入和删除操作的线性表。栈又称为先进先出（Last In First Out）的线性表，简称LIFO结构。

首先栈是一个线性表，栈元素具有线性关系，也就是前驱后继关系。注意，定义中说的表尾，不是栈底，而是说栈顶。它的特别是限制这个线性表的插入和删除位置，但它始终只在栈顶进行。

2、栈的特点

栈的特点是“先进后出，后进先出”。符合这个特征的数据才可以在栈中存储。

3、栈的操作

3.1栈的插入操作，叫进栈，也称压栈，入栈。如图所示：

5-1

3.2栈的删除操作，叫出栈，也叫弹栈，如图所示：

5-2

3.3 进栈出栈的顺序形式，如果有3个数字元素1、2、3依次进栈：

（1）1、2、3进，再3、2、1出，那么出栈次序为3 2 1;

（2）1进，1出，2进，2出，3进，3出，就是进一个出一个，那么出栈次序为1 2 3;

（3）1进，2进，2出，1出，3进，3出，那么出栈次序为2 1 3;

3个元素，大家可以排一下，共有5种可能的出栈次序。

4、栈的实现

前边的文章也讲过，所有的数据结构基本都是由数组和链表演化而来的，所以今天讲的栈这种数据结构也不例外。

栈的实现主要有两种，一种是数组的实现，叫做顺序存储结构，另外一种是链表的实现，叫做链式存储结构。如下：

4.1 栈的顺序存储结构

既然栈是线表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化。顺序栈是利用一组地址连续存储单元依次存放自栈底到栈顶的数据元素，同时用一个变量top记录栈顶的位置，通常称此变量为栈顶指针。

顺序栈的结构定义

#define StackSize 20//顺序栈的初始分配空间
typedef string ElemType;
typedef struct
{
   ElemType data[MaxSize];   //保存栈中元素
   int top;                     //栈顶指针
}SqStack;

由于数组下表的约定从0开始，因此用top=-1表示栈空。若现有一个栈，假设StackSize是4,则栈有普通情况，空栈和栈满情况如下图：

5-3

//初始化栈
void InitStack(SqStack st)
{
     St->top = -1;
}

//进栈运算
int Push(SqStack *st, ElemType e)
{
    if (st->top == MaxSize - 1) {    //判断栈满
    return ERROR;
}
else
{
    St->top++;
   St->data[st->top]= e;
   return OK;
    }
}

//出栈运算
int Pop(SqStack *st, ElemType e)
{
    if (st->top == -1)      //判断栈空
    return ERROR;
   else
  {
   e = st->data[st->top];
   St->top--;
   return OK;
   }
}

//取栈顶元素运算
int GetTop(SqStack st, ElemType e)
{
    if (st->top == -1)
    return ERROR;
    else
    {
     e = st->data[st->top];
     return OK;
     }
}

以上操作没有涉及到任何循环语句，所以时间复杂度均是O(1)

4.2 栈的链式存储结构

栈的链式存储结构也叫链栈，是通过线性表的链式存储结构实现的，操作起来和单链表形式差不多。链栈的操作与链表类似，入栈和出栈都在链表的表头进行。所以通常对于链栈来说，是不需要头结点的。

对于链栈来说，基本不存在栈满的情况，在定义链栈的结点时，定义一个存放数据的变量data，一个存放后继指针的变量*next,结点定义如下：

Typedef struct StackNode{
    ElemType data;         //定义数据变量
    struct StackNode *next;   //定义后继指针变量
}StackNode,*LinkStackPtr;

定义栈的时候，由于栈是在顶部进行元素的插入或删除操作，所以，需要一个栈顶指针top，因为是链栈，还需要一个计数变量count。链栈的结构定义如下：

Typedef struct Linkstack{
     LinkStackPtr  top;//定义栈顶指针
     int count;//定义计数变量
}Linkstack;

接下来就是元素的插入操作。因为是链式存储结构，满足栈的基本性质的情况下进行元素插入(只能在栈顶进行元素的插入操作）所以，在data中存放数据后，指针next中存放的就是top指针中的值，因为top指向的是栈顶。还需要再将栈顶指针指向新的存储空间。具体实现代码如下：

bool push(Linkstack *s,ElemType e){
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    s->data=e;
    s->next=s->top;//存放top指针值
    s->top=s;//指向栈顶元素
    s->count++;
    return true;
}

元素的删除操作与插入操作相反。删除一个元素只要将栈顶指针指向它的前一个元素，然后释放删除元素的空间。代码如下：

bool pop(Linkstack *s,ElemType e){
    LinkStackPtr p;
    If(StackEmpty(*s)
       Return ERROR;
    p=s->top;
    *e=s->top->data;
    s->top=s->top->next;    //栈顶指针指向前一个元素
    free(p);               //释放p结点
    s->count--;            //元素数量递减
    return true;
}

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

栈的作用分为以下几点：

（1）栈是每个函数架构的基础，实现了函数的重复利用，如传递参数，保存临时变量。

（2）问题发生的时候，可以利用栈来了解问题发生的情况，如保存现场/上下文。

（3）栈是构建出操作系统多任务模式的基础。