动态数组实现栈(Java)

太过爱你忘了你带给我的痛 2023-06-30 06:50 4阅读 0赞

# 栈 #

**定义**  
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

*  栈是一种线性结构
 *  相比数组，栈对应的操作是数组的子集
 *  只能从一端添加元素，也只能从一端取出元素
 *  这一端称为"栈顶"

**栈的复杂度分析**

*  void push(E) 均摊复杂度O(1)
 *  E pop() 均摊复杂度O(1)
 *  E peek() 复杂度O(1)
 *  int getSize() 复杂度O(1)
 *  boolean isEmpty() 复杂度O(1)

**动态数组** [动态数组及均摊复杂度与防止复杂度震荡][Link 1]

//动态数组
    public class Arr<E> {
        
    	private E[] data;// 创建一个数组
    	private int size;// 数组中元素个数
    
    	// 自定义构造器初始化数组 capacity数组的长度
    	public Arr(int capacity) {
        
    		// TODO Auto-generated constructor stub
    		data = (E[]) new Object[capacity];
    		size = 0;
    	}
    
    	// 默认构造方法 capacity数组的长度=10
    	public Arr() {
        
    		// TODO Auto-generated constructor stub
    		this(10);
    	}
    
    	// 获取数组个数
    	public int getSize() {
        
    		return size;
    	}
    
    	// 获取数组长度
    	public int getCapacity() {
        
    		return data.length;
    	}
    
    	// 判断数组是否为空
    	public boolean isEmpty() {
        
    		return size == 0;
    	}
    
    	// 数组中添加元素 index是插入元素的位置，e是插入的元素，时间复杂度为O(n)
    	public void add(int index, E e) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("数组排列要求不能有空");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		// 数组扩容
    		if (size == data.length) {
        
    			try {
        
    				resize(2 * data.length); // 这里是扩容为原数组的2倍，Arraylist是扩容1.5倍
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		for (int i = size - 1; i >= index; i--) {
        
    			data[i + 1] = data[i];
    		}
    		data[index] = e;
    		size++;
    	}
    
    	// 数组扩容或者缩容,时间复杂度为O(n)
    	private void resize(int newcapcatity) {
        
    		// TODO Auto-generated method stub
    		E[] newData = (E[]) new Object[newcapcatity];
    		for (int i = 0; i < size; i++) {
        
    			newData[i] = data[i];
    		}
    		data = newData;
    	}
    
    	// 在数组末尾添加元素,时间复杂度为O(1)
    	public void addLast(E e) {
        
    		add(size, e);
    	}
    
    	// 在数组首部添加元素,时间复杂度为O(n)
    	public void addFirst(E e) {
        
    		add(0, e);
    	}
    
    	// 重写toString 使用字符串拼接
    	@Override
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		res.append(String.format("Array:size = %d, capacity = %d\n", size, data.length));
    		res.append('[');
    		for (int i = 0; i < size; i++) {
        
    			res.append(data[i]);
    			if (i != size - 1) {
        
    				res.append(',');
    			}
    		}
    		res.append(']');
    		return res.toString();
    	}
    	
    	//获取最后一个元素
    	public E getLast() {
        
    		return get(size - 1);
    	}
    
    	//获取第一个元素
    	public E getFirst() {
        
    		return get(0);
    	}
    
    	// 获取index位置的数组元素,时间复杂度为O(1)
    	E get(int index) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		return data[index];
    	}
    
    	// 修改数组元素,时间复杂度为O(1)
    	void set(int index, E e) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e3) {
        
    				// TODO Auto-generated catch block
    				e3.printStackTrace();
    			}
    		}
    		data[index] = e;
    	}
    
    	// 查询是否包含数组元素e,时间复杂度为O(n)
    	public boolean contains(E e) {
        
    		for (int i = 0; i < size; i++) {
        
    			if (data[i].equals(e))
    				return true;
    		}
    		return false;
    	}
    
    	// 查找数组元素e,时间复杂度为O(n)
    	public int find(E e) {
        
    		for (int i = 0; i < size; i++) {
        
    			if (data[i].equals(e))
    				return i;// 返回元素e的位置
    		}
    		return -1;// 找不到元素e，返回-1
    	}
    
    	// 删除指定位置index的数组元素,时间复杂度为O(n)
    	public E remove(int index) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index非法");
    			} catch (Exception e3) {
        
    				// TODO Auto-generated catch block
    				e3.printStackTrace();
    			}
    		}
    		//缩容  为了避免复杂度震荡，当size==capacity/4，再进行缩容
    		//new数组空间时候长度不能为0
    		if (size==data.length/4 && data.length/2 != 0) {
        
    			resize(data.length/2);
    		}
    		E ret = data[index];
    		for (int i = index + 1; i < size; i++) {
        
    			data[i - 1] = data[i];
    		}
    		size--;
    		data[size] = null;
    		return ret;// 返回删除的元素
    	}
    
    	// 数组删除首个元素,时间复杂度为O(n)
    	public E removeFirst() {
        
    		return remove(0);
    	}
    
    	// 数组删除最后一个元素,时间复杂度为O(1)
    	public E removeLast() {
        
    		return remove(size - 1);
    	}
    
    	// 数组删除元素e,时间复杂度为O(n)
    	public void removeElement(E e) {
        
    		int index = find(e);
    		if (index != -1) {
        
    			remove(index);
    		} else {
        
    			System.out.println("数组中没有元素e");
    		}
    	}
    }

**栈接口**

public interface Stack<E> {
        
    	int getSize();//获取栈中元素个数
    	boolean isEmpty();//判断栈是否为空
    	void push(E e);//入栈
    	E pop();//获取栈顶元素并且出栈
    	E peek();//查看栈顶元素
    }

**栈**

public class ArrayStack<E> implements Stack<E> {
        
    	Arr<E> array;
    
    	public ArrayStack(int capacity) {
        
    		// TODO Auto-generated constructor stub
    		array = new Arr<>(capacity);
    	}
    
    	public ArrayStack() {
        
    		// TODO Auto-generated constructor stub
    		array = new Arr<>();
    	}
    
    	@Override
    	public int getSize() {
        
    		// TODO Auto-generated method stub
    		return array.getSize();
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		// TODO Auto-generated method stub
    		return array.isEmpty();
    	}
    
    	public int getCapacity() {
        
    		return array.getCapacity();
    	}
    
    	@Override
    	public void push(E e) {
        
    		// TODO Auto-generated method stub
    		array.addLast(e);
    	}
    
    	@Override
    	public E pop() {
        
    		// TODO Auto-generated method stub
    		return array.removeLast();
    	}
    
    	@Override
    	public E peek() {
        
    		// TODO Auto-generated method stub
    		return array.getLast();
    	}
    
    	@Override
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		res.append("Stack: ");
    		res.append('[');
    		for (int i = 0; i < array.getSize(); i++) {
        
    			res.append(array.get(i));
    			if (i != array.getSize() - 1) {
        
    				res.append(",");
    			}
    		}
    		res.append("] top");
    		return res.toString();
    	}
    }

**测试**

public class Test {
        
    	public static void main(String[] args) {
        
    		ArrayStack<Integer> stack = new ArrayStack<>();
    
    		for (int i = 0; i < 5; i++) {
        
    			stack.push(i);// 入栈
    			System.out.println(stack);
    			System.out.println("栈顶元素为："+stack.peek());// 查看栈顶元素
    		}
    		stack.pop();// 出栈
    		System.out.println(stack);
    	}
    }

**运行结果**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]

[Link 1]: https://blog.csdn.net/weixin_44190113/article/details/103978491
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200115155652786.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDE5MDExMw==,size_16,color_FFFFFF,t_70