Java数据结构和算法-4-栈和队列-封装一个自定义栈和队列类并提供相关类方法

悠悠 2022-03-10 11:12 190阅读 0赞

这篇来学习下数据结构中的栈，我们学习Java SE的时候，特别是面向对象画内存图的时候，经常要画栈内存和堆内存。这篇，我们来学习下栈，并且以此了解栈的常见的操作方法的底层是如何实现的。栈就相当于一个箱子，我们往里面装东西。栈有这么一个特点：先进后出，后进先出。给栈添加元素，我们习惯叫做压入栈，取出元素，叫弹出栈。然后我们再来看看队列，就像我们生活中的派对通过一座桥，队列的特点是先进先出。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70][]

1、封装一个栈

栈的底层实现是一个数组，下面这个自定义栈类，提供了元素压栈和弹栈，查找元素和判断栈是否为空，是否满栈等方法。

package stack;
    
    public class MyStack {
    	//栈的底层是一个数组，由于一些特征，我们取名叫做栈
    	private long[] arr;
    	private int top; //元素索引
    	
    	/**
    	 * 默认无参构造
    	 */
        public MyStack() {
        	arr = new long[10];
        	top = -1; // 表示当前栈内没有元素，top等于0表示有一个元素
        }
        
        /**
         * 带参数的构造
         */
        public MyStack(int maxsize) {
        	arr = new long[maxsize];
        	top = -1;
        }
        
        /**
         * 添加数据
         */
        public void push(int value) {
        	// 由于top默认等于-1，所以没压栈一个元素，top就自增
        	arr[++top] = value;
        }
        
        /**
         * 移除数据
         */
        public long pop() {
        	// 由于栈特点，移除元素每次都是移除最上面的那一个
        	return arr[top--];
        }
        
        /**
         * 查看数据：查看数据和pop不同
         */
        public long peek() {
        	//只能查看最上面那个元素
        	return arr[top];
        }
        
        /**
         * 判断是否为空
         */
        public boolean isEmpty() {
        	return top == -1; // 为-1说明没有元素就为空
        }
        
        /**
         * 判断栈是否满了
         */
        public boolean isFull() {
        	return top == arr.length - 1;
        }
    }

测试下方法

package stack;
    
    public class TestMyStack {
    
    	public static void main(String[] args) {
    		MyStack ms = new MyStack(4);
    		
    		ms.push(2);
    		ms.push(23);
    		ms.push(51);
    		ms.push(39);
            
    		System.out.println(ms.isEmpty());
    		System.out.println(ms.isFull());
    		
    		//弹栈两个元素
    		ms.pop();
    		ms.pop();
    		//查找当前top元素是多少
    		System.out.println(ms.peek());
    		System.out.println(ms.isFull());
    	}
    }

运行结果：

false
    true
    23
    false

2、队列

package queue;
    
    public class MyQueue {
    	//队列底层也是数组实现
    	long[] arr;
    	//有效数据大小
    	int elements;
    	//队头
    	int front;
    	//队尾
    	int end;
    	
    	/**
    	 * 默认构造
    	 */
    	public MyQueue() {
    		arr = new long[10];
    		elements = 0;
    		front = 0;
    		end = -1;
    	}
        
    	/**
    	 * 有参构造
    	 */
    	public MyQueue(int maxsize) {
    		arr = new long[maxsize];
    		elements = 0;
    		front = 0;
    		end = -1;
    	}
    	
    	/**
    	 * 添加数据,从队尾插入
    	 */
    	public void insert(long value) {
    		arr[++end] = value;
    		elements++;
    	}
    	
    	/**
    	 * 删除数据,从队头删除,每次从对头删除一个出去
    	 */
    	public long remove() {
                    elements--;
    		return arr[front++];
    	}
    	
    	/**
    	 * 查看数据,从队头查看
    	 */
    	public long peek() {
    		return arr[front];
    	}
    	
    	/**
    	 * 判断是否为空
    	 */
    	public boolean isEmpty() {
    		return elements == 0;
    	}
    	
    	/**
    	 * 判断是满了
    	 */
    	public boolean isFull() {
    		return elements == arr.length;
    	}
    }

测试封装的队列类

package queue;
    
    public class TestMyQueue {
    
    	public static void main(String[] args) {
    		MyQueue mq = new MyQueue(4);
    		
    		mq.insert(3);
    		mq.insert(9);
    		mq.insert(15);
    		mq.insert(26);
    		//此时队列内容是：3,9,15,26
    		System.out.println(mq.isEmpty());
    		System.out.println(mq.isFull());
    		//删除数据
    		mq.remove(); //变成 9，15,26
    		//查看队头数据
    		System.out.println(mq.peek()); // 9
    		System.out.println(mq.isFull()); 
    	}
    
    }

运行结果

false
    true
    9
    true

3、循环队列

先执行以下代码，看看发生什么。

运行结果：

Exception in thread "main" false
    true
    9
    true
    java.lang.ArrayIndexOutOfBoundsException: 4
    	at queue.MyQueue.insert(MyQueue.java:37)
    	at queue.TestMyQueue.main(TestMyQueue.java:21)

上面显示21行有问题，也就是insert方法在调用的时候出现了数组索引越界异常。很奇怪，明明这个队列有4个元素，之前删除了一个，后面再次插入一个为什么就报索引越界异常呢。

/**
    	 * 添加数据,从队尾插入
    	 */
    	public void insert(long value) {
    		arr[++end] = value;
    		elements++;
    	}

问题就在上面代码。因为end的初始值为-1，前面代码我们进行了四次insert操作，也就是end在第四次之后值为3，如果进行第五次，也就是21行代码报错地方再次调用insert方法，这个时候end的值应该为4（也就是说队列有5个元素），但是这个队列实际长度在初始化的时候设置为4，所以越界异常了。你可以在上面代码elements++前面插入一个打印end的语句，调试下代码就知道了。

为了解决这个问题，我们这里要改成循环队列。循环队列的作用就是，当发现插入元素之后判断end是否等于数组的长度-1，如果满足，end就恢复变成-1，这样形成循环。

package queue;
    
    public class MyQueue {
    	//队列底层也是数组实现
    	long[] arr;
    	//有效数据大小
    	int elements;
    	//队头
    	int front;
    	//队尾
    	int end;
    	
    	/**
    	 * 默认构造
    	 */
    	public MyQueue() {
    		arr = new long[10];
    		elements = 0;
    		front = 0;
    		end = -1;
    	}
        
    	/**
    	 * 有参构造
    	 */
    	public MyQueue(int maxsize) {
    		arr = new long[maxsize];
    		elements = 0;
    		front = 0;
    		end = -1;
    	}
    	
    	/**
    	 * 添加数据,从队尾插入
    	 */
    	public void insert(long value) {
    		if(end == arr.length - 1) {
    			end = -1;
    		}
    		arr[++end] = value;
    		elements++;
    	}
    	
    	/**
    	 * 删除数据,从队头删除,每次从对头删除一个出去
    	 */
    	public long remove() {
    		long value = arr[front++];
    		if(front == arr.length) {
    			front = 0;
    		}
    		elements--;
    		return value;
    	}
    	
    	/**
    	 * 查看数据,从队头查看
    	 */
    	public long peek() {
    		return arr[front];
    	}
    	
    	/**
    	 * 判断是否为空
    	 */
    	public boolean isEmpty() {
    		return elements == 0;
    	}
    	
    	/**
    	 * 判断是满了
    	 */
    	public boolean isFull() {
    		return elements == arr.length;
    	}
    }

注意上面修改了end 和front变成初始化值的if判断。在Insert和remove方法中。

package queue;
    
    public class TestMyQueue {
    
    	public static void main(String[] args) {
    		MyQueue mq = new MyQueue(4);
    		
    		mq.insert(3);
    		mq.insert(9);
    		mq.insert(15);
    		mq.insert(26);
    		//此时队列内容是：3,9,15,26
    		System.out.println(mq.isEmpty());
    		System.out.println(mq.isFull());
    		//删除数据
    		mq.remove(); //变成 9，15,26
    		System.out.println(mq.elements); // 查看队列长度
    		//查看队头数据
    		System.out.println(mq.peek()); // 9
    		System.out.println(mq.isFull()); 
    		
    		mq.insert(61);
    		System.out.println(mq.elements); //查看队列长度
    	}
    
    }

运行结果：

false
    true
    3
    9
    false
    4

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1NDE5NDY_size_16_color_FFFFFF_t_70]: /images/20220310/fcdcd617372d48a79c650d75f95c9468.png