美文网首页
栈的实现

栈的实现

作者: 毕丙伟 | 来源:发表于2017-07-11 21:15 被阅读0次

栈的特点:
先进后出,后进先出
除头尾节点之外,每个元素有一个前驱,一个后继。

图一 栈的示意图

实现功能:
判断非空、查询栈的长度、自动扩充栈的容量、push、pop、迭代
程序:
Item:是一个类型参数,用于表示用例将会使用的某种具体类型的象征性的占位符。(泛型)

package com.company;

import java.util.Iterator;

public class ResizingArrayStack<Item> implements Iterable<Item>{


    //这是一个模拟栈(后进先出)的小程序
    //实现判断非空、栈的大小、自动扩充容量、push、pop、迭代的功能

    private Item[] a = (Item[]) new Object[1];//栈元素

    private int N = 1;//表示栈的容量

    public Boolean isEmpty(){
        return N == 0;
    }

    public int length(){
        return N;
    }

    private void resize(int length){

        Item[] tempItem = (Item[]) new Object[length];//长度扩大两倍
        for(int i=0;i < length;i++){
            tempItem[i] = a[i];
        }
        a = tempItem;
    }

    //进
    public void push(Item i){
        if (N == a.length ){
            resize(2*a.length);
        }
        a[N++] = i;
    }

    //出
    public Item pop(Item i){
        Item item = a[--N];
        a[N] = null;
        if (N > 0 && N == a.length/4)
            resize(N/2);
        return item;
    }



    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }

    private class ReverseArrayIterator implements Iterator<Item> {
        private int i = N;
        @Override
        public boolean hasNext() {
            return i>0;
        }

        @Override
        public Item next() {
            return a[--i];
        }
    }
}

相关文章

  • 数据结构——栈和队列

    用数组实现栈和队列 用栈实现队列 用队列实现栈 栈和队列的经典算法题最小间距栈宠物收养所 数组实现栈和队列 用数组...

  • Swift 队列&栈 相关操作

    栈 LIFO(后进先出) 队列 FIFO(先进先出) 队列与栈相互的实现 栈 - 队列实现 队列 - 栈实现 相关...

  • Algorithm小白入门 -- 队列和栈

    队列和栈队列实现栈、栈实现队列单调栈单调队列运用栈去重 1. 队列实现栈、栈实现队列 队列是一种先进先出的数据结构...

  • 2018-07-09顺序表实现栈

    栈的实现 ——直接用顺序表(列表list)进行 栈结构实现 栈可以用顺序表实现,也可以用链表实现。 栈的操作 St...

  • 38_两个有趣的问题

    关键词:通过栈实现队列、通过队列实现栈 0. 通过栈实现队列 用栈实现队列等价于用后进先出的特性实现先进先出的特性...

  • 栈 Python实现

    栈的顺序表实现 栈的链接表实现

  • 算法-栈和队列算法总结

    栈和队列算法总结 1 模拟 1.1 使用栈实现队列 1.2 使用队列实现栈 2 栈的应用 2.1 栈操作 2.2 ...

  • 队列之-队列实现栈

    一、队列实现栈核心算法概述 之前已经描述过了用栈实现队列的功能,见栈系列之-实现队列,那么同样队列也可以用来实现栈...

  • 3. 栈的操作

    1. 栈的操作-c语言实现2. 栈操作的实现-顺序栈和链栈 3. 栈的实现与遍历4. c语言的函数调用栈5. 两个...

  • leecode刷题(26)-- 用栈实现队列

    leecode刷题(26)-- 用栈实现队列 用栈实现队列 使用栈实现队列的下列操作: push(x) -- 将一...

网友评论

      本文标题:栈的实现

      本文链接:https://www.haomeiwen.com/subject/tptvhxtx.html