数据结构与算法02-栈和队列(java实现)

什么是栈呢？大家可以把它想象成一个狭窄的盒子，我们往里面放东西，每次取出时，只能取出最后放进去的(最上面一个)，总结来讲就是 “先进后出”，如下图：

特点：先进后出，每次只能取得栈顶元素

思想：使用数组来实现栈
进栈push时，依次往数组后追加元素即可（和前面讲过的数组操作一样）
在出栈pop时，我们每次都取最后一个元素

相关操作：进栈push 、出栈pop 、获取栈顶元素peek 、判断为空isEmpty

代码：

public class MyStack {
    //栈底层采用数组存储
    int[] arr;
    public MyStack(){
        arr=new int[0];
    }
    //进栈 (和数组的add一样)
    public void push(int element){
        //初始化一个数组
        int[] newArr=new int[arr.length+1];
        for(int i=0;i 
测试类
 
public class TestStack {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        System.out.println("栈顶元素为:"+myStack.peek());
        System.out.println("出栈了"+myStack.pop());
        System.out.println("出栈了"+myStack.pop());
        System.out.println(myStack.isEmpty());
        System.out.println("出栈了"+myStack.pop());
        System.out.println(myStack.isEmpty());
    }
}
 
结果
 
栈顶元素为:3
出栈了3
出栈了2
false
出栈了1
true
 
2. 队列 
2.1 简介 
队列，听到这个词大家就想到生活中的排队吧，没错，其实队列就是排队
 排队时，我们必须遵守先来排前面，后来排后面，并且前面的人优先通过
 (当然vip除外哈，这里不错考虑)
 队列也一样，正好和栈相反：“先进先出”
 
 
特点：先进先出 （和我们平时排队一样，排在前面就优先）
 
2.2 队列的实现 
实现思想：
 
底层还是使用数组实现，和栈唯一不同是出栈每次取出数组第一个元素
 
主要操作：进队add 出队pill 判断是否为空isEmpty
 
代码：
 
public class MyQueue {
    //队列底层采用数组存储
    int[] arr;
    public MyQueue(){
        arr=new int[0];
    }
    //进栈 (和数组的add一样)
    public void add(int element){
        //初始化一个数组
        int[] newArr=new int[arr.length+1];
        for(int i=0;i 
测试：
 
public class TestQueue {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.add(1);
        myQueue.add(2);
        myQueue.add(3);
        System.out.println("出队了："+myQueue.pill());
        System.out.println("出队了："+myQueue.pill());
        System.out.println("出队了："+myQueue.pill());
        System.out.println(myQueue.isEmpty());
    }
}
 
结果：
 
出队了：1
出队了：2
出队了：3
true