做外贸阿里巴巴有哪些网站,做英语在线翻译兼职网站,wordpress站点标题图片,简繁英3合1企业网站生成管理系统目录 一、概念
1、栈的定义
2、栈顶
3、栈底 二、接口
1、可写接口
1#xff09;数据入栈
2#xff09;数据出栈
3#xff09;清空栈
2、只读接口
1#xff09;获取栈顶数据
2#xff09;获取栈元素个数
3#xff09;栈的判空
三、栈的基本运算
四、顺序栈数据入栈
2数据出栈
3清空栈
2、只读接口
1获取栈顶数据
2获取栈元素个数
3栈的判空
三、栈的基本运算
四、顺序栈Sequential Stack实现
1、数据结构定义
2、创建栈
3、清空栈
4、判断栈是否为空
5、判断栈是否饱和
6、入栈
7、出栈
8、取栈顶元素
9、释放malloc申请的内存
打印栈中所有元素示例
五、栈的链表实现
1、数据结构定义
2、创建栈
3、清空栈
4、判断栈是否为空
5、入栈
6、出栈
7、取栈顶元素
8、释放malloc申请的内存
打印栈中所有元素示例
六、两种实现的优缺点
1、顺序表实现
2、链表实现 一、概念
1、栈的定义 栈 是仅限在 表尾 进行 插入 和 删除 的 线性表。 栈 又被称为 后进先出 Last In First Out 的线性表简称 LIFO 。
2、栈顶 栈 是一个线性表我们把允许 插入 和 删除 的一端称为 栈顶。
3、栈底 和 栈顶 相对另一端称为 栈底实际上栈底的元素我们不需要关心。 二、接口
1、可写接口
1数据入栈 栈的插入操作叫做 入栈也可称为 进栈、压栈。如下图所示代表了三次入栈操作
2数据出栈 栈的删除操作叫做 出栈也可称为 弹栈。如下图所示代表了两次出栈操作
3清空栈 一直 出栈直到栈为空如下图所示
2、只读接口
1获取栈顶数据 对于一个栈来说只能获取 栈顶 数据一般不支持获取 其它数据。
2获取栈元素个数 栈元素个数一般用一个额外变量存储入栈 时加一出栈 时减一。这样获取栈元素的时候就不需要遍历整个栈。通过 (1)O(1) 的时间复杂度获取栈元素个数。
3栈的判空 当栈元素个数为零时就是一个空栈空栈不允许 出栈 操作。
三、栈的基本运算
创建空栈 : CreateStack (len)
清空栈 : ClearStack (S)
判断是否栈空 : EmptyStack (S)
判断是否栈满 : FullStack (S)
元素进栈 : PushStack (S,x)
元素出栈 : PopStack (S)
取栈顶元素 : GetTop (S)
四、顺序栈Sequential Stack实现
1、数据结构定义 对于顺序表在 C语言 中表现为 数组在进行 栈的定义 之前我们需要考虑以下几个点 1栈数据的存储方式以及栈数据的数据类型 2栈的大小 3栈顶指针 我们可以定义一个 栈 的 结构体C语言实现如下所示
typedef int datatype;
typedef struct node{ /*定义栈中数据元素的数据类型*/datatype *data; /*用指针指向栈的存储空间*/int maxlen; /*当前栈的最大元素个数*/int top; /*指示栈顶位置(数组下标)的变量*/
}sqstack; /*顺序栈类型定义*/
2、创建栈
C语言实现如下所示
sqstack* stack_create(int len)
{sqstack *s;if((s(sqstack *)malloc(sizeof(sqstack)))NULL){puts(malloc failed);return NULL;}if((s-data(datatype *)malloc(len*sizeof(datatype)))NULL){puts(malloc failed);return NULL;}s-maxlenlen;s-top-1;return s;
}
3、清空栈
C语言实现如下所示
void stack_clear(sqstack* s)
{s-top -1;
}
4、判断栈是否为空
C语言实现如下所示
int stack_empty(sqstack* s)
{return (s-top-1 ? 1:0);
}
5、判断栈是否饱和
C语言实现如下所示
int stack_full(sqstack* s)
{return (s-top(s-maxlen-1) ? 1:0);
}
6、入栈
C语言实现如下所示
int stack_push(sqstack* s,datatype value)
{if(s-tops-maxlen-1){puts(stack is full);return -1;}s-data[s-top1]value;s-top;return 1;
}
7、出栈
C语言实现如下所示
datatype stack_pop(sqstack* s)
{s-top--;return s-data[s-top1];
}
8、取栈顶元素
C语言实现如下所示
datatype stack_top(sqstack* s)
{return(s-data[s-top]);
}
9、释放malloc申请的内存
C语言实现如下所示
void stack_free(sqstack *s)
{free(s-data);s-dataNULL;free(s);sNULL;
}
打印栈中所有元素示例
C语言实现如下所示
sqstack.h
#ifndef __LINKLIST_H__
#define __LINKLIST_H__#include stdio.h
#include stdlib.h
typedef int datatype;typedef struct node{datatype *data;int maxlen;int top;
}sqstack;extern sqstack* stack_create(int len);
extern int stack_empty(sqstack* s);
extern int stack_full(sqstack* s);
extern void stack_clear(sqstack* s);
extern int stack_push(sqstack* s,datatype value);
extern datatype stack_pop(sqstack* s);
extern datatype stack_top(sqstack* s);
extern void stack_free(sqstack *s);#endifsqstack.c
#include sqstack.hsqstack* stack_create(int len)
{sqstack *s;if((s(sqstack *)malloc(sizeof(sqstack)))NULL){puts(malloc failed);return NULL;}if((s-data(datatype *)malloc(len*sizeof(datatype)))NULL){puts(malloc failed);return NULL;}s-maxlenlen;s-top-1;return s;
}int stack_empty(sqstack* s)
{return (s-top-1 ? 1:0);
}
int stack_full(sqstack* s)
{return (s-top(s-maxlen-1) ? 1:0);
}
void stack_clear(sqstack* s)
{s-top -1;
}
int stack_push(sqstack* s,datatype value)
{if(s-tops-maxlen-1){puts(stack is full);return -1;}s-data[s-top1]value;s-top;return 1;
}
datatype stack_pop(sqstack* s)
{s-top--;return s-data[s-top1];
}
datatype stack_top(sqstack* s)
{return(s-data[s-top]);
}
void stack_free(sqstack *s)
{free(s-data);s-dataNULL;free(s);sNULL;
}test.c
#include sqstack.hint main(int argc, const char *argv[])
{sqstack *s;int n5;sstack_create(n);stack_push(s,10);stack_push(s,20);stack_push(s,30);stack_push(s,40);stack_push(s,50);stack_push(s,60);while(!stack_empty(s)){printf(%d ,stack_pop(s));}putchar(10);stack_clear(s);stack_free(s);return 0;
}Makefile
CC gcc
CFLAGS -g -Walltest:test.o sqstack.o$(CC) $(CFLAGS) -o $ $^.PHONY:clean
clean:rm test *.o-g : 产生符号调试工具(GNU的gdb)所必要的符号资讯要想对源代码进行调试我们就必须加入这个选项
-Wall : 表示允许发出gcc所有有用的报警信息
-c : 只是编译不链接,生成目标文件.o
-o test : 表示把输出文件输出到file里
运行结果 五、栈的链表实现
1、数据结构定义 对于链表在进行 栈的定义 之前我们需要考虑以下几个点 1栈数据的存储方式以及栈数据的数据类型 2栈的大小 3栈顶指针 我们可以定义一个 栈 的 结构体C语言实现如下所示
typedef int datatype;typedef struct node{datatype data;struct node* next;
}listnode,*linklist;
2、创建栈
C语言实现如下所示
linklist stack_create()
{linklist s;if((s(linklist)malloc(sizeof(listnode)))NULL){puts(malloc failed);return NULL;}s-nextNULL;return s;
}
3、清空栈
C语言实现如下所示
void stack_clear(linklist s)
{linklist p;printf(clear:);ps-next;while(p){s-nextp-next;printf(%d ,p-data);free(p);ps-next;}putchar(10);
}
4、判断栈是否为空
C语言实现如下所示
int stack_empty(linklist s)
{return (s-nextNULL ? 1:0);
}
5、入栈
C语言实现如下所示
int stack_push(linklist s,datatype value)
{linklist p;if((p(linklist)malloc(sizeof(listnode)))NULL){puts(malloc failed);return -1;}p-data value;p-nexts-next;s-next p;return 0;
}
6、出栈
C语言实现如下所示
datatype stack_pop(linklist s)
{linklist p;datatype ret;ps-next;s-nextp-next;retp-data;free(p);pNULL;return ret;
}
7、取栈顶元素
C语言实现如下所示
datatype stack_top(linklist s)
{return (s-next-data);
}
8、释放malloc申请的内存
C语言实现如下所示
void stack_free(linklist s)
{linklist p;printf(free:);ps;while(p){ss-next;printf(%d ,p-data);free(p);ps;}putchar(10);}
打印栈中所有元素示例
C语言实现如下所示
linkstack.h
#ifndef __LINKLIST_H__
#define __LINKLIST_H__#include stdio.h
#include stdlib.h
typedef int datatype;typedef struct node{datatype data;struct node* next;
}listnode,*linklist;extern linklist stack_create();
extern int stack_empty(linklist s);
extern void stack_clear(linklist s);
extern int stack_push(linklist s,datatype value);
extern datatype stack_pop(linklist s);
extern datatype stack_top(linklist s);
extern void stack_free(linklist s);#endiflinkstack.c
#include linkstack.hlinklist stack_create()
{linklist s;if((s(linklist)malloc(sizeof(listnode)))NULL){puts(malloc failed);return NULL;}s-nextNULL;return s;
}
int stack_empty(linklist s)
{return (s-nextNULL ? 1:0);
}int stack_push(linklist s,datatype value)
{linklist p;if((p(linklist)malloc(sizeof(listnode)))NULL){puts(malloc failed);return -1;}p-data value;p-nexts-next;s-next p;return 0;
}datatype stack_pop(linklist s)
{linklist p;datatype ret;ps-next;s-nextp-next;retp-data;free(p);pNULL;return ret;
}datatype stack_top(linklist s)
{return (s-next-data);
}void stack_clear(linklist s)
{linklist p;printf(clear:);ps-next;while(p){s-nextp-next;printf(%d ,p-data);free(p);ps-next;}putchar(10);
}
void stack_free(linklist s)
{linklist p;printf(free:);ps;while(p){ss-next;printf(%d ,p-data);free(p);ps;}putchar(10);}test.c
#include linkstack.hint main(int argc, const char *argv[])
{linklist s;sstack_create();stack_push(s,10);stack_push(s,20);stack_push(s,30);stack_push(s,40);stack_push(s,50);stack_push(s,60);#if 0while(!stack_empty(s)){printf(%d ,stack_pop(s));}putchar(10);
#endif
// stack_clear(s);stack_free(s);return 0;
}Makefile
CC gcc
CFLAGS -g -Walltest:test.o linkstack.o$(CC) $(CFLAGS) -o $ $^.PHONY:clean
clean:rm test *.o运行结果 六、两种实现的优缺点
1、顺序表实现 在利用顺序表实现栈时入栈 和 出栈 的常数时间复杂度低且 清空栈 操作相比 链表实现 能做到 O(1)唯一的不足之处是需要预先申请好空间而且当空间不够时需要进行扩容扩容方式本文未提及可以参考大佬文章《C/C 面试 100 例》四vector 扩容策略。
2、链表实现 在利用链表实现栈时入栈 和 出栈 的常数时间复杂度略高主要是每插入一个栈元素都需要申请空间每删除一个栈元素都需要释放空间且 清空栈 操作是 O(n) 的直接将 栈顶指针 置空会导致内存泄漏。好处就是不需要预先分配空间且在内存允许范围内可以一直 入栈没有顺序表的限制。
