欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java实现链式栈

程序员文章站 2022-03-25 18:48:25
...

数组、链表、树等数据结构适用于存储数据库应用中的数据记录,它们常常用于记录那些现实世界的对象和活动的数据,便与数据的访问:插入、删除和查找特定数据项
而栈和队列更多的是作为程序员的工具来使用。他们主要作为构思算法的辅助工具,而不是完全的数据存储工具。这些数据结构的生命周期比那些数据库类型的结构要短很多。在程序操作执行期间它们才被创建,通常它们去执行某项特殊的任务,当任务完成后就被销毁
栈和队列的访问是受限制的,即在特定时刻只有一个数据项可以被读取或删除
栈和队列是比数组和其他数据结构更加抽象的结构,是站在更高的层面对数据进行组织和维护
栈的主要机制可用数组来实现,也可以用链表来实现。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。

栈只允许访问一个数据项:即最后插入的数据。移除这个数据项后才能访问倒数第二个插入的数据项。它是一种“后进先出”的数据结构。
栈最基本的操作是出栈(Pop)、入栈(Push),还有其他扩展操作,如查看栈顶元素,判断栈是否为空、是否已满,读取栈的大小等

/**
 * 实现一个链式栈结构
 * @param <T>
 */
class LinkStack<T>{
    // 链表的第一个节点充当栈顶元素
    private Entry<T> bottom; // 栈底
    private int count; // 记录链表节点的个数

    public LinkStack(){
        bottom = new Entry<>(null, null);
    }

    // 入栈操作
    public void push(T val){
        Entry<T> node = new Entry<>(val, bottom.next);
        bottom.next = node;
        count++;
    }

    // 出栈,并把出栈元素的值返回
    public T pop(){
        if(empty())
            return null;
        T val = bottom.next.data;
        bottom.next = bottom.next.next;
        count--;
        return val;
    }

    // 查看栈顶元素
    public T peek(){
        if(empty())
            return null;
        return bottom.next.data;
    }

    // 判断栈空
    public boolean empty(){
        return bottom.next == null;
    }

    // 返回栈里面元素的个数
    public int size(){
        return this.count;
    }

    /**
     * 链表的节点类型定义
     * @param <T>
     */
    static class Entry<T>{
        T data;
        Entry<T> next;

        public Entry(T data, Entry<T> next) {
            this.data = data;
            this.next = next;
        }
    }
}


public class LinkStackTest {
    public static void main(String[] args) {
        LinkStack<Integer> ls = new LinkStack<>();
        ls.push(23);
        ls.push(21);
        ls.push(56);
        ls.push(84);
        System.out.println(ls.size());
        while(!ls.empty()){
            System.out.print(ls.pop() + " ");
        }

        System.out.println();
    }

运行结果:
4
84 56 21 23