栈的两种实现方式

青旅半醒 2023-06-24 15:24 27阅读 0赞

##### 一、数组实现栈 #####

1.  首先需要定义一个数组来储存栈中的数据，并定义一个变量来记录数组中储存元素的个数，编写一个构造方法来构造一个长度为十得数组。

//先顶i有一个数组来存储栈中的元素
    	private Object array[];
    	//定义数组中存储元素的个数
    	private int size;
    	
    	//构造后一个长度与为10的数组
    	public MyStack() {
        
    		array = new Object[10];
    	}

1.  判断栈是否为空  
    只需要判断记录数组储存元素数量的变量是否为零即可。

//判断栈是否为空
       public boolean isEmple() {
        
       	return size == 0;
       }

1.  扩充数组  
    判断数组是否已经满了，如果满了则需要扩充数组，定义一个值为10的长度变量，调用Arrays中的copyOf(array, newsize)方法来扩充数组

//判断数组是否已经满了，如果满了则扩充数组
    	public void addarray(int size) {
        
    		if(size>array.length) {
        
    			int newsize = 10;
    			array = Arrays.copyOf(array, newsize);
    		}
    	}

1.  向栈中添加元素  
    先调用addarray方法查看当前元素是否能添加进去，如果数组已满则扩充数组长度。最后直接将需要添加的元素赋给数组的第size++个元素。

//向栈中添加元素
    	public void put(E e) {
        
    		//先判断数组是否能存储下当前元素,如果没有的话会自动扩充
    		addarray(size+1);
    		array[size++] = e;
    	}

5.查看栈顶元素  
先判断栈是否为空，如果为空直接返回false,反之直接返回数组的最后一个元素。

//查看栈顶元素
    	public E peek() {
        
    		if(isEmple()) {
            //如果栈为空
    			return null;
    		}
    		return (E) array[size-1];
    	}

1.  取出栈顶元素  
    直接调用peek方法，该方法会返回栈顶元素，直接将它赋给一个新的变量，然后将数组的最后一个元素也就是栈顶元素赋值为空，然后返回这个变量。

//取出栈顶元素
    	public E pop() {
        
    		E e = peek();
    		array[size-1] = null; //将栈顶赋为空
    		size--;    //数组长度-1
    		return e;
    	}

1.  测试：

public static void main(String[] args) {
        
    		MyStack<Integer> a = new MyStack<Integer>();
    		a.put(1);
    		a.put(2);
    		a.put(3);
    		a.put(4);
    		System.out.println("栈顶元素为："+a.pop());
    		System.out.println("栈顶元素为："+a.pop());
    		System.out.println("栈顶元素为："+a.pop());
    	}

1.  运行截图：  
    ![在这里插入图片描述][20191224124747893.png]

##### 二、链表实现栈 #####

1.  节点类：定义节点的值，下一个节点和新节点的构造方法。

public class Node<E> {
        
    	
    	E data;
    	Node<E> next;
    	public Node(E data) {
        
    		this.data = data;
    	}
    
    }

1.  实现类：先定义一个栈顶节点，判断栈知否为空，直接返回栈顶节点是否为空。

//定义一个栈顶节点
    	Node<E> top =null;
    	
    	//判断栈是否为空
    	public boolean isEmple() {
        
    		return top == null;
    	};

1.  向栈中添加元素  
    先创建一个新节点，并判断栈是否为空，如果为空的话，直接将新节点赋给栈顶节点，反之将栈顶节点赋给它的后继节点，再将新节点赋给栈顶节点，并返回栈顶结点。

//向栈中添加节点
    	public E put(E e) {
        
    		//创建一个新节点
    		Node<E> newNode = new Node<E>(e);
    		if(isEmple()) {
           //判断如果栈为空的话将新元素添加给栈顶节点
    			top = newNode;
    		}
    		newNode.next = top;   //将栈顶节点节点赋给新节点的下一个节点
    		top = newNode;    //将新节点赋给栈顶结点节点
    		return (E) top;
    	}

1.  查看栈顶元素：  
    先判断栈是否为空，如果为空返回空，反之返回栈顶节点值。

//查看栈顶元素
    	public E peek() {
        
    		if(isEmple()) {
        
    			return null;
    		}
    		return top.data;
    	}

1.  取出栈顶元素：  
    直接调用peek方法，该方法会返回栈顶节点的值，将其赋给一个新变量，然后将栈顶节点的后继节点赋给它本身，最后返回这个新变量。

//取出栈顶元素
    	public E pop() {
        
    		E e = peek();
    		top = top.next;   //将栈顶节点的后继节点赋给栈顶节点
    		return e;
    	}

1.  测试：

public static void main(String[] args) {
        
    		NodeStack<Integer> s = new NodeStack<Integer>(); 
    		s.put(1);
    		s.put(2);
    		s.put(3);
    		s.put(4);
    		System.out.println("栈顶元素："+s.pop());
    		System.out.println("栈顶元素："+s.pop());
    		System.out.println("栈顶元素："+s.pop());
    	}

1.  运行截图：  
    ![在这里插入图片描述][20191224131002218.png]

[20191224124747893.png]: https://img-blog.csdnimg.cn/20191224124747893.png
[20191224131002218.png]: https://img-blog.csdnimg.cn/20191224131002218.png