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


目录
打赏
0
2
3
0
46
分享
相关文章
|
4月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
64 1
|
2月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
159 77
|
8天前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
24 11
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
2月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
53 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
2月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
51 9
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
48 7
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
107 5
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
133 21
|
4月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
77 0