栈(stack) C语言实现详解

Love The Way You Lie 2022-05-25 05:25 155阅读 0赞

2019/5/22 更新，将颠倒的Push和Pop方法更正，并更换图片。  
栈是数据结构中较为简单的结构体,是一种操作收到限制的线性表.但简单不代表没用,毕竟数组很简单.但谁敢说数组没用呢?

# 栈 #

## 栈的理论 ##

*  栈是一个先进后出的结构,类似于堆盘子,先放到地上的盘子最后被取走(默认只能取走一个盘子)
 *  栈其实就是操作受限的线性表,只有一个口,每一次操作时,这个口可以当出口也可以当入口.
 *  例如:水桶,注入水时,水桶的头当做入口,倒水时,水桶的头当做出口

## 栈的图解. ##

在图解之前,先举一个例子,让大家记住栈 : **栈其实就是吃了一顿饭,然后吐出来.**

*  这是一个空栈,只有上面是入口和出口  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70]
 *  **放入一个元素a**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 1]

*  接着依次放入B,C元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 2]

*  取出一个元素,由栈只有一个口的特点可以知道取出了C

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 3]

*  **再次放入一个元素D**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 4]

栈的可用操作

根据理论环节,可以轻易的看出:栈的基本操作只有两个:

*  入栈
 *  出栈

而且样子长得十分像一个水桶。

但是如果栈已经放满了,就像水桶装满了水一样,不能再放水了,即不能再进行入栈操作,所以要在每次入栈前判断栈满的情况.同理,出栈之前,栈中必须有数据,不然就出现要么空指针,要么野指针.都不是我们想要的结果,所以出栈前要判断栈空,.  
所有一个栈一共有四个功能:

*  入栈(英文名:push)
 *  判(栈)满(isFull)
 *  出栈(pop)
 *  判(栈)空(isEmpty)

## 栈的C语言定义(结构体) ##

开篇就说了栈是操作收到限制的线性表,而众所周知的线性表主要有:  
1.顺序存储的数组,  
优点: 节省空间, 操作简单,学习成本较低,易于理解.  
缺点: 栈的大小一开始就声明’死’了,不利于使用.  
2.非顺序存储的链表.  
优缺点:与数组栈正好相反.

两种栈各有好处,争论是愚蠢的,学习是学不完的,所以赶快开始coding吧

### 数组栈 ###

数组栈,顾名思义,就是基于数组的栈,也是说把一个数组的强大的下标功能阉割掉,并且只能从一头进入(数组头明显更为方便)  
所以结构体为:  
(为了方便学习,存储类型统一使用int,但是我们一般更习惯在头文件下面给int 起一个别名,原因很简单:这样就这样实现简单的多态,需要将int类型栈改成char类型栈时,只需要改定义的别名中的类型即可)

typedef struct
    { 
        int Data[MaxSize];   // 存储元素的数组
        int topIdx;       //栈顶指针
    }SeqStack;

栈的四个基本操作定义:

//return 0 为false,1为true(下同)
    // 将元素推入栈中
    int Push(SeqStack &L, int e)
    {  // 栈已满
    	if(L.topIdx==MaxSize -1)
        { 
            return 0;
        }
        // 加入栈中
        L.Data[L.topIdx++] = e;
        // 返回自身
        return e;
    }
    // 移除栈顶元素
    int Pop(SeqStack &L)
    { 	// 栈空
         if(L.topIdx == 0)
        { 
             //返回失败
             return 0;
        }
        // 打印并返回栈
        int val = L.Data[--L.topIdx];
        printf("%d ",val);
        return val;
    }
    //判断栈s是否为空
    int isEmpty(SeqStack s)
    { 
        // 如果下标在0，说明栈中无元素
        if(s.topIdx != 0)
        { 
            return 1;
        }
        return 0;
    }
    // 判断栈是否已栈.
    Status isFull(SeqStack s)
    { 
        // 已满返回true(1)
        if(s.topIdx != MaxSize -1)//之前的定义数组的最大值的下标
        { 
            return 1;
        }
        return 0;
    }

### 链表栈 ###

结构体

typedef struct LNode
    { 
        ElemType data;
        struct LNode * next;
    } LNode,*LinkList;

两大功能(链表无需判满,判空也简单,不再单独实现)

Status Pop(LinkList L)
    { 
        if(L->next == NULL)
        { 
            return 0;
        }
        LinkList tem = L->next;
        printf("%d ",tem->data);
        L->next = tem->next;
        free(tem);
        return 1;
    }
    Status Push(LinkList L, ElemType e)
    { 
        LinkList newNode = (LinkList) malloc(sizeof(LinkList));
        newNode->data = e;
        newNode->next = L->next;
        L->next = newNode;
        return 1;
    }

最后写几个简单的作业(我们老师留给我们的)以及我的代码

//1、本题要求实现顺序栈，写出Push 、Pop、StackEmpty函数的实现，并用一个简单的main函数测试。
    
    //已有类型定义
    typedef struct
    { 
        ElementType Data[MaxSize];   // 存储元素的数组
        Position Top;       //栈顶指针
    }SeqStack;
    
    //函数接口定义：
    Status Push(SeqStack &L, ElemType e);
    Status Pop(SeqStack &L, ElemType &e);
    Status StackEmpty(SeqStack s);  //判断栈s是否为空
    //其中 L 和 e 都是用户传入的参数。 L 是带头结点的头指针； e 是数据元素。
    /** * 3、进制转换。 * 输入一个十进制正整数n和一个目标进制R（１<R<10)，将ｎ转换为R进制。要求不使用递归或数组，而使用第1题* 或第2题中定义的栈来实现。 */

我的代码实现：

#include <stdio.h>
    #include <stdlib.h>
    #define MaxSize 100
    typedef int Status;
    typedef int ElemType;
    typedef int Position;
    //1、本题要求实现顺序栈，写出Push 、Pop、StackEmpty函数的实现，并用一个简单的main函数测试。
    //已有类型定义
    typedef struct
    { 
        ElemType Data[MaxSize];   // 存储元素的数组
        Position Top;       //栈顶指针
    } SeqStack;
    
    //函数接口定义：
    Status Push(SeqStack &L,ElemType e);
    Status Pop(SeqStack &L);
    Status StackEmpty(SeqStack s);  //判断栈s是否为空
    Status prinStack(SeqStack &L);
    Status convNum(int n, int R);
    Status pipei();
    void work1();
    //其中 L 和 e 都是用户传入的参数。 L 是带头结点的头指针； e 是数据元素。
    int main()
    { 
        //work1();//第一题
        //convNum(8,2);//进制转化
        pipei();
        return 0;
    }
    Status prinStack(SeqStack &L)
    { 
        while (StackEmpty(L))
        { 
            Push(L);
        }
        return 1;
    }
    void work1()
    { 
        SeqStack L;
        L.Top = 0;
        Pop(L, 1);
        Pop(L, 2);
        Pop(L, 3);
        prinStack(L);
    }
    Status Pop(SeqStack &L)
    { 
    if(L.Top == 0)
        { 
            return 0;
        }
        printf("%d ",L.Data[--L.Top]);
        return 1;
    }
    Status Push(SeqStack &L, ElemType e)
    { 
            if(L.Top==MaxSize -1)
        { 
            return 0;
        }
        L.Data[L.Top++] = e;
        return 1;
    }
    //判断栈s是否为空
    Status StackEmpty(SeqStack s)
    { 
        if(s.Top != 0)
        { 
            return 1;
        }
        return 0;
    }
    //3、进制转换。
    //输入一个十进制正整数n和一个目标进制R（１<R<10)，将ｎ转换为R进制。要求不使用递归或数组，而使用第1题或第2题中定义的栈来实现。
    Status convNum(int n, int R)
    { 
        //声明栈
        SeqStack L;
        L.Top = 0;
        while (n!=0)
        { 
            //将每次产生的余数防入栈低
            Pop(L, n%R);
            n/=R;
        }
        prinStack(L);
        return 1;
    }

以下附上Java 代码实现的栈

public class LinkedStack<T> { 
        private Node topNode;
    
        public T push(T newEntry) { 
            Node newNode = new Node<T>(newEntry, topNode);
            topNode = newNode;
            T tempData = peek();
            return tempData;
        }
    
        public T pop() { 
            T tempData = peek();
            if (tempData == null) { 
                return null;
            }
            topNode = topNode.next;
            return tempData;
        }
    
        public T peek() { 
            if (isEmpty()) { 
                return null;
            }
            return (T) topNode.data;
        }
    
        public boolean isEmpty() { 
            return topNode == null;
        }
    
        public void clear() { 
            topNode = null;
            // java拥有内存回收，只需要让头结点引用为空即可，GC就可以回收掉所有其他节点。
        }
    
        public LinkedStack() { 
            this.topNode = null;
        }
    
        private class Node<T> { 
            private T data;
            private Node next;
    
            public Node(T dataPortion) { 
                this(dataPortion, null);
            }
    
            public Node(T data, Node next) { 
                super();
                this.data = data;
                this.next = next;
            }
    
            public T getData() { 
                return data;
            }
    
            public void setData(T data) { 
                this.data = data;
            }
    
            public Node getNext() { 
                return next;
            }
    
            public void setNext(Node next) { 
                this.next = next;
            }
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70]: /images/20220525/78d33d5af67e4d8aaa29b063e490059b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 1]: /images/20220525/99c4b2a5b65a44e4b6187fa5dcfa7413.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 2]: /images/20220525/2a0dba0c8a8f423aa7f8de6633c238d3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 3]: /images/20220525/b9d0ae95b200438f96b6308681f42c5d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTYxOTQ4_size_16_color_FFFFFF_t_70 4]: /images/20220525/39022360b1644cf3a6915ce64fcccdd3.png