深入理解数据结构（1）—用链表实现栈

深藏阁楼爱情的钟 2024-02-20 09:17 38阅读 0赞

> 栈是一种数据结构，链表也是一种数据结构。它们都是由基础的语法实现的。
> 
> 如果一个数据结构可以用另外的数据结构来实现，那么可以有力的证明——“数据结构是一种思想”，是一种讲语法组合起来实现某种功能的手段

## 一、栈的特点——要实现哪些功能？ ##

既然要用链表来模拟栈，那么要实现哪些功能？

1.  栈是一种特殊的线性表，只允许在固定一端进行插入和删除元素操作
2.  后进先出

那么对于这两个特性，我们可以做出如下设想：

> 在使用单链表的情况下，从头部插入——模拟入栈，头部删除——模拟出栈。同时这样操作满足了时间复杂度O（1）
> 
> 每次向栈中插入一个元素，就是向这个链表前端插入一个新的“head”；
> 
> 每次从栈中弹出一个元素，就是从链表头部删除一个“head”，然后“head = head.next”；

二、代码实现

public class MyStack {
        /*创建链表的节点*/
        static class Node{
            public int val;
            public Node next;
    
            public Node(int val){
                this.val = val;
            }
        }
        public Node head;
        public int size;
    
        //实现入栈方法
        public void push(int val){
            Node node = new Node(val);
            /*如果此时链表中没有节点，那么将node设为head，并将有效元素个数size加1
            * 如果链表中已经有元素的话，将node节点头插到head节点前，并设为head*/
            if (size == 0){
                head = node;
            }else {
                node.next = head;
                head = node;
            }
            size++;
        }
        //实现出栈方法
        /*返回当前头节点的值，并将头节点后移*/
        public int pop(){
            int h = head.val;
            head = head.next;
            size--;
            return h;
        }
        //获取栈顶元素的peek方法
        public int peek(){
            return head.val;
        }
        //判断栈是否为空
        public boolean empty(){
            return size == 0;
        }
    
        public static void main(String[] args) {
            MyStack stack = new MyStack();
            stack.push(12);
            stack.push(24);
            stack.push(26);
            stack.push(58);
            int b = stack.pop();
            int a = stack.peek();
            System.out.println(b);
            System.out.println(a);
    
        }
    }