数据结构之栈（C语言实现）

淩亂°似流年 2023-07-19 05:47 14阅读 0赞

**Table of Contents**

定义

实现

定义结构

定义操作初始化栈

判断栈是否为空

访问栈顶元素

出栈

入栈

--------------------

# 定义 #

在线性表中，根据存储结构可分为：顺序表和链表。顺序表和链表可以访问任意位置结点，在任意位置插入和删除结点。倘若对上述操作加以限制，如：  
1. 在线性表的一端插入、删除、访问结点。  
2. 在线性表的一端插入结点、另一端删除、访问结点。

\*注：对线性表操作的限制有很多，上述只介绍两种主流的限制，在数据结构中叫做栈和队列。

栈的概念比较抽象，举个栗子（对，就是板栗的栗子）。

一群人依次走进一个死胡同，宽度只够通行一个人。如果他们要出来，只能依次退出来。最后进去的人最先出来，在外面的人也只看的见最后进去的人是谁。这里，进去一个人叫做插入结点，出来一个人叫做删除结点。看的见最后进去的人，叫访问结点。

总结：栈有先进后出的特性，简称FILO（First in Last Out）。只能在线性表的一端插入和删除结点。

# 实现 #

栈是操作受限制的线性表，根据不同的存储结构可分成顺序栈和链式栈。  
在顺序栈中，可以将顺序表的有效长度作为栈顶指针，在顺序表的末尾删除和插入节点。  
在链式栈中，可以将链表的头结点作为栈顶指针，入栈采用头插法。

## 定义结构 ##

#define LIST_INIT_SIZE 10
    #define LISTINCREMENT 2
    
    typedef int StackType; //存储单元类型
    
    typedef struct stackNode {
        StackType *elem; //存储空间基地址
        int length; //当前长度
        int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）
    }Stack;

这里定义的实际上是顺序表的结构，所以实现的也就是顺序栈。只是操作方法比顺序表的操作少很多。

## 定义操作   初始化栈 ##

int initStack(Stack& stack) {
        stack.elem = (StackType *) malloc(sizeof(StackType) * LIST_INIT_SIZE);
        if (!stack.elem)
            return 0; //内存分配失败，存储空间不够
        stack.length = 0;
        stack.listsize = LIST_INIT_SIZE;
        return 1;
    }

给栈的基地址分配一段连续的存储单元，并标记栈的长度为0。初始化成功返回1，初始化失败返回0。

## 判断栈是否为空 ##

int isEmptyStack(Stack stack) {
        return stack.length;
    }

栈为空，返回0，不为空返回非0。

## 访问栈顶元素 ##

int top(Stack stack, StackType& elem) {
        if (stack.length == 0)
            return 0;
        elem = stack.elem[stack.length - 1];
        return 1;
    }

取出栈顶元素，传值给形参elem，但不删除栈顶元素。由于采用的是引用的方式，因此形参值的改变可以传给实参。如果栈为空，返回0，栈非空，返回1。

## 出栈 ##

int pop(Stack& stack, StackType& elem) {
    
        if (stack.length > 0) {
            elem = stack.elem[--stack.length];
            return 1;
        }
        return 0;
    }

取出并删除栈顶元素，传值给形参elem。由于采用的是引用的方式，因此形参值的改变可以传给实参。如果栈为空，返回0，栈非空，返回1。

## 入栈 ##

int push(Stack& stack, StackType data) {
        if (stack.length == stack.listsize) { //顺序表的存储单元已经存满
            printf("顺序表的存储单元已满，继续分配新的存储单元。");
            StackType* newBase = (StackType*) realloc(stack.elem,
                    (stack.listsize + LISTINCREMENT) * sizeof(StackType)); //继续分配存储单元
            if (!newBase) {
                printf("分配内存单元失败");
                return 0;
            }
            stack.elem = newBase;
            stack.listsize += LISTINCREMENT;
        }
        stack.elem[stack.length] = data;
        stack.length++;
        return 1;
    }

在栈顶插入元素。若，当前栈已满，继续分配内存单元再插入。返回1表示入栈成功，返回0表示入栈失败。

最后附上头文件的定义

/*
     * stack.h
     *
     *  Created on: 2016年9月26日
     *      Author: flueky
     */
    
    
    #ifndef STACK_H_
    #define STACK_H_
    
    #define LIST_INIT_SIZE 10
    #define LISTINCREMENT 2
    
    typedef int StackType; //存储单元类型
    
    typedef struct stackNode {
        StackType *elem; //存储空间基地址
        int length; //当前长度
        int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）
    }Stack;
    
    int initStack(Stack&);
    
    int isEmptyStack(Stack);
    
    int top(Stack,StackType&);
    
    int push(Stack&,StackType);
    
    int pop(Stack&,StackType&);
    
    #endif /* STACK_H_ */