Stack栈

栈概述

又称堆栈,它是运算受限的线性表,其限制是仅允许在一端进行插入和删除操作。按照先进后出(First In Last Out )的原则存储数据

栈顶top

允许进行插入和删除操作的一段被称为栈顶,栈的入口、出口的都是栈的顶端位置。

栈底bottom

无法进行数据操作的一端被称为栈底

压栈PUSH

就是存元素。即,把元素存储到栈的顶端位置,栈中已有元素依次向栈底方向移动一个位置。

弹栈POP

就是取元素。即,把栈的顶端位置元素取出,栈中已有元素依次向栈顶方向移动一个位置。

public interface Stack<Item> {
    int getSize();
    boolean isEmpty();
    void push(Item e);
    Item pop();
}

基本操作

 @Override
    public int size() {
        return top;
    }

    @Override
    public boolean isEmpty() {
        return top==0;
    }

    @Override
    /**
     * 压栈
     */
    public void push(Item e) {
        if (size()== stack.length){
            expandCapacity();
        }
        stack[top]=e;
        top++;
    }

    /**
     * 栈扩容
     */
    private void expandCapacity(){
        stack = Arrays.copyOf(stack,stack.length*2);
    }

    @Override
    /**
     * 出栈 返回当前栈顶元素
     */
    public Item pop() {
        if (isEmpty())
            throw  new EmptyStackException();
        top--;
        Item item = stack[top];
        return item;
    }

    @Override
    public Item peek() {
        if (isEmpty())
            throw  new EmptyStackException();
        return stack[top-1];
    }

通过链表实现栈

public class LinkedStack <Item> implements Iterator<Item> {

    private class Node{
        Item item;
        Node next;

        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
    private Node first;//栈顶元素
    private int size;//栈元素总数
    private Node currNode;

    public void push(Item item){
        first = new Node(item,first);
        currNode = first;
        size++;
    }

    public Item pop(){
        Node currFirst = first;
        first = currFirst.next;
        currNode = first;
        size--;
        return currFirst.item;
    }

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

    public int getSize() {
        return size;
    }

    @Override
    public boolean hasNext() {
        return currNode!=null;
    }

    @Override
    public Item next() {
        Item item = currNode.item;
        currNode = currNode.next;
        return item;
    }
    
    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Hadoop序列化

    把内存中对象转换成字节序列(或其他数据传输协议)以便于存储到磁盘(持久化)和网络传输

    羊羽shine
  • Java基础——变量和常量

    标识符 标识符就是为程序代码中的变量,常量,方法,类,接口等指定的含有一定特殊含义的名称。跟我们世界万物的所拥有的名称或者我们每个人的姓名类型。标识符可以是任...

    羊羽shine
  • Go基础——function函数

    我们以写一个计算商品价格的函数为例,输入参数是单件商品的价格和商品的个数,两者的乘积为商品总价,作为函数的输出值。

    羊羽shine
  • Spring Security 实战干货:动态权限控制(下)实现

    Spring Security 实战干货:内置 Filter 全解析[1] 中提到的第 32 个 Filter 不知道你是否有印象。它决定了访问特定路径应该具备...

    码农小胖哥
  • MyBatis设计思想(4)——缓存模块

    相信大家对于缓存都不陌生,MyBatis也提供了缓存的功能,在执行查询语句时首先尝试从缓存获取,避免频繁与数据库交互,大大提升了查询效率。MyBatis有所谓的...

    张申傲
  • 剑指Offer-变态跳台阶

    package Recursion; /** * 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳...

    武培轩
  • java之struts2的action优化配置

    当一个Action处理类中处理多个业务时,action的配置 文件将会急剧增加,导致配置文件很臃肿的问题。

    Vincent-yuan
  • Java Concurrent CountDownLatch

    CountDownLatch 用于使一组线程(1 or n)等待一个外部任务的完成。很多人将它称为闭锁,可以理解为锁的就是那些线程,然后需要一个外部任务的完成来...

    邹志全
  • 每天一算:Two Sum II

    示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 i...

    五分钟学算法
  • leetcode-217-Contains Duplicate(使用排序来判断整个数组有没有重复元素)

    Given an array of integers, find if the array contains any duplicates.

    chenjx85

扫码关注云+社区

领取腾讯云代金券