数据结构——栈的实现及应用

一、何为栈？
     栈，是一种线性表的变形，它是一种特殊的线性表。特殊之处是栈的数据插入和删除操作只允许在表尾（或表头，这要看如何实现）。
二、栈的实现
     栈的基本操作：1.创建一个空栈 2.判空 3.出栈 4.入栈 5.查看长度 6.仅获得栈顶数据
实现代码：

/*
 *File Name:    StackData.h
 *Author Name:  Dronsure
 *Create Time:  Sat Sep 19 20:39:42 2015
 */
/*

若要自定义数据结构体，请修改 StackData.h StackData.c

/

#ifndef STACKDATA_H

#define STACKDATA_H

typedef struct

{

int data;

} ElementType;    //自定义数据结构体

void VoluationElementTypeData(ElementType dataDest,ElementType dataSource);    //自定义数据结构体赋值函数

ElementType InputElementTypeData();    //自定义数据结构体输入函数

void PrintElementTypeData(ElementType data);    //输出自定义数据结构体数据函数

#endif / STACKDATA_H */
/*

*File Name:    StackData.c

*Author Name:  Dronsure

*Create Time:  Sat Sep 19 20:47:25 2015

*/
/*

*若要自定义数据结构体，请修改 StackData.h StackData.c

*/
#include "StackData.h"

#include <stdio.h>

void VoluationElementTypeData(ElementType* dataDest, ElementType dataSource)

{

dataDest->data = dataSource.data;

}

ElementType InputElementTypeData()

{

ElementType tmpData;

printf("Please input data: \n");

scanf("%d",&tmpData.data);

return tmpData;

}

void PrintElementTypeData(ElementType dataSource)

{

printf("The data is :%d\n",dataSource.data);

}
/*

*File Name:    Stack.h

*Author Name:  Dronsure

*Create Time:  Fri Sep 18 21:08:09 2015

*/

#include "StackData.h"

#ifndef STACK_H

#define STACK_H

typedef struct Node

{

ElementType data;

struct Node *next;

struct Node *previous;

} Stack, StackNode;    //数据结点

Stack CreateStack();    //创建一个栈

char isEmpty(Stack stackIns);    //判断栈是否为空

ElementType pop(Stack stackIns);    //出栈

void push(Stack stackIns, ElementType dataSource);  //入栈

#endif / STACK_H */
/*

*File Name:    Stack.c

*Author Name:  Dronsure

*Create Time:  Fri Sep 18 21:03:17 2015

/

#include "Stack.h"

#include <malloc.h>

Stack CreateStack()

{

Stack head = NULL;

head = (StackNode)malloc(sizeof(StackNode));

head->next = NULL;

return head;

}

char isEmpty(Stack stackIns)

{

return stackIns->next == NULL;

}

void push(Stack stackIns, ElementType dataSource)

{

StackNode *p = stackIns;

StackNode *tmp;

while(p->next != NULL)

p = p->next;

tmp =(StackNode ) malloc(sizeof(StackNode));

VoluationElementTypeData(&tmp->data,dataSource);

tmp->next = NULL;

tmp->previous = p;

p->next = tmp;

}

ElementType pop(Stack stackIns)

{

StackNode p = stackIns;

ElementType tmp;

while(p->next != NULL)

p = p->next;

p->previous->next = NULL;

VoluationElementTypeData(&tmp, p->data);

free(p);

return tmp;

}
/*

*File Name:    main.c

*Author Name:  Dronsure

*Create Time:  Fri Sep 18 20:46:49 2015

/

#include <stdio.h>

#include "Stack.h"

int main(int argc, char argv[])

{

Stack stackIns;

stackIns = CreateStack();

printf("%d\n",isEmpty(stackIns));

push(stackIns, InputElementTypeData());

printf("%d\n",isEmpty(stackIns));

push(stackIns, InputElementTypeData());

PrintElementTypeData(pop(stackIns));

PrintElementTypeData(pop(stackIns));

printf("%d\n",isEmpty(stackIns));

return 0;

}