用单链表实现栈

首先要了解栈的机制,栈的执行逻辑是先入先出,如图所示。


栈结构动图.gif

每次入栈、出栈的动作都是操作在最上面的节点。
所以每次记录head 头节点就好,栈操作全部基于头节点来进行操作。

入栈操作: 创建一个新的节点cur,将新的节点设置为头节点,指向老的头节点head。
出栈操作: 记录第二个节点,删除头节点,并删除头节点指向下一个节点的引用。
返回当前头节点:返回头节点内容。不做其他操作。

//链表对象
public static class Node<V> {
   public V value;
   public Node<V> next;

   public Node(V v) {
      value = v;
      next = null;
   }
}
 
 //栈对象
 //<V> 使用了泛型,不了解的可以提前了解下。
 public static class MyStack<V> {
   private Node<V> head;
   private int size;

   public MyStack() {
      head = null;
      size = 0;
   }

   public boolean isEmpty() {
      return size == 0;
   }

   public int size() {
      return size;
   }
   /**
    *入栈操作
    */
   public void push(V value) {
      Node<V> cur = new Node<>(value);
      if (head == null) {
         head = cur;
      } else {
         cur.next = head;
         head = cur;
      }
      size++;
   }
     /**
    *出栈操作
    */
   public V pop() {
      V ans = null;
      if (head != null) {
         ans = head.value;
         head = head.next;
         size--;
      }
      return ans;
   }

   public V peek() {
      return head != null ? head.value : null;
   }

}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。