栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

自己实现一个简单的栈

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

自己实现一个简单的栈

引

什么是栈?

  • 栈其实就是一种数据结构,特点是先进后出,后进先出
  • 栈的底层就是一个数组

什么是栈帧?

  • 调用函数的时候,我们会为这个函数在 JVM 上开辟一块内存空间,这就叫做栈帧。

  • 先调用的函数在栈底,后调用的函数在栈顶,这个过程就叫压栈

一、使用数组

时间复杂度:

  • 入栈:O(1)
  • 出栈:O(1)

代码:

public class MyStack1 {

    private int[] elem;
    private int usedSize;
    
    public TestDemo2() {
        // 数组初始容量设置为 10
        this.elem = new int[10];
    }

    public void push(int val) {
        if (isFull()) {
            // 满了就扩容,这里是二倍扩容
            elem = Arrays.copyOf(elem,elem.length * 2);
        }
        elem[usedSize++] = val;
    }
    
    public int pop() {
        if (isEmpty()) {
            // 为空就返回 -1, 这里也可以抛异常
            return -1;
        }
        return elem[usedSize--];
    }

    public int peek() {
        if (isEmpty()) {
            // 为空就返回 -1, 这里也可以抛异常
            return -1;
        }
        return elem[usedSize];
    }
    
    public int size() {
        return usedSize;
    }
    
    public boolean isEmpty() {
        return usedSize == 0;
    }
    
    private boolean isFull() {
        return elem.length == usedSize;
    }
    
}
二、使用链表

时间复杂度

  • 尾插法: 入栈:O(N) 出栈:O(N)

  • 头插法:入栈:O(1) 出栈:O(1)

  • 因此用链表实现栈的时候,用头插法来入栈和出栈。

代码:

// 使用链表来实现一个栈
public class MyStack2 {

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    private Node head;
    private Node last;

    public void push(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            this.head = newNode;
            this.last = newNode;
        } else {
            newNode.next = this.head;
            this.head = newNode;
        }
    }

    public int pop() {
        if (isEmpty()) {
            // 如果为空就返回 -1
            return -1;
        }
        int val = this.head.val;
        this.head = this.head.next;
        return val;
    }

    public int peek() {
        if (isEmpty()) {
            // 如果为空就返回 -1
            return -1;
        }
        return this.head.val;
    }

    public int size() {
        Node cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

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

}
三、使用队列

OJ: 用队列实现栈

时间复杂度:

出栈:入栈:O(1) 出栈:O(1)

思路:需要准备两个队列

  1. 入栈:入到不为空的队列
  2. 出栈:从不为空的队列出

代码:

public class MyStack {

    Queue queue1;
    Queue queue2;

    public MyStack() {
        // 初始化队列
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        // 那个队列不为空就入到那个队列
        // 都为空就默认入 queue1
        if (!queue1.isEmpty()) {
            queue1.offer(x);
        } else if (!queue2.isEmpty()) {
            queue2.offer(x);
        } else {
            queue1.offer(x);
        }
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        int size = 0;
        if (!queue1.isEmpty()) {
            // 计算 size 即队列中的元素个数 - 1
            // 将剩下的最后一个元素弹出
            size = queue1.size() - 1;
            for (int i = 0; i < size; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        } else {
            size = queue2.size() - 1;
            for (int i = 0; i < size; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

    public int top() {
        if (empty()) return -1;
        int size;
        int x = 0;
        if (!queue1.isEmpty()) {
            size = queue1.size();
            for (int i = 0; i < size; i++) {
                x = queue1.poll();
                queue2.offer(x);
            }
        }
        else {
            size = queue2.size();
            for (int i = 0; i < size; i++) {
                x = queue2.poll();
                queue1.offer(x);
            }
        }
        return x;
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }

}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970963.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号