查看“３栈和队列”的源代码

== 栈的定义 ==
=== 基本概念 ===
定义：栈是限定仅在表尾进行插入和删除操作的线性表。栈 (Stack)是一种后进先出(last in first off，LIFO)的数据结构，又称为LIFO结构。把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的找称为空栈。

注意事项：首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。

基本操作：栈的插入操作，叫作进栈，也称压栈、入栈。栈的删除操作，叫作出找，也有的叫作弹栈。
[[文件:zhan.jpg|缩略图]]

=== 进栈出栈变化形式 ===
n个元素进栈共有多少种出栈顺序？

我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出：
                                     f(1) = 1     //即 1
                                     f(2) = 2     //即 12、21
                                     f(3) = 5     //即 123、132、213、321、231

然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑：元素a只可能出现在1号位置，2号位置，3号位置和4号位置(很容易理解，一共就4个位置，比如abcd,元素a就在1号位置)。

分析：

 1) 如果元素a在1号位置，那么只可能a进栈，马上出栈，此时还剩元素b、c、d等待操作，就是子问题f(3)；

 2) 如果元素a在2号位置，那么一定有一个元素比a先出栈，即有f(1)种可能顺序（只能是b），还剩c、d，即f(2)，     根据乘法原理，一共的顺序个数为f(1) * f(2)；

 3) 如果元素a在3号位置，那么一定有两个元素比1先出栈，即有f(2)种可能顺序（只能是b、c），还剩d，即f(1)，根据乘法原理，一共的顺序个数为f(2) * f(1)；

 4) 如果元素a在4号位置，那么一定是a先进栈，最后出栈，那么元素b、c、d的出栈顺序即是此小问题的解，即         f(3)；结合所有情况，即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3);

为了规整化，我们定义f(0) = 1；于是f(4)可以重新写为：

f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0)

然后我们推广到n，推广思路和n=4时完全一样，于是我们可以得到：

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0)
[[文件:ruzhan.png|缩略图]]

== 栈的抽象数据类型 ==
=== 栈的ADT定义 ===

	ADT 栈(stack)

	Data

	    同线性表。元素具有相同的类型，相邻元素具有前驱和后堆关系。
	Operation

	    InitStack ( *S )：初始化操作.建立一个空栈S。

	    DestroyStack ( *S )：若栈存在，則销毁它。

	    ClearStack (*S)：将栈清空。

	    StackEmpty ( S ):若栈为空，返回true,否則返回 false。

	    GetTop (S,*e)：若栈存在且非空，用e返回S的栈顶元素。

	    Push (*S,e)：若栈S存在，插入新元素e到栈S中并成为栈頂元素。

	    Pop (*S,*e)：删除栈S中栈顶元素，并用e返回其值。

	    StackLength (S)：返回回栈S的元素个数。

	endADT

== 栈的顺序存储结构及实现 ==
=== top指针 ===
定义一个top变量来指示栈顶元素在数组中的位置，这top就如同中学物理学过的游标卡尺的游标，如上图所示，它可以来回移动，意味着栈顶的top可以变大变小，但无论如何游标不能超出尺的长度。同理，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1。
[[文件:top2.jpg|缩略图]]

=== 结构体定义 ===
#include "stdio.h"

/* 存储空间初始分配量 */
#define MAXSIZE 20

/* SElemType类型根据实际情况而定，这里假设为int */
typedef int SElemType;

/* 顺序栈结构 */
typedef struct
{
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SqStack;

int main()
{
}
=== 进栈操作--push ===
如图所示，进栈操作push大概分为两步:

1.栈顶指针 S->top 先自增1，给需要进栈的元素腾出内存空间；

2.再赋值。就是给对应的数组元素赋值：S->data[S->top]=e。
代码实现：

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
    if(S->top == MAXSIZE -1) /* 栈满 */
    {
        return ERROR;
    }
    S->top++;				/* 栈顶指针增加一 */
    S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
    return OK;
}
[[文件:入栈.jpg|缩略图]]

=== 出栈操作--pop ===
代码实现：

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{
    if(S->top==-1)
        return ERROR;
    *e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
    S->top--;				/* 栈顶指针减一 */
    return OK;
}
完整可实现代码：
#include "stdio.h"
#include "stdlib.h"

#define OK 1
#define ERROR 0
/* 存储空间初始分配量 */
#define MAXSIZE 20

typedef int Status;
/* SElemType类型根据实际情况而定，这里假设为int */
typedef int SElemType;

/* 顺序栈结构 */
typedef struct
{
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}SqStack;

/*  构造一个空栈S */
Status InitStack(SqStack *S)
{
    /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */
    S->top=-1;
    return OK;
}

/* 从栈底到栈顶依次对栈中每个元素显示 */
Status StackTraverse(SqStack S)
{
    int i;
    i=0;
    while(i<=S.top)
    {
        visit(S.data[i++]);
    }
    printf("\n");
    return OK;
}

Status visit(SElemType c)
{
    printf("%d ",c);
    return OK;
}

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
    if(S->top == MAXSIZE -1) /* 栈满 */
    {
        return ERROR;
    }
    S->top++;				/* 栈顶指针增加一 */
    S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
    return OK;
}

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{
    if(S->top==-1)
        return ERROR;
    *e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
    S->top--;				/* 栈顶指针减一 */
    return OK;
}

int main()
{
    SqStack s;
    int opp;
    int j, value, e;

    if(InitStack(&s)==OK)
    {
        printf("顺序栈初始化成功。");
        StackTraverse(s);
    }

    printf("\n1.随机给栈赋值 \n2.栈遍历 \n3.进栈 \n4.出栈");
    printf("\n0.退出 \n请选择你的操作：\n");
    while(opp != '0'){
        scanf("%d",&opp);
        switch(opp){
            case 1:
                srand(time(0));
                for(j=1;j<=10;j++)
                {
                    Push(&s,rand()%100+1);
                }
                StackTraverse(s);
                break;

            case 2:
                StackTraverse(s);
                break;

            case 3:
                printf("请输入需要进栈的元素：");
                scanf("%d", &value);
                Push(&s, value);
                StackTraverse(s);
                break;

            case 4:
                Pop(&s,&e);
                printf("弹出的栈顶元素 e=%d\n",e);
                StackTraverse(s);
                break;

            case 0:
                exit(0);
        }
    }
}