栈和队列(上)-栈

1. 栈的概念

引入:

我们平时拿羽毛球,是从盒子顶部的羽毛球开始拿的,而顶部的元素是我们最后放进去的.

栈: 一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则.总而言之就是一个后进先出的线性表

压栈: 在栈里面插入元素,也叫做进栈/压栈/入栈.入数据是在栈顶

出栈: 在栈里面删除元素,也叫做出栈.出数据在栈顶

2. 实现栈的方式

我们实现栈可以用数组来实现,也可以用链表来实现栈.

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的.

我们也可以用链表来实现栈,我们如果用双链表来实现栈就很方便不管在把头当栈顶还是把尾当栈顶,出入栈都是O(1),但是如果用单链表,把它的尾巴当栈顶,那么出入栈就是O(n),用头当栈顶和双链表一样是O(1)

3. 栈的底层实现

我们为了更好的理解栈,我们来自己实现一个栈

首先我们写一个IStack接口

然后我们写一个MyStack类实现这个接口,我们先来解释一下接口的一些变量,我们实现MyStack是使用的数组来实现的,所以我们先定义一个elem数组,我们再创建一个usedSize变量来记录有效数据的个数,然后设置一个默认容量,并且生成俩个构造方法,一个无参数的构造方法,在创建栈的时候默认容量是10,一个有参的构造方法,我们要大就设置多大的值.

3.1 判断栈是不是满 isFull()

当usedSize的大小和elem数组的大小一样的时候,我们就知道栈满了,如果不一样则没满.

3.2 判断栈是不是空的 empty()

如果usedSize的大小为0,说明栈里面没有元素了.

3.3 计算栈的有效数据的数目(栈的大小) size()

我们设置count变量,然后遍历整个栈,进行计数,其实也可以直接返回usedSize.

3.4 入栈 push(int x)

我们的usedSize下标就相当于一个下标,表示没有元素在数组里面的下标,因此我们直接借助usedSize即可,也就是elem[usedSize] = x;usedSize++;这就是入栈操作,不过在把元素放进去之前我们要判断栈是不是满了,如果满了我们就要进行二倍扩容也就是

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

3.5 出栈 pop()

我们的出栈,首先要判断栈是不是空,如果式空我们需要抛出异常,在这个基础上,我们进行出栈操作,我们先保存出栈的元素的值,然后操作usedSize下标即可,因为我们入栈也是通过usedSize下标,就算数组下标之前有值,我们也可以直接覆盖掉.

3.6 查看栈顶元素 peek()

我们查看栈顶元素同样要看栈是不是空的,然后我们直接返回usedSize-1下标的elem数组的值即可.

整体代码:

package 栈和队列;import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;public class MyStack implements IStack{//我们的栈底层是个数组private int[] elem;private int usedSize;//有效数据的个数private static final int DEFALUT_CAPACITY = 10;public MyStack() {elem = new int[DEFALUT_CAPACITY];}public MyStack(int capacity) {elem = new int[capacity];}@Overridepublic void push(int x) {//TODO 入栈//先判断栈是不是满的if(isFull()) {elem = Arrays.copyOf(elem, 2 * elem.length);}//把usedSize位置赋值为xelem[usedSize] = x;usedSize++;}@Overridepublic int pop() {//TODO 出栈//先判断是不是没有元素if(empty()){//抛异常throw new EmptException("栈空,无法出栈! ");}//我们的usedSize相当于存储了下标int old = elem[usedSize - 1];usedSize--;//这个就相当于删除,虽然原来位置还是有值,但是我们后期push会覆盖掉原先的值//如果是引用类型: elem[usedSize] = null;return old;}@Overridepublic int peek() {//TODO 看栈顶元素//先判断是不是没有元素if(empty()){//抛异常throw new EmptException("栈空,无法出栈! ");}return elem[usedSize - 1];//直接返回即可}@Overridepublic int size() {int count = 0;for (int i = 0; i < usedSize; i++) {count++;}return count;}@Overridepublic boolean empty() {return usedSize == 0;}@Overridepublic boolean isFull() {if (usedSize == elem.length){return true;}return false;}
}

4. java提供的栈的方法的使用和介绍

下面是栈的方法:

方法	功能
Stack()	构造一个空的栈
E push(E e)	入栈并返回e
E pop()	出栈并返回栈顶元素
E peek()	获取栈顶元素
int size()	获取栈种有效元素的个数
boolean empty()	检测栈是否为空

E这里表示泛型,泛型表示引用数据类型.

我们来使用一下:

public class T1 {public static void main(String[] args) {Stack<Integer> s = new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size()); // 获取栈中有效元素个数---> 4System.out.println(s.peek()); // 获取栈顶元素---> 4s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3if (s.empty()) {System.out.println("栈空");} else {System.out.println(s.size());}}
}
结果:
4
4
3
2