`
nnwq
  • 浏览: 209103 次
社区版块
存档分类
最新评论

数据结构和算法系列3 栈

 
阅读更多

上一篇总结完了线性表之链表，这一篇文章我们要总结的是栈，我想从以下几个方面来进行总结。

1，什么是栈？
2，栈的存储结构？
3，栈的常见操作及代码实现？

1，什么是栈

首先栈是一种特殊的线性表。那它的特殊性表现在哪里呢？栈是限定在表的一端进行插入和删除运算的线性表，因此，栈也称为后进先出(LIFO)的线性表。

它有很多应用场景，比如食堂中的一叠盘子，我们只能从顶端一个一个地取。

2，栈的存储结构

ds13

实现代码：

/// <summary>
    /// 封装顺序栈
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class SeqStack<T>
    {
        //使用数组来存放结点
        public T[] data;

        //栈顶指针
        public int top = -1;

        public SeqStack(int length)
        { 
            data=new T[length];
        }
    }

3，栈的常见操作及实现代码

1，初始化

实现思路：用指定大小的length实例化一个SeqStack<T>，然后使top指针指向-1。

2，进栈

实现思路：将top指针加1，然后将新结点插入到top指针指向的位置。

3，出栈

实现思路：消灭top指向的结点，并使top指针减1。

4，获取栈顶元素

实现思路：与出栈相似，只是不改变栈的状态而已。

5，判断是否栈空

实现思路：如果top指针是否等于-1，如果是则返为空栈。

6，判断是否栈满

实现思路：检查top指针的值是否等于数组的长度，如果是则为栈满。

 

C#版代码：

namespace DS.Model
{
    /// <summary>
    /// 学生实体
    /// </summary>
    public class Student
    {
        public int ID { get; set; }
        public string Name { get; set; }
        public int Age { get; set; }
    }
}

namespace DS.BLL
{
    public class SeqStackBLL
    {
        /// <summary>
        /// 初始化
        /// </summary>
        /// <param name="length"></param>
        /// <returns></returns>
        public static SeqStack<T> Init<T>(int length)
        {
            SeqStack<T> seqStack = new SeqStack<T>(length);
            seqStack.top = -1;
            return seqStack;
        }

        /// <summary>
        /// 进栈
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="seqStack"></param>
        /// <param name="data"></param>
        public static void Push<T>(SeqStack<T> seqStack, T data)
        { 
            //检查是否栈满
            if (IsFull(seqStack)) return;
            seqStack.data[++seqStack.top] = data;
        }

        /// <summary>
        /// 出栈
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="seqStack"></param>
        public static T Pop<T>(SeqStack<T> seqStack)
        { 
            //检查是否栈空
            if (IsEmpty(seqStack)) return default(T);

            seqStack.data[seqStack.top]=default(T);
            return seqStack.data[--seqStack.top];
        }

        /// <summary>
        /// 获取栈顶元素
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="seqStack"></param>
        /// <returns></returns>
        public static T GetTop<T>(SeqStack<T> seqStack)
        {
            //检查是否栈空
            if (IsEmpty(seqStack)) return default(T);

            return seqStack.data[seqStack.top];
        }

        /// <summary>
        /// 获取栈中元素个数
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="seqStack"></param>
        /// <returns></returns>
        public static int GetLength<T>(SeqStack<T> seqStack)
        {
            return seqStack.top + 1;
        }

        /// <summary>
        /// 判断是否栈满
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="seqStack"></param>
        /// <returns></returns>
        private static bool IsFull<T>(SeqStack<T> seqStack)
        {
            return seqStack.top == seqStack.data.Length;
        }

        /// <summary>
        /// 判断是否栈空
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="seqStack"></param>
        /// <returns></returns>
        private static bool IsEmpty<T>(SeqStack<T> seqStack)
        {
            return seqStack.top == -1;
        }
    }

    /// <summary>
    /// 封装顺序栈
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class SeqStack<T>
    {
        //使用数组来存放结点
        public T[] data;

        //栈顶指针
        public int top = -1;

        public SeqStack(int length)
        { 
            data=new T[length];
        }
    }
}

namespace SeqStack.CSharp
{
    class Program
    {
        static void Main(string[] args)
        {
            SeqStack<Student> seqStack = null;
            Console.WriteLine("***********************初始化*****************************\n");
            seqStack = SeqStackBLL.Init<Student>(10);
            if (seqStack != null && seqStack.data.Length > 0) Console.WriteLine("初始化成功\n");
            else Console.WriteLine("初始化失败\n");
            Console.WriteLine("当前栈中有{0}个元素", SeqStackBLL.GetLength(seqStack));

            Console.WriteLine("\n***********************进栈*****************************\n");
            Console.WriteLine("压入3条数据\n");
            SeqStackBLL.Push<Student>(seqStack, new Student { ID = 1, Name = "a", Age = 10 });
            SeqStackBLL.Push<Student>(seqStack, new Student { ID = 2, Name = "b", Age = 11 });
            SeqStackBLL.Push<Student>(seqStack, new Student { ID = 3, Name = "c", Age = 12 });
            Display(seqStack);

            Console.WriteLine("\n***********************出栈*****************************\n");
            Console.WriteLine("弹出栈顶元素\n");
            Student student= SeqStackBLL.Pop<Student>(seqStack);
            Console.WriteLine("当前栈顶元素为：ID={0},Name={1},Age={2}",student.ID,student.Name,student.Age);

            Console.WriteLine("\n***********************获取栈顶元素*****************************\n");
            Student student1= SeqStackBLL.GetTop(seqStack);
            Console.WriteLine("当前栈顶元素为：ID={0},Name={1},Age={2}", student1.ID, student1.Name, student1.Age);

            Console.WriteLine("\n***********************获取栈中元素个数*****************************\n");
            Console.WriteLine("当前栈中有{0}个元素\n", SeqStackBLL.GetLength(seqStack));


            Console.ReadKey();
        }

        private static void Display(SeqStack<Student> seqStack)
        {
            Console.WriteLine("****展示数据****\n");
            for (int i = SeqStackBLL.GetLength(seqStack)-1; i>=0; i--)
            {
                Console.WriteLine("ID={0},Name={1},Age={2}",seqStack.data[i].ID,seqStack.data[i].Name,seqStack.data[i].Age);
            }
            Console.WriteLine("****展示完毕****\n");
        }
    }
}

程序运行结果：

ds15

 

C语言版：

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 10

typedef int Status; 
typedef int ElemType;

/* 顺序栈结构 */
typedef struct
{
    /*使用数组来存放结点*/
    ElemType data[MAXSIZE];

    /* 栈顶指针 */
    int top;
}SeqStack;


/*初始化*/
/************************************************************************/
/* 思路：使top指针指向-1                                                 */
/************************************************************************/
Status Init(SeqStack *seqStack)
{
    seqStack->top=-1;
    return OK;
}

/*进栈*/
/************************************************************************/
/*思路：top指针加1,然后将新结点从栈顶压入                                 */
/************************************************************************/
Status Push(SeqStack *seqStack,ElemType e)
{
    //检查是否栈满
    if (IsFull(seqStack)) return ERROR;

    seqStack->data[++seqStack->top]=e;
}

/*出栈*/
/************************************************************************/
/*思路：消灭top指向的结点，并使top指针减1                                 */
/************************************************************************/
Status Pop(SeqStack *seqStack,ElemType *e)
{
    //检查是否栈空
    if (IsEmpty(seqStack)) return ERROR;

    *e=seqStack->data[seqStack->top];
    seqStack->top--;
    return OK;
}

/*获取栈顶元素*/
/************************************************************************/
/*思路：用e返回top指针指向的元素的值                                      */
/************************************************************************/
Status GetTop(SeqStack *seqStack,ElemType *e)
{
    //检查是否栈空
    if (IsEmpty(seqStack)) return ERROR;
    
    *e=seqStack->data[seqStack->top];
}

/*获取栈中元素个数*/
/************************************************************************/
/*思路：取栈的长度即可                                                   */
/************************************************************************/
int GetLength(SeqStack *seqStack)
{
    return seqStack->top+1;
}

/*判断是否栈空*/
Status IsEmpty(SeqStack *seqStack)
{
    return seqStack->top==-1;
}

/*判断是否栈满*/
Status IsFull(SeqStack *seqStack)
{
    return seqStack->top==MAXSIZE-1;
}

/*展示栈中数据*/
void Display(SeqStack *seqStack)
{
    int i;
    printf("**********开始展示数据**********\n");

    for (i=seqStack->top;i>=0;i--)
    {
        printf("%d ",seqStack->data[i]);
    }
    printf("\n**********展示结束**********\n");
}


void main()
{
    SeqStack seqStack;
    int j;
    ElemType e;

    printf("********************初始化********************\n");
    if (Init(&seqStack)) printf("初始化成功!\n");
    else printf("初始化失败!\n");

    printf("\n********************进栈********************\n");
    printf("依次插入10个元素\n");
    for (j=1;j<=10;j++)
    {
        Push(&seqStack,j);
    }
    Display(&seqStack);

    printf("\n********************出栈********************\n");
    printf("弹出栈顶元素\n");
    Pop(&seqStack,&e);
    printf("被弹出的栈顶元素是：%d\n",e);

    printf("\n****************获取栈顶元素****************\n");
    GetTop(&seqStack,&e);
    printf("当前栈顶元素是:%d\n",e);

    printf("\n****************获取栈中元素个数****************\n");
    printf("当前栈中共有%d个元素\n",GetLength(&seqStack));

    getchar();
}

程序运行结果：

ds14

1
顶
1
踩
分享到：
| 千位分隔符，万位分隔，那个更好！
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    数据结构与算法之美

    数组、链表、栈、队列、树、图、散列表和堆等都是常见的数据结构。每种数据结构有其特定的用途和优势，例如链表擅长在任意位置进行快速插入和删除操作，而数组则提供了随机访问的能力。掌握这些基本数据结构的知识，...

    数据结构和算法导学 数据结构和算法导学

    数据结构和算法是计算机科学的基础，对于理解和设计高效的软件系统至关重要。它们构成了计算机科学的核心，为编程、问题解决和系统优化提供了理论支持。本导学将深入探讨这两个关键概念，帮助初学者建立坚实的理论...

    Java数据结构和算法中文第二版

    根据提供的信息，“Java数据结构和算法中文第二版”这本书主要关注的是数据结构与算法的相关内容。下面将基于这些信息，详细介绍数据结构与算法的核心概念、重要性和应用领域，以及在Java编程环境中如何实现这些概念...

    数据结构与算法分析电子书合集

    除了这些经典之作，合集中可能还包括其他关于特定数据结构（如栈、队列、树、图）和算法（如递归、分治、贪心、回溯）的专业书籍。这些书籍将详细阐述每种数据结构的特性、操作以及适用场景，并探讨不同算法的效率和...

    数据结构和算法系列教程

    本系列教程涵盖了数据结构和算法的核心概念，旨在帮助学习者强化软件开发的内功心法。 首先，我们从01数据结构概述.ppt开始，它会介绍数据结构的基本概念，如数组、链表、栈、队列、树和图等。数据结构是存储和组织...

    数据结构和算法分析电子版

    标题“数据结构和算法分析电子版”所指向的知识点，首先是关于数据结构和算法分析这两个计算机科学的基础领域的探讨。数据结构主要涉及的是数据的组织、管理和存储方法，以便于更高效地访问和修改。它包括如数组、...

    数据结构与算法.pdf

    栈、队列、树、哈希表、排序算法和图等，都是数据结构中的重要组成部分，它们在程序设计中具有广泛的应用。 栈是一种线性数据结构，具有后进先出（LIFO）的特性，即最后进入栈的元素将最先被移除。它仅允许在一端...

    数据结构与算法教程

    第1章为绪论，介绍数据结构和算法的基础知识，包括数据结构的定义、算法的概念、算法的效率评估、时间复杂度和空间复杂度分析以及算法设计的基本策略。 第2章讲述线性表的基本概念、存储结构以及相关的操作算法，还...

    02 如何抓住重点，系统高效地学习数据结构与算法

    重点则包括要熟练掌握常用的数据结构（如数组、链表、栈、队列、树、图等）以及基础算法（如排序、搜索等），并且能够对这些概念进行深入理解，能够根据实际需要选择和使用恰当的算法和数据结构来解决问题。...

    数据结构与算法 课后习题答案

    根据给定文件的信息，我们可以深入探讨《数据结构与算法》一书中的关键知识点，该书由张铭、王腾蛟和赵海燕编著，并由高等教育出版社出版。本书旨在为学生提供对数据结构和算法的基本理解和实践应用能力，涵盖了从...

    C语言描述的数据结构与算法教程

    数据结构与算法是计算机科学的基础，C语言作为一门强大的编程语言，被广泛用于描述和实现这些概念。本教程旨在帮助初学者理解数据结构和算法，并通过C语言进行实践。同时，教程还涉及到机器学习的基本算法，使学习者...

    数据结构与算法-PPT课件

    数据结构与算法是计算机科学中的核心课程，它探讨如何有效地组织和处理数据，以及如何设计和分析解决问题的算法。这份“数据结构与算法-PPT课件”提供了丰富的学习材料，涵盖了多个关键主题。 首先，我们要了解数据...

    数据结构和算法Flash动画演示

    本资源包含了一系列关于数据结构和算法的动态展示，通过视觉化的手段帮助我们深入理解它们的工作原理。 1. **数据结构**：数据结构是组织和存储数据的方式，以便于高效地访问和修改。常见的数据结构有数组、链表、...

    数据结构算法与应用电子书

    本电子书《数据结构算法与应用》以C++为语言工具，深入探讨了这一主题，对于学习者来说是一份宝贵的资源。 首先，我们来了解一下“数据结构”。数据结构是指在计算机中存储、组织数据的方式，它不仅包括数据的存储...

    数据结构与算法课件

    在这个“数据结构与算法课件”中，我们可以预见到一系列深入的理论讲解和实践应用。以下是对这些关键概念的详细解析： 1. **数据结构**：数据结构是组织、管理、存储和检索数据的方式。常见的数据结构包括数组、...

    哈工大数据结构与算法（第5版）课程PPT.rar

    数据结构与算法是计算机科学的基础，对于理解和解决复杂问题至关重要。哈工大的这门课程《数据结构与算法（第5版）》显然旨在深入探讨这些关键概念。PPT材料通常包含课程的核心要点、实例和练习，帮助学生系统地学习...

    数据结构经典算法实例

    在这个名为“数据结构经典算法实例”的压缩包中，我们找到了一系列用C语言实现的数据结构和算法的经典示例。通过这些源代码，我们可以深入理解数据结构和算法的工作原理，以及如何在实际编程中应用它们。 首先，...

    数据结构与算法资料

    它详细介绍了各种重要的数据结构和算法，如堆、平衡二叉树、图算法（如Dijkstra最短路径算法、Floyd-Warshall所有对最短路径算法）、字符串匹配算法等，并配有大量的实例和习题，帮助读者深入理解和掌握。...

    数据结构与算法（Java语言版）含有源码

    3. Java语言：作为面向对象的编程语言，Java提供了丰富的库和工具，使得数据结构和算法的实现更为便捷。例如，Java集合框架（java.util包）为实现各种数据结构提供了基础类，如List、Set和Map接口，以及其实现类。...

Magicbox
Global site tag (gtag.js) - Google Analytics