【 C 】经典抽象数据类型（ADT）之堆栈（用静态数组实现堆栈）

堆栈简介

堆栈（stack）最鲜明的特点就是后进先出（Last-In First-Out，LIFO）的数据进出方式。

基本的堆栈操作通常被称为 push 和 pop。push就是将一个新值压入到堆栈的顶部， pop就是把堆栈顶部的值移出堆栈并返回这个值。堆栈只提供对它的顶部值的访问。

传统的堆栈接口中，访问顶部元素的唯一方法就是把它移除。另一类堆栈接口提供三种基本的操作：push，pop，top。push和前面所说的一样，把一个新值压入堆栈的顶部，pop有点不一样的是只把顶部元素从堆栈中移除，并不返回这个值。top返回顶部元素的值，但它并不把顶部元素从堆栈中移除。下面统统采用这种方式！

我们需要两个额外的函数来使用堆栈。一个空堆栈不能执行pop操作，所以我们需要一个函数告诉我们堆栈是否为空。在实现堆栈时，如果存在最大长度限制，那么我们也需要另一个函数告诉我们堆栈是否已满。

这里提前说一下，这两个函数一个是判断堆栈是否已空的函数（is_empty），如果堆栈为空，返回TRUE，否则返回FALSE；另一个是判断堆栈是否已满的函数（is_full），如果已满，返回TRUE，否则返回FALSE。

在真正的堆栈实现中，这两个函数需要配合assert宏使用，后面你就将看到，关于assert宏的基础知识，见博文：【 C 】assert.h 简明介绍

如果不了解什么是宏，可以参考博文：【 C 】宏 简记

堆栈接口

什么是堆栈接口，实际上就是一个头文件，声明了堆栈的一些操作，包含堆栈需要使用的函数的一些原型！

堆栈是最容易实现的ADT之一。它的基本方法是当值被push到堆栈时把它们存储于数组中连续的位置上。你必须记住最近一个被push的值的下标。如果需要执行pop操作，你只需要简单地减少这个下标值就好了。

下面的头文件描述了一个堆栈模块的非传统接口：

  

   

    

     

    
    

     

      //一个堆栈模块的接口
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define STACK_TYPE int //堆栈所存储值的类型
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //push
     
    
   

    

     

    
    

     

      //把一个新值压入到堆栈中，它的参数是需要被压入的值。
     
    
   

    

     

    
    

     

      void push( STACK_TYPE value );
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //pop
     
    
   

    

     

    
    

     

      //从堆栈弹出一个值，并将其丢弃
     
    
   

    

     

    
    

     

      void pop( void );
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      // is_empty
     
    
   

    

     

    
    

     

      // 如果堆栈为空，返回TRUE，否则返回FALSE
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int is_empty( void );
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      // is_full
     
    
   

    

     

    
    

     

      // 如果堆栈已满，返回TRUE，否则返回FALSE
     
    
   

    

     

    
    

     

      int is_full( void );
     
    
  
 

保存为：stack.h

注意堆栈接口只包含了用户使用堆栈所需要的信息，特别是它并没有展示堆栈的实现方式。事实上，对这个头文件稍作修改，它可以用于三种实现方式。用这种方式定义接口是一种好方法，因为它防止用户以为它依赖于某种特定的实现方式。

具体实现方式后面会一一道来。

这个接口的一个有趣的特征就是存储于堆栈中的值的类型的声明方式。在编译这个堆栈模块之前，用户可以修改这个类型以适合自己的需要。例如上面声明为：#define STACK_TYPE int     //堆栈所存储值的类型

实现堆栈

用静态数组实现堆栈

  

   

    

     

    
    

     

      //用静态数组实现堆栈，数组的长度只能通过修改#define定义
     
    
   

    

     

    
    

     

      //并对模块重新编译来实现
     
    
   

    

     

    
    

     

      #include <assert.h>
     
    
   

    

     

    
    

     

      #include "stack.h"
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #define STACK_SIZE 100 //堆栈中值数量的最大限制
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //定义堆栈数组和栈顶下标
     
    
   

    

     

    
    

     

      static STACK_TYPE stack[STACK_SIZE];
     
    
   

    

     

    
    

     

      static int top_element = -1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //push
     
    
   

    

     

    
    

     

      void push( STACK_TYPE value )
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       assert( !is_full() ); //判断堆栈是否已经满了，未满则继续执行，否则退出
     
    
   

    

     

    
    

     

       top_element += 1;
     
    
   

    

     

    
    

     
 stack[ top_element ] = value;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //pop
     
    
   

    

     

    
    

     

      void pop( void )
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       assert( !is_empty() ); //判断堆栈是否是空的，如果不是，则继续执行，否则退出
     
    
   

    

     

    
    

     

       top_element -= 1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //top
     
    
   

    

     

    
    

     

      STACK_TYPE top( void )
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       assert( !is_empty() ); //堆栈未空，则继续
     
    
   

    

     

    
    

     
 return stack[ top_element ]; 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //is_empty
     
    
   

    

     

    
    

     

      int is_empty( void )
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return top_element == -1; //堆栈为空，则返回TRUE，否则返回FALSE
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //is_full
     
    
   

    

     

    
    

     

      int is_full( void )
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 return top_element == STACK_SIZE - 1; //堆栈已满，返回TRUE，否则返回FALSE
     
    
   

    

     

    
    

     

      }
     
    
  
 

变量top_element保持堆栈顶部元素的下标值。它的初始值为-1，提示堆栈为空。push函数在存储新元素之前先增加这个变量的值，这样top_element始终包含顶部元素的下标值。

这个堆栈模块的一个值得注意的特性就是它使用assert宏来防止非法操作，诸如从一个空堆栈中弹出一个元素或者从一个已满堆栈中压入元素。这个断言调用is_full和is_empty函数，而不是测试top_element本身。如果你以后决定使用不同的方法来检测空堆栈或者满堆栈，使用这种方法显然要容易很多。

对于用户无法消除的错误，使用断言是很合适的。

下篇博文再说用动态数组实现堆栈以及使用链式结构实现堆栈！

文章来源: reborn.blog.csdn.net，作者：李锐博恩，版权归原作者所有，如需转载，请联系作者。

原文链接：reborn.blog.csdn.net/article/details/82729120