ArrayStack(栈)

　　顺序栈即数组型的栈。什么是栈呢?简单来说就像一个刚好装的下乒乓球大小的球筒，假设不能暴力打开球筒且只有一端有出口，那你放入或取出里面的球的操作都只能在一端进行，并且把球放进去或取出来都是由顺序决定的，也就是说你只能从里面没有球或空间足够的时候把球放进去，然后需要的时候再从最外面的那个球拿出一个才能再拿里面的，这就是后进先出(LILO - last in last out)，栈的原理就是这么回事。其本质基本上就是一个顺序储存结构，也就是一个线性表，所以栈是前驱后继的关系的线性结构。人们口中常说的堆栈一般就是指栈，而不是堆和栈。

　　栈的应用也很重要，比如做递归的时候就是一个栈的原理、符号的匹配问题、后缀表达式等等。

　　code:

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define EmptyToStack -1

#define MAXSIZE 500

#define TRUE 1

#define FALSE 0;

typedef int ElemType;

typedef int Status;

typedef struct

{

    ElemType * data;

    int top;

}Stack;

Stack * CreateStack();

Status IsEmpty();

Status IsFull();

Status Push();

Status Pop();

int Top();

int StackLength();

Stack * CreateStack(void)

{

    Stack * S;

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

    S -> data = (ElemType *)malloc(sizeof(ElemType));

    S -> top = EmptyToStack;

    return S;

}

Status IsEmpty(Stack * S)

{

    return S -> top == EmptyToStack;

}

Status IsFull(Stack * S)

{

    return S -> top == MAXSIZE;

}

Status Push(Stack * S, ElemType Elem)

{

    if(IsFull(S))

        return FALSE;

    S -> data[++ S -> top] = Elem;

    return TRUE;

}

Status Pop(Stack * S)

{

    if(IsEmpty(S))

        return FALSE;

    S -> top --;

    return TRUE;

}

int Top(Stack * S)

{

    return S -> top;

}

int StackLength(Stack * S)

{

    return S -> top + 1;

}

int main(void)

{

    ElemType e;

    Stack * p;

    char c;

    int i;

    p = CreateStack();

    puts("1) 进栈        2) 出栈");

    puts("3) 遍历栈    4) 返回栈顶元素");

    puts("5) 清空栈    6) 当前栈的长度");

    puts("q) 退出");

    while((c = getch()) != 'q')

    {

        if(c == '1')

        {

            puts("请输入数据:");

            scanf("%d",&e);

            Push(p, e);

        }

        if(c == '2')

        {

            puts("当前栈顶元素为:");

            printf("%d\n",p -> data[Top(p)]);

            Pop(p);

            puts("当前栈顶元素为:");

            printf("%d\n",p -> data[Top(p)]);

        }

        if(c == '3')

        {

            puts("显示数据:");

            for(i = Top(p); i > EmptyToStack; i--)

            {

                printf("%d -> ",p -> data[i]);

            }

            printf("NULL\n");

        }

        if(c == '4')

        {

            puts("当前栈顶元素为:");

            printf("%d\n",p -> data[Top(p)]);

        }

        if(c == '5')

        {

            do Pop(p);

            while(p -> top != EmptyToStack);

            if(!IsEmpty(p))

                puts("ERROR!\n");

        }

        if(c == '6')

        {

            printf("当前栈长: %d\n",StackLength(p));

        }

    }

    return 0;

}

巴特西

ArrayStack(栈)

最新文章

热门文章