今天我们来学习一下栈。首先我们用C来表示，并且首先用数组去实现它。在数据结构中，栈是一中特殊的ADT（抽象数据类型）。它的特殊性在于它的操作只能在一个位置进行，无论是入栈还是出栈。这个位置是表的末端，也叫做栈顶。栈是操作受限的线性表。栈在计算机科学中几乎无处不在，是一中非常重要的数据结构。

用数组实现栈代码简单，但是也有缺点，那就是必须提前声明一个数组的大小，并且在程序的运行过程中不能改变，这在一定程度上限制了栈的灵活性，但是却带来了更为简洁的代码。数组的下标为0我们表示栈空。

#include <stdio.h>

#include <malloc.h>

#define STACK_SIZE 100

 

//栈的节点声明

typedef struct Stack{

    int top;

    int array[STACK_SIZE];

    }Stack;

Stack S;//定义一个栈

//初始化一个空栈

int Init_Stack(){

    S.top = 0;//top为0表示空栈

    return 1;

    }

//测试是否为空栈

int IsEmpty(){

    if(S.top==0)return 1;

       else return 0;

    }

//元素e入栈

int Push(int e){

    S.top++;

    S.array[S.top] = e;

    return S.top;

    }

//出栈,并返回该元素值

int Pop(){

    S.top--;

    return S.array[S.top+1];

    }

void main(){

    int i=0,j=0;

     Init_Stack();

     for(;i<=5;i++){

         Push(i);

         }

     for(i=0;i<=5;i++){

         j = Pop();

         printf("[%d] ",j);

         }

    getch();

    }

栈的基本操作实现后，我们来看下利用栈的一个小题目。编写程序，识别以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和2都不含‘&’字符，且序列1和序列2互为逆序列。这其实就是利用栈的Pop()操作。代码如下：

#include <stdio.h>

#include <malloc.h>

#define STACK_SIZE 200

#define   EleType  char

//栈的节点声明

typedef struct Stack{

    EleType top;

    EleType array[STACK_SIZE];

    }Stack,*pStack;

//初始化一个空栈

int Init_Stack(pStack S){

    S->top = 0;//top为0表示空栈

    return 1;

    }

//测试是否为空栈

int IsEmpty(pStack S){

    if(S->top==0)return 1;

       else return 0;

    }

//元素e入栈

int Push(pStack S,EleType e){

    S->top++;

    S->array[S->top] = e;

    return S->top;

    }

//出栈,并返回该元素值

EleType Pop(pStack S){

    S->top--;

    return S->array[S->top+1];

    }

void main(){

    int i=0;

    pStack S;

    char a[]="abc&cba@";

    char b[]="fgh&hgf@";

    S = (pStack)malloc(sizeof(Stack));

    Init_Stack(S);

     while(b[i]!='@'){

        Push(S,b[i]);

         i++;

        }

        i=0;

        for(;i<=6;i++){

              if(b[i]!=Pop(S)){

              printf("error");

              break;

             }

            }

 

    if(i>6)printf("ok");

    getch();

    }