22 May 2014
数据结构-栈

栈的定义

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶。

由定义我们可以知道栈其实就是一个线性表，前面一篇博客线性表中,我们已经详细介绍了线性表。我们得知线性表的两种实现方法，顺序存储结构和链式存储结构。

栈也一样，由两中实现方法：顺序栈和链式栈。

两种实现区别

顺序栈：就是利用数组实现的顺序栈，更流行的方法，唯一的危险可能是我们需要提前声明一个数组的大小。因为删除元素和插入元素都在数组的末端，所以不存在效率低的问题。 链式栈：所有操作都花费常数时间，因为没有哪个函数涉及到栈的大小，但有个缺点就是对于malloc和free调用的开销是昂贵的，push和pop操作都需要用到两者。

从上面我们可以得出：声明一个足够大而不至于浪费太多的空间通常并不困难。所以一般用数组实现会更高效，如果你连这点都做不到的话就用链式表来实现。

实现源码

具体实现方法就不多说了，这个一定要亲自试试的，如果做不出，在看源码。下面我直接给出两者的实现。

顺序栈源码:

/*************************************************************************
	> File Name: stackarray.c
	> Author: huanglei
	> Mail: huanglei2109@gmail.com 
	> Created Time: 2014年05月20日 星期二 16时17分23秒
    > 用数组实现栈
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>

#define MinStackSize 5
typedef void* ElemType ;
struct Node ;
typedef Node* Stack ;
struct Node
{
    int Capacity ;       //数组最大容量
    int TopOfStack ;        //栈顶，即数组最后一个元素的索引
    ElemType * Array ;   //动态数组
};

int IsEmpty(Stack s) ;
void MakeEmpty(Stack s) ;
Stack CreateStack(int MaxElemNum) ;
int IsFull(Stack s) ;
void DisposeStack(Stack s) ;
void Push(ElemType e,Stack s) ;
ElemType Top(Stack s) ;
void Pop(Stack s) ;
ElemType TopAndPop(Stack s) ;
void PrintStack(Stack s) ;

main()
{
    Stack s ;
    s = CreateStack(10) ;
    if(IsEmpty(s))
        printf("hi! I ma empty!\n") ;
    
    int i = 1 ;
    int j = 2 ;
    int k = 3 ;
    int l = 4 ;
    Push(&i,s) ;
    Push(&j,s) ;
    Push(&k,s) ;
    Push(&l,s) ;

    PrintStack(s) ;
    printf("\n") ;
    Pop(s) ;

    PrintStack(s) ;
    printf("\n") ;

    printf("the top of stack is %d\n",*(int*)TopAndPop(s)) ;

    MakeEmpty(s) ;

    PrintStack(s) ;

}

int IsEmpty(Stack s)
{
    return s->TopOfStack==-1 ;
}

Stack CreateStack(int MaxElemNum)
{
    Stack s ;
    if(MaxElemNum<MinStackSize){
        printf("stack size is too small !") ;
        exit(-1) ;
    }
    s = (Stack)malloc(sizeof(Stack)) ;
    if(s==NULL){
        printf("out of stack!") ;
        exit(-1) ;
    }

    /* init stack Array,Capacity,TopOfStack */
    s->Array = (ElemType*)malloc(sizeof(ElemType)*MaxElemNum) ;
    if(s->Array==NULL){
        printf("out of stack!") ;
        exit(-1) ;
    }
    s->Capacity = MaxElemNum ;
    s->TopOfStack = -1 ; //i.e stack is empty
}

void MakeEmpty(Stack s)
{
    if(s==NULL)
        printf("you must create stack first!") ;
    else
        s->TopOfStack = -1 ;
}

void Pop(Stack s)
{
    if(IsEmpty(s)){
        printf("stack is empty !") ;
        exit(-1) ;
    }else
        s->TopOfStack-- ;
}

ElemType TopAndPop(Stack s)
{
    if(IsEmpty(s)){
        printf("stack is empty!") ;
        exit(-1) ;
    }
    return s->Array[s->TopOfStack--] ;
}

void Push(ElemType e ,Stack s)
{
    if(s->TopOfStack==s->Capacity){
        printf("stack is full!") ;
        exit(-1) ;
    }else{
        s->Array[++s->TopOfStack] = e ;
    }
}

void PrintStack(Stack s)
{
    int i ;
    if(s==NULL)
        printf("please create Stack first!") ;
    else if(s->TopOfStack == -1)
        printf("stack is empty!") ;
    else
        for(i=0;i<=s->TopOfStack;++i)
            printf("%d->",*(int*)s->Array[i]) ;
}

链式栈源码

/*************************************************************************
	> File Name: stacklist.c
	> Author: huanglei
	> Mail: huanglei2109@gmail.com 
	> Created Time: 2014年05月19日 星期一 21时13分41秒
	> 用链表实现栈
 ************************************************************************/

#include<stdio.h>
#include<stdlib.h>
typedef void* ElemType ;
typedef struct Node
{
    ElemType elem ;
    Node *Next ;
}*Stack ;
/* 栈的函数*/
int IsEmpty(Stack s) ;
Stack CreateStack(void) ;
//void DisposeStack(Stack s) ;
void Push(ElemType x,Stack s) ;
ElemType Top(Stack s) ;
void Pop(Stack s) ;
void MakeEmpty(Stack s) ;

main()
{
    Stack s ;
    s = CreateStack() ;
    printf("%d\n",IsEmpty(s)) ;
    int i = 1 ;
    Push(&i,s) ;
    printf("%d\n",*(int*)Top(s)) ;
    int j = 2 ;
    Push(&j,s) ;

    Pop(s) ; 
    printf("%d\n",*(int*)Top(s)) ;

    MakeEmpty(s) ;
}

int IsEmpty(Stack s)
{
    return s->Next==NULL ;
}

Stack CreateStack(void)
{
    Stack s ;
    s = (Stack)malloc(sizeof(struct Node)) ;
    if(!s){
        printf("out of space!") ;
        exit(-1) ;
    }
    s->Next = NULL ;
    return s ;
}

void Push(ElemType e,Stack s)
{
    Stack current ;
    current = (Stack)malloc(sizeof(struct Node)) ;
    if(!current){
        printf("out of space!") ;
        exit(-1) ;
    }
    current->elem = e ;
    /* S->Next指向第一个元素*/
    current->Next = s->Next ;
    s->Next = current ;
}

ElemType Top(Stack s)
{
    return s->Next->elem ;
}

void Pop(Stack s)
{
    Stack tmp ;
    if(IsEmpty(s)){
        printf("empty stack") ;
        exit(-1) ;
    }else{
        tmp = s->Next->Next ;
        free(s->Next) ;
        s->Next = tmp ;
    }
}

void MakeEmpty(Stack s)
{
    if(!s){
        printf("you must create stack first!") ;
        exit(-1) ;
    }else{
        while(IsEmpty(s))
            Pop(s) ;
    }
}

2014年05月22日14:13:21

乐此不疲~

xule

scribble

22 May 2014 数据结构-栈