Java实现链栈和链队列

朴灿烈づ我的快乐病毒、 2022-05-15 03:12 155阅读 0赞

继上次更新，同样将以前C++的实现转换为Java实现。

先来看看链栈

import javax.print.attribute.Size2DSyntax;
    
    
    public class LinkStack<E> {
    
    	private Node<E> top; //栈顶元素
    	private int size;
    	class Node<E>{
    		E e;
    		Node<E> nextNode;
    		public Node(E e, Node<E> nextNode) {
    			super();
    			this.e = e;
    			this.nextNode = nextNode;
    		}
    
    	}
    
    	/**
    	 * 初始化一个空栈
    	 */
    	public LinkStack() {
    		top=null; 
    	}
    
    	/**
    	 * 返回栈的长度
    	 * @return
    	 */
    	public int length(){
    		return size;
    	}
    
    	/**
    	 * 入栈
    	 * @param e 入栈元素值
    	 * @return
    	 */
    	public boolean push(E e) {
    		Node<E> node = new Node<E>(e, top);
    		top=node;
    		size++;
    		return true;
    	}
    
    	/**
    	 * 判空
    	 * @return
    	 */
    	public boolean empty() {
    		return size==0;
    	}
    
    	/**
    	 * 查看栈顶元素，不出栈
    	 * @return
    	 */
    	public Node<E> peek() {
    		if (empty()) {
    			throw new RuntimeException("空栈异常！");
    		}else {
    			return top;
    		}
    	}
    	/**
    	 * 出栈
    	 * @return 栈顶元素
    	 */
    	public Node<E> pop(){
    		if(empty()){
                throw new RuntimeException("空栈异常！");
            }else {
            	Node<E> node=top;   //暂存栈顶元素
        		top=top.nextNode;   //元素下移
        		node.nextNode=null; //删除
        		size--;          
        		return node;
    		}
    	}
    
    
    
    }

再来看看链队列

public class LinkQueen<E> {
    	private Node front;//队头元素
    	private Node rear;//队尾元素
    	private int size=0; //队列长度
    	
    	/**
    	 * 节点
    	 * @author U
    	 *
    	 * @param <E>
    	 */
    	class Node<E>{
    		E e;
    		Node<E> nextNode;
    		public Node(E e, Node<E> nextNode) {
    			super();
    			this.e = e;
    			this.nextNode = nextNode;
    		}
    	}
     
    	/**
    	 * 初始化一个空队列
    	 * 
    	 */
    	public LinkQueen(){
    		front=null;
    		rear=null;
    	}
        /**
         * 判空
         * @return
         */
    	public boolean empty(){
    		return size==0;
    	}
    	/**
    	 * 长度
    	 * @return
    	 */
    	public int length(){
    		return size;
    	}
    	/**
    	 * 插入
    	 * @param e
    	 * @return
    	 */
    	public boolean add(E e) {
    		if (empty()) {   //还是空队列时
    			front=new Node<E>(e, null);
    			rear=front;
    		}else{
    			Node<E> node =  new Node<E>(e, null);
    			rear.nextNode=node;
    			rear=node;
    		}
    		size++;
    		return true;
    	}
    	 //返回队首元素，但不删除
        public Node<E> peek(){
            if(empty()){
                throw new RuntimeException("空队列异常！");
            }else{
                return front;
            }
        }
        
        /**
         * 出队列
         * @return 返回出队列的值
         */
        public Node<E> pop() {
    		if (empty()) {
                throw new RuntimeException("空队列异常！");
    		}else {
    			Node node=front; //保存队首元素，方便返回
    			front=front.nextNode; //移动队首指针
    			node.nextNode=null;  
    			size--;   
    			return node;  //返回出队列的元素
    		}
    	}
    }