数据结构——顺序栈与链式栈的实现-1
https://developer.aliyun.com/article/1507980
7、出栈
C语言实现如下所示：
datatype stack_pop(sqstack* s) { s->top--; return s->data[s->top+1]; }
8、取栈顶元素
C语言实现如下所示：
datatype stack_top(sqstack* s) { return(s->data[s->top]); }
9、释放malloc申请的内存
C语言实现如下所示：
void stack_free(sqstack *s) { free(s->data); s->data=NULL; free(s); s=NULL; }
打印栈中所有元素示例
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); #endif
sqstack.c
#include "sqstack.h" 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->maxlen=len; 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->top==s->maxlen-1){ puts("stack is full"); return -1; } s->data[s->top+1]=value; s->top++; return 1; } datatype stack_pop(sqstack* s) { s->top--; return s->data[s->top+1]; } datatype stack_top(sqstack* s) { return(s->data[s->top]); } void stack_free(sqstack *s) { free(s->data); s->data=NULL; free(s); s=NULL; }
test.c
#include "sqstack.h" int main(int argc, const char *argv[]) { sqstack *s; int n=5; s=stack_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 -Wall test: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->next=NULL; return s; }
3、清空栈
C语言实现如下所示：
void stack_clear(linklist s) { linklist p; printf("clear:"); p=s->next; while(p) { s->next=p->next; printf("%d ",p->data); free(p); p=s->next; } putchar(10); }
4、判断栈是否为空
C语言实现如下所示：
int stack_empty(linklist s) { return (s->next==NULL ? 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->next=s->next; s->next = p; return 0; }
6、出栈
C语言实现如下所示：
datatype stack_pop(linklist s) { linklist p; datatype ret; p=s->next; s->next=p->next; ret=p->data; free(p); p=NULL; 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:"); p=s; while(p) { s=s->next; printf("%d ",p->data); free(p); p=s; } 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); #endif
#include "linkstack.h" linklist stack_create() { linklist s; if((s=(linklist)malloc(sizeof(listnode)))==NULL){ puts("malloc failed"); return NULL; } s->next=NULL; return s; } int stack_empty(linklist s) { return (s->next==NULL ? 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->next=s->next; s->next = p; return 0; } datatype stack_pop(linklist s) { linklist p; datatype ret; p=s->next; s->next=p->next; ret=p->data; free(p); p=NULL; return ret; } datatype stack_top(linklist s) { return (s->next->data); } void stack_clear(linklist s) { linklist p; printf("clear:"); p=s->next; while(p) { s->next=p->next; printf("%d ",p->data); free(p); p=s->next; } putchar(10); } void stack_free(linklist s) { linklist p; printf("free:"); p=s; while(p) { s=s->next; printf("%d ",p->data); free(p); p=s; } putchar(10); }
test.c
#include "linkstack.h" int main(int argc, const char *argv[]) { linklist s; s=stack_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 0 while(!stack_empty(s)) { printf("%d ",stack_pop(s)); } putchar(10); #endif // stack_clear(s); stack_free(s); return 0; }
Makefile
CC = gcc CFLAGS = -g -Wall test:test.o linkstack.o $(CC) $(CFLAGS) -o $@ $^ .PHONY:clean clean: rm test *.o
六、两种实现的优缺点
1、顺序表实现
在利用顺序表实现栈时，入栈 和 出栈 的常数时间复杂度低，且 清空栈 操作相比 链表实现 能做到 O(1)，唯一的不足之处是：需要预先申请好空间，而且当空间不够时，需要进行扩容，扩容方式本文未提及，可以参考大佬文章：《C/C++ 面试 100 例》（四）vector 扩容策略。
2、链表实现
在利用链表实现栈时，入栈 和 出栈 的常数时间复杂度略高，主要是每插入一个栈元素都需要申请空间，每删除一个栈元素都需要释放空间，且 清空栈 操作是 O(n) 的，直接将 栈顶指针 置空会导致内存泄漏。好处就是：不需要预先分配空间，且在内存允许范围内，可以一直 入栈，没有顺序表的限制。
