前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Stack栈

Stack栈

作者头像
羊羽shine
发布2019-05-28 13:38:16
3350
发布2019-05-28 13:38:16
举报
文章被收录于专栏:Golang开发
栈概述

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

栈顶top

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

栈底bottom

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

压栈PUSH

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

弹栈POP

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

代码语言:javascript
复制
public interface Stack<Item> {
    int getSize();
    boolean isEmpty();
    void push(Item e);
    Item pop();
}

基本操作

代码语言:javascript
复制
 @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];
    }

通过链表实现栈

代码语言:javascript
复制
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();
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.05.12 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 栈概述
  • 栈顶top
  • 栈底bottom
  • 压栈PUSH
  • 弹栈POP
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档