数据结构之栈和队列(C语言版)
数据结构学习继续向前推进,之前对线性表进行了学习,现在我们进入栈和队列的学习。同样我们先学习一些基本概念以及堆栈的ADT.
创新互联公司专注于岚山网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供岚山营销型网站建设,岚山网站制作、岚山网页设计、岚山网站官网定制、重庆小程序开发公司服务,打造岚山网络公司原创品牌,更为您提供岚山网站排名全网营销落地服务。
栈和队列是两种中重要的线性结构。从数据结构角度看,栈和队列也是线性表,只不过是受限的线性表。因此可以称为限定性数据结构。但从数据类型来看,他们是和线性表大不相同的两类重要的抽象数据类型。
栈:(stack)是限定仅在表尾进行相应插入和删除操作的线性表。因此,对栈来说,表尾有其特殊含义,称为栈顶,表头称为栈底,不含元素的空表称为空栈。栈一个重要特性就是后进先出.OK,我们来看一下栈的结构:
ADT Stack
{
数据对象:D = {ai| ai属于ElemSet,i = 1,2,……,n, n >= 0 }
约定an端为栈顶,a1端为栈底。
基本操作:
Status Init_SeqStack(SeqStack *s)
初始化栈,构造一个空栈。
Status Destory(SeqStack *s)
摧毁栈
Status Clear(SeqStack *s)
清空栈
int IsEmpty(SeqStack *s)
判断是否为空栈,是空栈返回1,不是空栈返回0
int IsFull(SeqStack *s )
判断栈是否满,栈满返回1,没有满返回0
int GetLength(SeqStack s)
返回栈中元素的个数
Status PushStack(SeqStack *s,ElemType x)
插入元素e为新的栈顶元素
Status GetTop(SeqStack *s,ElemType *value)
获取栈顶元素,用value带回
Status PopStack(SeqStack *s)
删除栈顶元素
Status Show_Stack(SeqStack s)
打印输出栈中元素
}
以上就是栈的抽象数据类型,好了我们接下来用C语言实现栈结构,既然栈受限的线性表,线性表有链式存储结构和顺序存储结构,那么栈也同样有两种,顺序栈和链栈。依然沿袭过去先弄清结构再通过代码解释。开篇已经讲了栈是受限的线性表,那么我们就要类比着看栈的操作:顺序栈,就类比顺序表。链栈就类比单链表。ok,我们先来看顺序栈:
顺序栈
顺序栈,即就是栈的顺序存储结构,是利用一组连续的存储单元一次依次存放自栈底到栈顶的数据元素,同时附设top指示栈顶元素在顺序表中的位置,通常的习惯做法以top=0表示空栈,鉴于以C语言作为描述语言时,如此设定会带来很大不便;另一方面,由于栈在使用过程中所需的最大空间大小无法估计。因此一般来说,先为初始化空栈时不应设定栈的最大空间容量。一个较合理的做法是:先为栈分配一个基本容量,然后在应用过程中,当栈的空间不够时再逐段扩大。为此,可以设定两个常 STACK_INIT_SIZE(存储空间初始分配量)和STACK_INC_SIZE(存储空间分配增量)
ok我们先定义顺序栈的结构:
#define ElemType char
#define Status int
#define FALSE 0
#define TRUE 1
#define STACK_INIT_SIZE 8 存储空间初始分配量
#define STACK_INC_SIZE 20 存储空间分配增量
typedef struct SeqStack
{
ElemType *bace;
int capacity;
int top;
}SeqStack;
//判断是否为空栈,栈结构中的top也就记录了顺序栈中的状态,栈空返回1,非空返回0
int IsEmpty(SeqStack *s)
{
return s->top == 0;
}
//判断是否栈满,栈满返回1,非满返回0
int IsFull(SeqStack *s )
{
return s->top >= s->capacity;
}
//此函数解决,上面提到的,当基空间不够时,增加空间。增加成功放回TRUE,也就是1,增加失败返回FALSE
Status IncSize(SeqStack *s)
{
ElemType *newbase = (ElemType *)realloc(s->bace,sizeof(ElemType) * (s->capacity + STACK_INC_SIZE));
if(NULL == newbase)
{
printf("out of memory\n");
return FALSE;
}
s->bace = newbase;
s->capacity += STACK_INC_SIZE;
return TRUE;
}
顺序栈的初始化
//初始化栈,就是为栈分配一个基空间,修改结构中top让其等于0,表示空栈。
//初始化成功返回TRUE,初始化失败返回FALSE;
Status Init_SeqStack(SeqStack *s)
{
s->bace = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
if(NULL == s->bace )
{
printf("out of memory,filed Init_SeqStack\n");
return FALSE;
}
s->top = 0;
s->capacity = STACK_INIT_SIZE;
return TRUE;
}
顺序栈的压栈出栈
这里一直强调栈是受限的线性表,那么,初始化,等其他的基本类同,主要区别就是在栈中的压栈和出栈,压栈出栈,对顺序栈就是对顺序表的尾插、尾删,ok我们继续用图理一下结构。
//入栈(压栈)成功返回TRUE,失败返回FALSE
Status PushStack(SeqStack *s,ElemType x)
{
/*
这里就是解决栈的基空间不够会满的情况,需要调用前边定义的函数再次为其增加空间。这里的
if条件需要注意,IsFull(s) 函数,当栈已满是返回1结果为真,IncSize(s)函数返回值,当开辟
成功后返回1结果为真,所以当开辟成功后取反就为价所以&&操作后为假,if模块就不执
行了,就继续执行后边的代码模块
*/
if(IsFull(s) && !IncSize(s))
{
printf("栈空间已满,%d不能入栈\n",x);
return FALSE;
}
s->bace[s->top++] = x;
//s->top++; 简化代码
return TRUE;
}
//出栈
Status PopStack(SeqStack *s)
{
if(IsEmpty(s))
{
printf("栈已空,不能出栈\n");
return FALSE;
}
s->top--;
return TRUE;
}
顺序栈的获取栈顶元素
继续看上一张图,中的那段话,在C语言中,由于数组下标是从0开始的,top中保存栈中元素个数,所以base[top]是指向栈顶元素的上一个空间,所以获取栈顶元素时就需要减去1.
//获取栈顶元素,
Status GetTop(SeqStack *s,ElemType *value)
{
if(IsEmpty(s))
{
printf("栈空间已空,不能取栈顶元素\n");
return FALSE;
}
*value = s->bace[s->top - 1];
return TRUE;
}
顺序栈的的长度
top中保存的就是栈中的元素个数,所以获取栈中元素个数直接返回top的值就可以。
//获取栈长度
int GetLength(SeqStack s)
{
return s.top;
}
顺序栈的清空栈
//清空栈,清空栈就是让栈为空,所以只需要把top修改为0即可。
Status Clear(SeqStack *s)
{
s->top = 0;
return TRUE;
}
顺序栈的摧毁栈
//摧毁栈,摧毁栈,意味着,不仅要top修改为0,更要释放掉栈的空间。
Status Destory(SeqStack *s)
{
free(s->bace);
s->bace = NULL;
s->top = 0;
return TRUE;
}
顺序栈的输出
//输出栈中的元素,既然栈是从栈顶出,那么全部打印的输出的时候,就需要从数组的尾输出。
Status Show_Stack(SeqStack s)
{
if(s.top == 0)
{
printf("栈已空\n");
return FALSE;
}
for(int i = s.top-1; i >= 0; i--)
{
printf("%d",s.bace[i]);
}
printf("\n");
return TRUE;
}
顺序栈的操作的基本操作就总结到这里,我们接着看栈的另一种存储结构——链栈。
栈之链栈
链栈也是栈,所以就不在介绍它的ADT,我们直接看链栈的结构。顺序栈我们类比顺序表,那么链栈我们类比链表,链表的种类那么多,我们选用那种呢?看栈的定义,我们不难得出是单链表,至于是带头结点还是不带头结点,由于栈操作是从栈顶操作也就是线性表的表尾,所以这里也不用考虑带头结点或者不带头结点,都一样,也就不需要用带头结点了。
之前说顺序栈的时候我们谈到,栈会满,我们采用了一种结构处理这种情况,为其增开辟空间,解决栈满的情况。那么对于链栈,只要内存不满,就可以一直压栈存储元素。(系统内存耗尽除外,当发生这种情况时,系统已经瘫痪,所以程序的崩溃也已经无所谓了。),所以也不需要顺序栈中判断栈是否为满的情况这个函数。
ok我们继续先看一下链栈的结构和结构定义:
栈的结构
#define ElemType int
#define TRUE 1
#define FALSE 0
#define Status int
typedef struct StackNode
{
ElemType data;
struct StackNode *next;
}StackNode;
typedef StackNode* LinkStack; // 这里需要注意后边LinkStack 定义的变量就是指针类型的。
Status InitLinkStack(LinkStack *ls)
{
*ls = NULL;
return TRUE;
}
链栈的压栈出栈
顺序栈时已经说过,压栈出栈对于栈是最重要的结构,那么其他操作类比一下不带头结点单链表的操作,OK,压栈就是对不带头结点的头插,头插!对就是头插,不再是顺序表中说的尾插,没有搞错,我们退回去看链栈的结构图,当插入元素时,指向栈顶的指针指向新的元素,那么当通过指向栈顶的指针访问链表的时候,不就是后进先出,不就是符合栈的定义吗?其实顺序表也一定意义上头插,我们通过栈顶看,不就是头插吗?说顺序栈是尾插,是由于顺序栈是通过数组实现的,数组名是指向数组的第一个元素的,我们要通过数组名操作存储数据,所以才说是尾插。我们继续看结构图:
结构弄清了链栈的压栈只是一个没有不带头结点的头插;ok我们看具体C语言代码实现:
压栈
//压栈,压栈成功返回TRUE,失败返回FALSE;
Status PushStack(LinkStack *ls,ElemType x)
{
StackNode *s = (StackNode *)malloc(sizeof(StackNode));
if(NULL == s)
{
printf("out of memory\n");
return FALSE;
}
s->data = x;
if(NULL == *ls)
{
*ls = s;
s->next = NULL;
}
else
{
s->next = *ls;
*ls = s;
}
return TRUE;
}
出栈
对于链栈的出栈要注意释放结点空间,防止内存泄露
//出栈,出栈成功返回TRUE,失败返回FALSE
Status PopLinkStack(LinkStack *ls)
{
StackNode *p = *ls;
if(NULL == p)
{
printf("栈已空,出栈失败\n");
return FALSE;
}
*ls = p->next;
free(p);
p = NULL;
return TRUE;
}
链栈的清空
这里由于不带头结点,所以这里只给出了清空链栈的操作,但是,需要强调意义不一样。
//清空链表,清空成功返回TRUE,失败返回FALSE
Status ClearLinkStack(LinkStack *ls)
{
StackNode *p = *ls;
while(NULL != p)
{
*ls = p->next;
free(p);
p = *ls;
}
*ls = NULL;
return TRUE;
}
链栈的获取栈顶元素
//获取栈顶元素,即就是栈不空的条件下,获取栈的首元素。
Status GetTop(LinkStack *ls,ElemType *value)
{
StackNode *p = *ls;
if(NULL == p)
{
printf("栈已空,获取栈顶元素失败\n");
return FALSE;
}
*value = p->data;
return TRUE;
}
链栈的获取栈的长度
链栈不像顺序栈,通过top可以直接获得栈中元素个数,需要遍历所以元素统计栈的元素个数。
//获取链表长度
int GetLength(LinkStack *ls)
{
StackNode *p = *ls;
int length = 0;
while(NULL != p)
{
length++;
p = p->next;
}
return p;
}
链栈的输出
Status Show_LinkStack(LinkStack *s)
{
StackNode *p = *s;
if(NULL == s)
{
printf("栈已空\n");
return FALSE;
}
while(NULL != p->next)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
ok栈的基本操作就总结到这里,写道这里线性表,栈的基本操作我们都讲完了,会有人说,堆,线性表就只能进行这些基本操作吗?那岂不是很没有用,下一篇我将对线性表的应用简单总结一下。
分享文章:数据结构之栈和队列(C语言版)
文章链接:http://ybzwz.com/article/pogogo.html