数据结构——顺序栈与链式栈的实现
目录
一、概念
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->maxlen=len;
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->top==s->maxlen-1){
puts("stack is full");
return -1;
}
s->data[s->top+1]=value;
s->top++;
return 1;
}
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
linkstack.c
#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)?的,直接将?栈顶指针?置空会导致内存泄漏。好处就是:不需要预先分配空间,且在内存允许范围内,可以一直?入栈,没有顺序表的限制。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!