理解栈手写栈
一、栈的基础知识
1.1 栈的特征
栈和队列是比较特殊的线性表，又称之为访问受限的线性表。栈是很多表达式、符号等运算的基础，也是递归的底层实现。理论上递归能做的题目栈都可以，只是有些问题用栈会非常复杂。
栈底层实现仍然是链表或者顺序表，栈与线性表的最大区别是数据的存取的操作被限制了，其插入和删除操作只允许在线性表的一端进行。一般而言，把允许操作的一端称为栈顶(Toρ)，不可操作的一端称为栈底(Bottom),同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈。
1.2 栈的操作
栈的常用操作主要有：
push(E):增加一个元素E
pop():弹出元素E
peek():显示栈顶元素，但是不出栈
empty():判断栈是否为空
我们在设计自己的栈的时候，不管用数组还是链表，都要实现上面几个方法。
1.3 java中的栈
java的util中就提供了栈Stack类，使用不复杂，看一个例子就够了：
public class MainTest{
public static void main(String[]args){
Stack<Integer>stack new stack();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println("栈顶元素为："+stack.peek());
while (!stack.empty()){
//只显示没出栈
System.out.println(stack.peek());
//出栈并且显示
System.out.println(stack.pop());
}
}
}
二、基于数组实现栈
import java.util.Arrays;
class Mystack<T>{
//实现栈的数组
private Object[] stack;
//栈顶元素
private int top;
Mystack(){
//初始容量为10
stack new Object[10];
}
//判断是否为空
public boolean isEmpty(){
return top == 0;
}
//返回栈顶元素
public T peek(){
T t = null;
if (top > 0)
t = (T) stack[top -1];
return t;
}
public void push(T t){
expandCapacity(top + 1);
stack[top] = t;
top++;
}
//出栈
public T pop(){
T t = peek();
if(top > 0){
stack[top - 1] = null;
top--;
}
return t;
}
//扩大容量
public void expandCapacity(int size){
int len = stack.length;
if (size > len)
size = size * 3 / 2 + 1;//每次扩大50%
stack = Arrays.copyOf(stack, size);
}
}
三、基于链表实现栈
class ListStack<T>{
//定义链表
class Node<T>{
public T t;
public Node next;
}
public Node<T>head;
//构造函数初始化头指针
ListStack(){
head null;
}
//入栈
public void push(T t){
if (t =null){
throw new NullPointerException("参数不能为空")；
}
if (head == null){
head = new Node<T>();
head.t =t;
head.next = null;
}
else{
Node<T>temp = head;
head = new Node<>();
head.t = t;
head.next = temp;
}
}
//出栈
public T pop(){
if (head == null){
return null;
}
T t = head.t;
head = head.next;
return t;
}
//取栈顶元素
public T peek(){
if (head == null){
return null;
T t = head.t;
return t;
}
}
//栈空
public boolean isEmpty(){
if (head == null)
return true;
else
return false;
}
}
