欢迎关注个人主页：逸狼

---

创造不易，可以点点赞吗~

如有错误，欢迎指出~

---

---

目录

栈

栈的方法介绍

入栈push

出栈pop和

瞄一眼peek

判空isEmpty和判满isFull

模拟实现栈

push入栈

pop出栈和peek

 测试

使用泛型实现栈

测试

使用链表实现栈（链式栈）

---

栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。

栈是一种 先进后出 的数据结构

栈的方法介绍

入栈push

<code>Stack<Integer> stack=new Stack<>();

//入栈

stack.push(1);

stack.push(2);

stack.push(3);

stack.push(4);

出栈pop和

pop出栈,会删除栈顶元素

<code> //出栈

Integer x=stack.pop();

System.out.println(x);

瞄一眼peek

peek（瞄一眼~）获取栈顶元素，不删除

<code>//peek

Integer y1=stack.peek();

System.out.println(y1);

Integer y2=stack.peek();

System.out.println(y2);

判空isEmpty和判满isFull

Stack<Integer> stack=new Stack<>();

System.out.println(stack.isEmpty());

System.out.println(stack.isFull());

模拟实现栈

下面是利用数组模拟实现一个栈，这种叫做顺序栈。

定义一个数组来实现栈

usedSize表示

当前存放的数据个数当前存放数据的下标

<code>public class MyStack {

public int[] elem;

public int usedSize;

public MyStack(){

this.elem=new int[10];//初始设定为10个空间

}

}

push入栈

public void push(int val){

//判断是否满了

if(isFull()){

//扩容

elem= Arrays.copyOf(elem,2*elem.length);

}

elem[usedSize]=val;

usedSize++;

}

public boolean isFull(){

return usedSize==elem.length;

}

pop出栈和peek

public int pop(){

if(empty()){

return -1;

}

int oldVal=elem[usedSize-1];

// elem[usedSize-1]=null;//如果是引用类型要置空

usedSize--;

return oldVal;

}

public int peek(){

if (empty()) {

return -1;

}

return elem[usedSize-1];

}

public boolean empty(){

return usedSize==0;

}

 测试

MyStack myStack=new MyStack();

myStack.push(1);

myStack.push(2);

myStack.push(3);

System.out.println(myStack.pop());

System.out.println(myStack.peek());

System.out.println(myStack.peek());

使用泛型实现栈

将int换成E类型

<code>import java.util.Arrays;

public class MyStack2<E> {

public Object[] elem;

public int usedSize;

public MyStack2(){

this.elem=new Object[10];//初始设定为10个空间

}

public void push(E val){

//判断是否满了

if(isFull()){

//扩容

elem= Arrays.copyOf(elem,2*elem.length);

}

elem[usedSize]=val;

usedSize++;

}

public boolean isFull(){

return usedSize==elem.length;

}

public E pop(){

if(empty()){

return null;

}

E oldVal=(E)elem[usedSize-1];

// elem[usedSize-1]=null;//如果是引用类型要置空

usedSize--;

return oldVal;

}

public E peek(){

if (empty()) {

return null;

}

return (E)elem[usedSize-1];

}

public boolean empty(){

return usedSize==0;

}

}

测试

MyStack2<Integer> myStack2=new MyStack2<>();

myStack2.push(9);

myStack2.push(8);

myStack2.push(7);

System.out.println(myStack2.pop());

System.out.println(myStack2.peek());

System.out.println(myStack2.peek());

使用链表实现栈（链式栈）

如果使用的是单链表，那么入栈和出栈最好使用链表的头部，这样的时间复杂度可以达到O(1),

若用链表的尾部，时间复杂度是O(N)

如果使用的是双向链表，那么入栈和出栈可以使用链表的头部或尾部，时间复杂度都是O(1)