链表LinkedList实现栈(Java)

╰半橙微兮° 2023-07-01 08:42 168阅读 0赞

# 链表LinkedList实现栈 #

**LinkedList.java（链表）**[详细请看链表LinkedList(Java)][LinkedList_Java]

public class LinkedList<E> {
        
    	private class Node {
        // 内部类将节点设为私有 隐藏实现细节
    		public E e;// 元素
    		public Node next;// next指针
    
    		public Node(E e, Node next) {
        
    			this.e = e;
    			this.next = next;
    		}
    
    		public Node(E e) {
        
    			this(e, null);
    		}
    
    		public Node() {
        
    			this(null, null);
    		}
    
    		@Override
    		public String toString() {
        
    			return e.toString();
    		}
    	}
    
    	private Node dummyhead; // 设置虚拟头节点
    	int size;// 链表中元素个数
    
    	public LinkedList() {
        
    		// TODO Auto-generated constructor stub
    		dummyhead = new Node(null, null);
    		size = 0;
    	}
    
    	// 获取链表中的元素个数
    	public int getSize() {
        
    		return size;
    	}
    
    	// 返回链表是否为空
    	public boolean isEmpty() {
        
    		// TODO Auto-generated method stub
    		return size == 0;
    	}
    
    	// 在链表的index位置添加一个元素
    	public void add(int index, E e) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("index越界");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    
    		Node prev = dummyhead;// 创建一个索引与dummyhead指向一致
    		for (int i = 0; i < index; i++) // 需要找到索引的前一个位置
    			prev = prev.next;// prev在链表中移动
    		// Node node = new Node(e);//创建一个node
    		// node.next = prev.next;//node.next指向prev.next
    		// prev.next = node;//prev.next指向node
    		prev.next = new Node(e, prev.next);// 等于 上面3行代码
    		size++;
    
    	}
    
    	// 在链表尾部添加元素
    	public void addLast(E e) {
        
    		add(size, e);
    	}
    
    	// 在链表头添加元素
    	public void addFirst(E e) {
        
    		// TODO Auto-generated method stub
    		add(0, e);
    	}
    
    	// 获得链表的第index个元素
    	public E get(int index) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("index越界");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		Node cur = dummyhead.next;// 寻找第index个元素
    		for (int i = 0; i < index; i++)
    			cur = cur.next;
    		return cur.e;// 返回cur.e就是第index个元素
    	}
    
    	// 获得第一个元素
    	public E getFirst() {
        
    		return get(0);
    	}
    
    	// 获得最后一个元素
    	public E getLast() {
        
    		return get(size - 1);
    	}
    
    	// 修改链表的第index个元素
    	public void set(int index, E e) {
        
    		if (index < 0 || index >= size) {
        
    			try {
        
    				throw new Exception("index越界");
    			} catch (Exception e1) {
        
    				// TODO Auto-generated catch block
    				e1.printStackTrace();
    			}
    		}
    		Node cur = dummyhead.next;// 寻找第index个元素
    		for (int i = 0; i < index; i++)
    			cur.e = e;
    	}
    
    	// 查找链表中是否有元素e
    	public boolean contains(E e) {
        
    		Node cur = dummyhead.next;
    		while (cur != null) {
        
    			if (cur.e.equals(e)) // 判断cur.e是否等于用户传来的e
    				return true;
    			cur = cur.next;// 依次遍历
    		}
    		return false;
    	}
    
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		// Node cur = dummyhead.next;
    		// while (cur != null) {
        
    		// res.append(cur + "->");
    		// cur = cur.next;
    		// }
    		for (Node cur = dummyhead.next; cur != null; cur = cur.next)
    			res.append(cur + "->");
    		res.append("NULL");
    		return res.toString();
    	}
    
    	// 删除链表中第index个元素，并返回删除的元素
    	public E remove(int index) {
        
    		if (index < 0 || index > size) {
        
    			try {
        
    				throw new Exception("index越界");
    			} catch (Exception e) {
        
    				// TODO Auto-generated catch block
    				e.printStackTrace();
    			}
    		}
    		Node prev = dummyhead;
    		for (int i = 0; i < index; i++)
    			prev = prev.next;
    		Node retNode = prev.next;// prev.next与retNode所指的都是要删除的节点
    		prev.next = retNode.next;// prev.next跳过retNode直接指向retNode.next
    		retNode.next = null;// 垃圾回收retNode.next
    		size--;
    		return retNode.e;
    	}
    
    	// 删除链表中第一个元素，返回删除的元素
    	public E removeFirst() {
        
    		return remove(0);
    	}
    
    	// 删除链表中最后一个元素，返回删除的元素
    	public E removeLast() {
        
    		return remove(size - 1);
    	}
    }

**Stack.java（栈接口）**

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

**LinkedListStack.java（链表实现的栈）**

public class LinkedListStack<E> implements Stack<E>{
        
    	
    	private LinkedList<E> list;
    	public LinkedListStack() {
        
    		// TODO Auto-generated constructor stub
    		list = new LinkedList<>();
    	}
    	
    	@Override
    	public int getSize() {
        
    		// TODO Auto-generated method stub
    		return list.getSize();
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		// TODO Auto-generated method stub
    		return list.isEmpty();
    	}
    
    	@Override
    	public void push(E e) {
        
    		// TODO Auto-generated method stub
    		list.addFirst(e);
    	}
    
    	@Override
    	public E pop() {
        
    		// TODO Auto-generated method stub
    		return list.removeFirst();
    	}
    
    	@Override
    	public E peek() {
        
    		// TODO Auto-generated method stub
    		return list.getFirst();
    	}
    	
    	public String toString() {
        
    		StringBuilder res = new StringBuilder();
    		res.append("Stack：top ");
    		res.append(list);
    		return res.toString();
    	}
    }

**测试（main）**

public class StackTest {
        
    	public static void main(String[] args) {
        
    		LinkedListStack<Integer> stack = new LinkedListStack<>();
    		for (int i = 0; i < 5; i++) {
        
    			stack.push(i);
    			System.out.println(stack);
    		}
    		
    		stack.pop();
    		System.out.println(stack);
    	}
    }

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

## 链表实现的栈的时间复杂度 ##

**入栈：O(1)  
出栈：O(1)  
查询栈顶元素：O(1)**  
  
**链表栈需要不停的重新new Node，需要在内存中开发内存，如果操作越多，耗时会越长**

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