凡科网站建设公司,厦门湖里区建设局网站,推广小程序,2017两学一做竞赛网站还是先把这张图贴出来#xff0c;以便对比和理解 栈是限制在一段进行插入操作和删除操作的线性表#xff08;俗称堆栈#xff09;#xff0c;允许进行操作的一端称为“栈顶”#xff0c;另一固定端称为“栈底”#xff0c;当栈中没有元素称为“空栈”。特点#xff1a;先… 还是先把这张图贴出来以便对比和理解 栈是限制在一段进行插入操作和删除操作的线性表俗称堆栈允许进行操作的一端称为“栈顶”另一固定端称为“栈底”当栈中没有元素称为“空栈”。特点先进后出FILO。 栈顶即top这里top有两种定义方式 1、满栈Full Stack,top指向最后一个使用的空间 2、空栈Empty Stacktop指向下一个可用的空间 栈也是线性表所以也分顺序存储和链式存储 一、顺序存储 栈是顺序表的一种具有顺序表同样的存储结构由数组定义配合用数组下表表示的栈顶指针top(相对指针)完成各种操作。 [cpp] view plaincopy typedef int data_t; //定义栈中数据元素的数据类型 typedef struct { date_t *data; //用指针指向栈的存储空间 int maxlen; //当前栈的最大元素个数 int top; //指向栈顶位置数组下标的变量 }seqstack_t; //顺序栈类型定义 如图我们可以看到栈的顺序存储与顺序表的区别顺序表数组大小是固定的这样限制了我们的后期修改而栈的顺序存储将数据域单独开辟了一片空间才存放大小为maxlen*sizeof(data_t), 下面是栈的基本运算 1、创建栈 [cpp] view plaincopy seqstack_t *CreateEmptyStack(int max_len) { seqstack_t *stack; stack (seqstack_t *)malloc(sizeof(seqstack_t)); stack-data (data_t *)malloc(sizeof(data_t)*max_len); stack-top -1; stack-max_len max_len; return stack; } 2、摧毁一个栈 [cpp] view plaincopy void DestroyStack(seqstack_t *stack) { if(stack ! NULL) { if(stack-data ! NULL) free(stack-data); free(stack); } } 3、清空一个栈 [cpp] view plaincopy void ClearStack(seqstack_t *stack) { if(stack ! NULL) stack-top -1; } 4、判断栈是否为空 [cpp] view plaincopy int EmptyStack(seqstack_t *stack) { if(stack NULL) return -1; return(stack-top -1 ? 1 : 0); } 5、判断栈是否为满 [cpp] view plaincopy int FullStack(seqstack_t *stack) { if(stack NULL) return -1; return(stack-top (stack-max_len - 1) ? 1 : 0); } 6、进栈 [cpp] view plaincopy int PushStack(seqstack_t *stack ,data_t x) { if(FullStack(stack)) return -1; else { stack-top; stack-data[stack-top] x; } return 0; } 7、出栈 [cpp] view plaincopy int PopStack(seqstack_t *stack,data_t *x) { if(EmptySqstack(stack)) return -1; else { *x stack-data[stack-top]; stack-top--; } return 0; } 8、取栈顶元素 [cpp] view plaincopy int GetTop(seqstack_t *stack,data_t *x) { if(EmptyStack(stack)) return -1; else *x stack-data[stack-top]; return 0; } 二、链式存储 若是栈中元素的数目变化范围较大或不清楚栈元素的数目就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作链栈。链栈通常用一个无头结点的单链表表示。如图所示 插入操作和删除操作均在链表头部进行链表尾部就是栈底栈顶指针就是头指针 [cpp] view plaincopy typedef int data_t; typedef struct node_t { data_t data; //数据域 struct node_t *next; //链接指针域 }linkstack_t; //链栈类型定义 栈链式存储基本运算如下 1、创建空栈 [cpp] view plaincopy linkstack_t *CreateLinkstack() { linkstack_t *top; top (linkstack_t *)malloc(sizeof(linkstack_t)); top-next NULL; return top; } 2、判断是否为空栈 [cpp] view plaincopy int EmptyStack(linkstack_t *top) { return (top-next NULL ? 1 : 0); } 3、入栈 [cpp] view plaincopy void PushStack(linkstack_t *top,data_t x) { linkstack_t *p; p (linkstack_t *)malloc(sizeof(linkstack_t)); p-data x; p-next top-next; top-next p; return; } 4、出栈 [cpp] view plaincopy int PopStack(linkstack_t stack,data_t *x) { if(stack-next NULL || stack NULL) return -1; linkstack_t p; p stack-next; stack-next p-next; if(x ! NULL) *x p-data; free(p); return 0; }
