[数据结构]栈的实现,双向链表与单向链表

末蓝、 2023-03-03 06:30 6阅读 0赞

I'm Shendi

下面是使用链表实现的栈(数组的太简单了)

单链表的

/**
     * 栈.
     * @author Shendi <a href='tencent://AddContact/?fromId=45&fromSubId=1&subcmd=all&uin=1711680493'>QQ</a>
     * @version 1.0
     */
    public class 栈<E> {
    	
    	private static class Node<E> {
    		E data;
    		Node<E> next;
    		public Node (E data, Node<E> next) {
    			this.next = next;
    			this.data = data;
    		}
    	}
    	
    	int size = 0;
    	
    	private Node<E> top;
    	
    	public E pop() {
    		if (top == null) return null;
    		Node<E> node = top;
    		top = top.next;
    		size--;
    		return node.data;
    	}
    	
    	public void push(E e) {
    		if (top == null) top = new Node<E>(e,null);
    		else {
    			Node<E> node = new Node<E>(e, top);
    			top = node;
    		}
    		size++;
    	}
    	
    	public static void main(String[] args) {
    		栈<Integer> z = new 栈<>();
    		z.push(1);
    		z.push(2);
    		z.push(3);
    		for (int i = 0;i < 3;i++) {
    			System.out.println(z.pop());
    		}
    		for (int i = 0;i < 3;i++) {
    			System.out.println(z.pop());
    		}
    	}
    	
    }

双链表的

/**
     * 栈.
     * @author Shendi <a href='tencent://AddContact/?fromId=45&fromSubId=1&subcmd=all&uin=1711680493'>QQ</a>
     * @version 1.0
     */
    public class 栈<E> {
    	
    	private static class Node<E> {
    		Node<E> prev;
    		E data;
    		Node<E> next;
    		public Node (Node<E> prev, E data, Node<E> next) {
    			this.prev = prev;
    			this.next = next;
    			this.data = data;
    		}
    	}
    	
    	int size = 0;
    	
    	private Node<E> top;
    	
    	public E pop() {
    		if (top == null) return null;
    		Node<E> node = top;
    		top = top.next;
    		size--;
    		return node.data;
    	}
    	
    	public void push(E e) {
    		if (top == null) top = new Node<E>(null,e,null);
    		else {
    			top.prev = new Node<E>(null, e, top);
    			top = top.prev;
    		}
    		size++;
    	}
    	
    	public static void main(String[] args) {
    		栈<Integer> z = new 栈<>();
    		z.push(1);
    		z.push(2);
    		z.push(3);
    		for (int i = 0;i < 3;i++) {
    			System.out.println(z.pop());
    		}
    		for (int i = 0;i < 3;i++) {
    			System.out.println(z.pop());
    		}
    	}
    	
    }