顺序栈的实现

简介: 顺序栈的实现

一.准备知识

   顺序栈是数据结构栈的一个分类,顺序栈也是一种受限的线性表,我们说这个受限是指它受到了某种限制,这个限制是什么呢?

  先来看一下顺序栈的示意图:

a1,a2…an依次进入这个容器,出来的时候是an先出来,接着…a2,a1.我们把这种进入出入的方式成为“先进后出”。造成这种方式的原因是这个容器只有一个开口,栈底是不能出入的,只能在栈顶那端进行操作,这就是我们说的受限。

二.顺序栈结构的打造

前期文章《顺序表》我们谈到顺序表的存储结构时用的是数组存取元素值,当前顺序栈也是同样的道理,具体看前期文章。

用结构体打造顺序栈:

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef struct Stack
{
  int data[MAXSIZE];//栈空间
  int top;//栈顶指针
}SeqStack;

这时候我们打造了如下的栈结构:

三.功能函数的声明与写法

void Init_SeqStack(SeqStack *s);//初始化
int Empty_SeqStack(SeqStack *s);//判空
int Push_SeqStack(SeqStack *s, int x);//入栈
void PrintStack(SeqStack *s);//打印栈元素
int Pop_SeqStack(SeqStack *s, int *x);//出栈
int Gettop_SeqStack(SeqStack *s, int *x);//获取栈顶元素

函数接口我们不用再具体分析了。

第一步初始化

void Init_SeqStack(SeqStack *s)
{
   s->top = -1;//置空操作
}

在这里我们需要知道:

  栈空:top=-1

  栈满:top=MAXSIZE-1

这里是怎么来的呢?观察如下示意图:

0以下为-1,MAXSIZE以下为满。

第二步判空

int Empty_SeqStack(SeqStack *s)
{
  if (s->top == -1)
    return 1;
  else
    return 0;
}

第三步入栈

int Push_SeqStack(SeqStack *s, int m)
{
  if (s->top == MAXSIZE - 1)
    return 0;//栈满不能入栈
  else
  {
    s->top++;
    s->data[s->top] = m;
  }
  return 1;
}

第四步顺序栈元素值的打印

void PrintStack(SeqStack *s)
{
  int i;
  if (Empty_SeqStack(s) == 1)
  {
    printf("顺序栈为空!");
    exit(1);
  }
  else
    for (i = s->top; i >= 0; i--)
      printf("%4d", s->data[i]);
}

第五步顺序栈的出栈

int Pop_SeqStack(SeqStack *s, int *x)
{
  if (Empty_SeqStack(s) == 1)
    return 0;//栈空,不能出栈
  else
  {
    *x = s->data[s->top];//将栈顶元素放入变量x中
    s->top--;
  }
  return 1;
}

第六步栈顶元素的读取

int Gettop_SeqStack(SeqStack *s, int *x)
{
  if (Empty_SeqStack(s) == 1)
    return 0;//栈空
  else
  {
    *x = s->data[s->top];
  }
  return 1;
}

四.完成主函数

int main()
{
  SeqStack s;
  int x;//出栈的时候读取到的值
  int data[MAXSIZE];//这一个数组的定义主要是为了使用PrintStack函数的时候使用的
  int n, m, i;
  Init_SeqStack(&s);
  Empty_SeqStack(&s);
  printf("请输入元素个数?\n");
  scanf("%d", &n);
  printf("请输入入栈的%d个元素的值:\n\n", n);
  for (i = 0; i < n; i++)
  {
    scanf("%d", &m);
    Push_SeqStack(&s, m);
  }
  
  printf("出栈的元素为:\n");
  for (i = 0; i < n; i++)
  {
    Pop_SeqStack(&s,&x);
    printf("%4d",x);
  }
  /*
  其实输出栈的函数你可以选择使用PrintStack函数,这里我选择了使用出栈的函数Pop_SeqStack。
  */
  Gettop_SeqStack(&s,&x);
  printf("\n此时的栈顶元素读取到为%d\n", x);
  //PrintStack(&s);
  return 0;
}

心得体会:

  1. 通过函数接口分析和算法分析自己完成主函数,这是一项很重要的能力。
  2. 入栈出栈的调用操作,我们通常在主函数里面用循环完成,循环调用。
  3. 观察函数接口用到的指针变量,我们在主函数里需要进行定义,定义好了梳理函数调用的先后次序,最后开始写代码。

五.全部代码演示

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef struct Stack
{
  int data[MAXSIZE];//栈空间
  int top;//栈顶指针
}SeqStack;
/*==========================
函数声明
===========================*/
void Init_SeqStack(SeqStack *s);
int Empty_SeqStack(SeqStack *s);
int Push_SeqStack(SeqStack *s, int x);
void PrintStack(SeqStack *s);
int Pop_SeqStack(SeqStack *s, int *x);
int Gettop_SeqStack(SeqStack *s, int *x);
int main()
{
  SeqStack s;
  int x;//出栈的时候读取到的值
  int data[MAXSIZE];//这一个数组的定义主要是为了使用PrintStack函数的时候使用的
  int n, m, i;
  Init_SeqStack(&s);
  Empty_SeqStack(&s);
  printf("请输入元素个数?\n");
  scanf("%d", &n);
  printf("请输入入栈的%d个元素的值:\n\n", n);
  for (i = 0; i < n; i++)
  {
    scanf("%d", &m);
    Push_SeqStack(&s, m);
  }
  
  printf("出栈的元素为:\n");
  for (i = 0; i < n; i++)
  {
    Pop_SeqStack(&s,&x);
    printf("%4d",x);
  }
  /*
  其实输出栈的函数你可以选择使用PrintStack函数,这里我选择了使用出栈的函数Pop_SeqStack。
  */
  Gettop_SeqStack(&s,&x);
  printf("\n此时的栈顶元素读取到为%d\n", x);
  //PrintStack(&s);
  return 0;
}
/*=============================
函数功能:顺序栈的初始化
==============================*/
void Init_SeqStack(SeqStack *s)
{
  s->top = -1;
}
/*=============================
函数功能:顺序栈的判空
==============================*/
int Empty_SeqStack(SeqStack *s)
{
  if (s->top == -1)
    return 1;
  else
    return 0;
}
/*=============================
函数功能:顺序栈的入栈
==============================*/
int Push_SeqStack(SeqStack *s, int m)
{
  if (s->top == MAXSIZE - 1)
    return 0;//栈满不能入栈
  else
  {
    s->top++;
    s->data[s->top] = m;
  }
  return 1;
}
/*=============================
函数功能:顺序栈的输出
==============================*/
void PrintStack(SeqStack *s)
{
  int i;
  if (Empty_SeqStack(s) == 1)
  {
    printf("顺序栈为空!");
    exit(1);
  }
  else
    for (i = s->top; i >= 0; i--)
      printf("%4d", s->data[i]);
}
/*=============================
函数功能:顺序栈的出栈
==============================*/
int Pop_SeqStack(SeqStack *s, int *x)
{
  if (Empty_SeqStack(s) == 1)
    return 0;//栈空,不能出栈
  else
  {
    *x = s->data[s->top];//将栈顶元素放入变量x中
    s->top--;
  }
  return 1;
}
/*=============================
函数功能:顺序栈的栈顶元素的读取
==============================*/
int Gettop_SeqStack(SeqStack *s, int *x)
{
  if (Empty_SeqStack(s) == 1)
    return 0;//栈空
  else
  {
    *x = s->data[s->top];
  }
  return 1;
}

六.运行结果

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

热门文章

最新文章