大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

2022/8/10 说明: 评论区有很多反对的声音, 有说我写错的, 有说我用了C++的, 大家可以自己多尝试下, 截至2022/8/10的反馈我都看过了, 目前都没问题.
2019/5/22 更新，将颠倒的Push和Pop方法更正，并更换图片。
栈是数据结构中较为简单的结构体,是一种操作收到限制的线性表.但简单不代表没用,毕竟数组很简单.但谁敢说数组没用呢?

栈

栈的理论

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

栈的图解.

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

• 这是一个空栈,只有上面是入口和出口
  

• 放入一个元素a

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

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

• 再次放入一个元素D

栈的可用操作

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

• 入栈
• 出栈

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

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

• 入栈(英文名: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;
        }

    }
}