数据结构——顺序栈与链式栈的实现

目录

一、概念

1、栈的定义

2、栈顶

3、栈底

二、接口

1、可写接口

1）数据入栈

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->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) 的，直接将 栈顶指针 置空会导致内存泄漏。好处就是：不需要预先分配空间，且在内存允许范围内，可以一直 入栈，没有顺序表的限制。

代码007普通

打赏 收藏 海报 链接