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

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

数据结构——顺序栈与链式栈的实现-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里


运行结果:


068a751f1a47c107c796f6d8ac49b62b_6118640bdb7b42afb3d5697b0620750d.png


五、栈的链表实现

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


相关文章
|
4天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
12 3
|
1天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
1天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
|
1天前
数据结构——栈和队列
数据结构——栈和队列
|
2天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
4天前
数据结构初阶 栈
数据结构初阶 栈
8 1
|
9天前
|
算法
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
11 0
|
9天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)二
14 2
|
9天前
|
算法 C语言
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)一
13 0
|
9天前
|
算法 C语言
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
数据结构和算法学习记录——特殊线性表之栈(下)-销毁栈函数、判断栈是否为空、压栈函数、出栈函数、取栈顶元素、计算栈中有多少个元素、栈有关习题-有效的括号
10 0