3.线性表之栈(手工实现)
栈 栈(Stack)是限定仅在表尾进行插入和删除的线性表
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又称为是后进先出(Last In First Out)的线性表，简称LIFO结构。
理解栈的时候要注意：
首先它是一个线性表，即栈元素具有线性关系(前驱后继)关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾指栈顶，而不是栈底。
它的特殊之处在于限制了这个线性表的插入和删除位置，它时钟只在栈顶进行。这也就使得:栈底是固定的，最先进栈的只能在栈底
栈的插入操作，叫做进栈，也称压栈、入栈。 栈的删除操作，叫做出栈，也有的叫做弹栈，如下图所示：
文章图片
由于栈本身是一个线性表，所以对于存储方式来说有顺序存储和链式存储两种类型。
顺序栈 类结构图
文章图片
静态顺序栈封装类
package com.company.datastructure;
/**
* 静态栈的顺序存储
* @param 泛型
*/
public class MyStack {
private Object[] elements;
//使用数组存储栈
private int top;
//栈顶标识
private int size;
//当前栈的大小
private final int DEFAULT_CAPACITY = 30;
//默认初始化长度为30
/**
* 初始化一个空栈
*/
public MyStack(){
elements = new Object[DEFAULT_CAPACITY];
top = -1;
//top=-1时表示空栈
}/**
* 入栈
* @param element 元素值
*/
public void push(E element) {
if (size 栈测试类
public class TestMyStack {
public static void main(String[] args) {
MyStack ms = new MyStack<>();
ms.push("chen0");
ms.push("chen1");
ms.push("chen2");
System.out.println(ms.size());
int size = ms.size();
for (int i = 0;
i < size;
i++) {
System.out.println(ms.peek());
ms.pop();
}
}
}对于两个相同类型的栈，可以考虑两个栈共用同一空间，如下图所示：
文章图片
关键思路是:两个栈在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要他们两个不碰面，两个栈就可以一直使用。那么什么时候栈满呢?
两个栈顶见面时即：top1+1=top2时，栈为满栈。
链栈 【3.线性表之栈(手工实现)】由于栈只有栈顶能够进行插入和删除操作，而且单链表有头指针，所以栈顶在单链表头部，并且不需要单链表的头结点。
如下图1所示，
文章图片
文章图片
文章图片
对于链栈来说，由于是在单链表头部进行插入和删除，所以也就不存在栈满的问题了。
入栈：如图2所示，首先将新结点next指针指向当前top结点，然后将新结点赋值给top结点即可
出栈：如图3所示，首先将栈顶元素下移，然后将原栈顶结点指针设置为null；
类结构图
文章图片
链栈封装类
package com.company.datastructure;
/**
* 静态栈的链式存储
* @param 泛型
*/
public class MyLinkStack {
private class Node{
public E element;
private Node next;
public Node(E element){
this.element = element;
}
}
private Node top;
private int size;
public MyLinkStack(){
top = null;
}/**
* 入栈
* @param element 栈元素值
*/
public void push(E element){
Node newNode = new Node<>(element);
newNode.next = top;
top = newNode;
size++;
}/**
* 出栈
* @return 出栈元素
*/
public E pop() {
if(top==null){
throw new NullPointerException("栈为空栈");
}else{
Node temp = top;
top = top.next;
temp.next = null;
size--;
return temp.element;
}
}/**
* 取得栈底元素
* @return 栈顶元素值
*/
public E peek(){
if(top==null){
throw new NullPointerException("栈为空栈");
}else{
return top.element;
}
}/**
* 获得链栈长度
* @return 链栈长度
*/
public int getSize(){
return size;
}/**
* 判断空栈
* @return 空返回true否则返回false
*/
public boolean isEmpty(){
return size==0?true:false;
}
}
链栈测试类
package com.company.datastructure;
public class TestMyLinkStack {
public static void main(String[] args) {
MyLinkStack mls = new MyLinkStack<>();
mls.push("chen0");
mls.push("chen1");
mls.push("chen2");
System.out.println(mls.getSize());
int size = mls.getSize();
for (int i = 0;
i < size;
i++) {
System.out.println(mls.peek());
mls.pop();
}
}
}对比一下顺序栈和链栈可以看到，在时间性能上，顺序栈和链栈的时间复杂度都是O(1),在空间性能上 ，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的情况，但优势是存取和定位都十分方便。而链栈需要每个结点都有一个指针域，在一定程度上增加了内存开销，但是链栈的长度没有限制。所以如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。
推荐阅读
- 程序员客栈TOP收入的萌系开发者心得|程序员客栈TOP收入的萌系开发者心得 - 雨晴
- C语言进阶栈帧示例详解教程
- c语言|一文搞懂栈(stack)、堆(heap)、单片机裸机内存管理malloc
- Java深入了解数据结构之栈与队列的详解
- 机器学习|线性回归原理与python实现
- Java积累|Java积累 - 堆和栈
- Python|Python实战（使用线性回归预测房价）
- 浅析栈溢出遇到的坑及绕过技巧
- 机器学习之回归
- 机器学习|线性回归的正规方程法