数据结构与算法学习——栈结构

在程序设计中，一定接触过“堆栈”的概念。其实，“栈 ” 和 “堆 ” 是两个不同的概念。这里，栈是一种特殊的数据结构，在中断处理特别是重要数据的现场保护有着重要意义。

1. 什么是栈结构

从数据的逻辑结构来看，栈结构其实就是一种线性结构。如果从数据的存储结构来进一步划分，栈结构包括两类。

顺序桟结构：即使用一组地址连续的内存单元依次保存栈中的数据。在程序中，可以定义一个指定大小的结构数组来作为栈，序号为0的元素就是栈底，再定义一个变量top保存栈顶的序号即可。

链式栈结构：即使用链表形式保存栈中各元素的值。链表首部 （head 指针所指向元素）为栈顶 ，链表尾部 （指向地址为NULL) 为栈底。

典型的栈结构，如图1所示。从图中可以看出，在栈结构中只能在一端进行操作，该操作端称为栈顶，另一端称为栈底。也就是说，保存和取出数据都只能从栈结构的一端进行。从数据的运算角度来分析，栈结构是按照“后进先出”的原则处理结点数据的。

其实，栈结构在日常生活中有很多生动的例子。例如，当仓库中堆放货物时，先来的货物放在里面，后来的货物码放在外面；而要取出货物时，总是先取外面的，鉍后才能取到里面放的货物。也就是说，后放入货物先取出。

在栈结构中，只有桟顶元素是可以访问的，栈结构的数据运算也非常简单。一般栈结构的基本操作只有两个。

• 入栈（Push):将数据保存到栈顶的操作。进行入栈操作前，先修改栈顶指针，使其向上移一个元素位置，然后将数据保存到栈顶指针所指的位置。
• 出栈（Pop):将栈顶数据弹出的操作。通过修改找顶指针，使其指向栈中的下一个元素。

1. 栈的数据结构定义

#include <stdio.h>
#include <malloc.h>
#define  MAXLEN  50 //定义栈结构的最大长度
typedef struct
{
   char  name[10];  //姓名
   int   age;      //年龄
}Data;
typedef struct stack
{
    Data  data[MAXLEN];  //数据元素
    int   top ;          
//栈顶   top为0时表示栈空，top为MAXLEN-1表示栈满。
}Student;

2. 初始化栈结构
   在使用顺序栈之前，首先要创建一个空的顺序栈，也就是初始化顺序栈。顺序栈的初始化操作步骤如下：

(1)按符号常量MAXLEN指定的大小申请一片内存空间，用来保存栈中的数据。

(2) 设置栈顶指针的值为0 ,表示是一个空栈。

初始化顺序栈的示例代码如下：

Student  *StInit()
{
    Student  *p;
    if(p=(Student *)malloc(sizeof(Student)))
    {
        p->top = 0; //设置栈顶为0;
        return p;  //返回指向栈的指针
    }
    return NULL;
}

说明：首先使用malloc()函数申请内存，申请成功后设置栈顶为0，然后返回申请内存的首地址。如果申请内存失败，将返回—NULL。

3. 判断空栈

判断空栈就是判断一个栈结构是否为空。如果是空栈，则表示该栈结构中没有数据。此时可以进行入栈操作，但不可以进行出找操作。

判断空栈代码如下

int StIsEmpty(Student *s)
{    
    int t;
    t = s->top==0?1:0;
 
    return t;
}

说明：在这里，输入参数s为一个指向操作的栈的指针。程序中，根据栈顶指针top是为0，判断栈是否为空。

4. 判断满栈

判断满找就是判断一个栈结构是否为满。如果是满栈，则表示该找结构中没有多余的空间来保存额外数据。此时不可以进行入栈操作，但是可以进行出找操作。

判断满栈的示例代码如下：

int  StIsFull(Student *s)
{
    int t;
    t = s->top == MAXLEN - 1?1:0;
 
    return t;
}

说明：在这里，输入参数s为一个指向操作的栈的指针。程序中判断栈顶指针top是否已等于符号常量MAXLEN – 1,从而判断栈是否已满。

5. 清空栈
   淸空栈就是栈中的所有数据被淸除。清空栈的示例代码如下：

void  StClear(Student *s)
{
    s->top == 0;
}

说明：在这里，输入参数s 为一个指向操作的栈的指针。程序中，简单地将栈顶指针top设置为0，表示执行清空栈操作。

6. 释放空间
   释放空间是释放栈结构所占用的内存单元。由前面可知，在初始化栈结构时，使用了 malloc()函数分配内存空间。虽然可以使用清空栈操作，但是清空栈操作并没有释放内存空间，这就需要使用free()函数释放所分配的内存。

释放空间的示例代码如下

void StFree(Student *s)
{
    if(s)
      free(s);
}

说明：在这里，输入参数s为一个指向操作的栈的指针。程序中，直接调用free函数释放所分配的内存。一般在不需要使用栈结构时调用该函数，特别是程序结束时。

7. 入栈
   入栈（Push)是栈结构的基本操作，主要操作是将数据元素保存到栈结构。入栈操作的具体步骤如下：

(1) 首先判断桟顶top，如 果top大于等于MAXLEN则表示溢出, 进行出错处理。否则执行以下操作。

(2) 设置top=top+1 (栈顶指针加1 , 指向入栈地址）。

(3)将入栈元素保存到top指向的位置。

入栈操作的示例代码如下：

int PushSt(Student *s, Data data)
{
    if(s->top >= MAXLEN)
    {
        printf("栈溢出!\n");
        return 0;
    }
    s->data[++s->top] = data;   //将元素入栈
 
    return 1;
}

说明：在这里，输入参数s为一个指向操作的栈的指针，输入参数data是需要入栈的数据元素。程序中首先判断栈是否溢出，如果溢出则不进行入栈操作，否则修改栈顶指针的值，再将元素入栈。

8. 出栈

出栈（Pop)是栈结构的基本操作，主要操作与入栈相反，它是从栈顶弹出一个数据元素。出栈操作的具体步骤如下：

(1)首先判断栈顶top,如果top等于0，则表示为空栈，进行出错处理。否则，执行下面的步骤。

(2)将栈顶指针top所指位置的元素返回。

(3)设置top=top-1, 也就是使栈顶指针减1 , 指向栈的下一个元素，原来找顶元素被弹出。

Data PopSt(Student *s)
{
    if(s->top==0)
    {
        printf("栈为空！\n");
        exit(0);
    }
 
    return (s->data[s->top--]);
}

说明：在这里，输入参数s为一个指向操作的栈的指针。该函数返回值是一个Data类型的数据，返回值是栈顶的数据元素。

9. 读结点数据

读结点数据也就是读取栈结构中结点的数据。由于找结构只能在一端进行操作，因此这里的读操作其实就是读栈顶的数据。

需要注意的是，读结点数据的操作和出栈操作不同。读结点数据的操作仅是显示栈顶结点数据的内容，而出找操作则将栈顶数据弹出，该数据不再存在。

Data PeekSt(Student *s)
{
     if(s->top==0)
    {
        printf("栈为空！\n");
        exit(0);
    }
 
    return (s->data[s->top]);
}
 

说明：在这里，输入参数s 为一个指向操作的栈的指针。该函数返回值同样是一个Data类型的数据，返回值是栈顶的数据元素。

10. 完整实例

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
 
#define  MAXLEN  50 //定义栈结构的最大长度
 
typedef struct
{
   char  name[10];  //姓名
   int   age;      //年龄
}Data;
 
typedef struct stack
{
    Data  data[MAXLEN];  //数据元素
    int   top ;          //栈顶   top为0时表示栈空，top为MAXLEN-1表示栈满。
}Student;
 
 
//初始化顺序栈
Student  *StInit()
{
    Student  *p;
 
    if(p=(Student *)malloc(sizeof(Student)))
    {
        p->top = 0; //设置栈顶为0;
        return p;  //返回指向栈的指针
    }
 
    return NULL;
}
 
//判断空栈
int StIsEmpty(Student *s)
{    
    int t;
    t = s->top==0?1:0;
 
    return t;
}
 
//判断栈满
int  StIsFull(Student *s)
{
    int t;
    t = s->top == MAXLEN - 1?1:0;
 
    return t;
}
 
//清空栈
void  StClear(Student *s)
{
    s->top == 0;
}
 
//释放空间
void StFree(Student *s)
{
    if(s)
      free(s);
}
 
//入栈
int PushSt(Student *s, Data data)
{
    if(s->top >= MAXLEN)
    {
        printf("栈溢出!\n");
        return 0;
    }
    s->data[++s->top] = data;  //将元素入栈
 
    return 1;
}
 
//出栈
Data PopSt(Student *s)
{
    if(s->top==0)
    {
        printf("栈为空！\n");
        exit(0);
    }
 
    return (s->data[s->top--]);
}
 
//读栈顶数据
Data PeekSt(Student *s)
{
     if(s->top==0)
    {
        printf("栈为空！\n");
        exit(0);
    }
 
    return (s->data[s->top]);
}
 
int main(void)
{
    Student *s;
    Data d1,d2;
 
    s = StInit();
    printf("入栈操作:\n");
    printf("输入姓名  年龄进行入栈:\n");
 
    do{
        scanf("%s%d",d1.name,&d1.age);
        if(strcmp(d1.name,"0")==0)
            break;  //若输入0，则退出
        else
        {
            PushSt(s,d1);
        }
    }while(1);
    printf("\n");
    do{
        printf("出栈操作：按任意键进行出栈操作：\n");
        getchar();   //输入空格
        d2 = PopSt(s);
        printf("出栈数据是(%s, %d)\n",d2.name,d2.age);
    } while(1);   
 
    StFree(s);
 
    return 0;
 
}

说明：在这里主函数首先初始化栈结构，然后循环进行入栈操作，添加数据结点，当输入值全部为0 时则退出结点添加的进程。接下来，用户每按一次键，则进行一次出栈操作，显示结点数据 。当为空栈时，退出程序。

运行结果如下：