如何使用Java数组和链表实现栈

小编给大家分享一下如何使用Java数组和链表实现栈，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

一、何为栈？

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈可以类比成现实生活中的弹夹或者羽毛球桶

二、用数组实现栈

用数组模拟栈的思路分析如图：

定义一个top变量（指针）表示栈顶初始化为-1.
2.定义一个变量来记录栈的大小。
3.入栈操作有数据加入到栈中：top++; arr[top]=value;
4.出栈操作： int value=arr[top]; top–; return value;

下面看完整代码示例：

class Stack{    public int maxsize;//栈的大小    public int top=-1;//栈顶    public int[] arr;    public Stack(int maxsize) {        this.maxsize = maxsize;        arr=new int[maxsize];    }    //判断栈是否为空    public boolean isEmpty(){        return top==-1;    }    //判断栈是否满    public boolean isFull(){        return top==maxsize-1;    }    //添加一个元素    public void push(int value){        if(isFull()){            throw new RuntimeException("栈满");        }        top++;        arr[top]=value;    }    //弹出一个元素    public int pop(){        if(isEmpty())            throw new RuntimeException("栈空");        int value=arr[top];        top--;        return value;    }    //遍历栈中的元素    public void traverse(){        if (isEmpty()){            return;        }        //需要从栈顶开始显示数据        for(int i = top; i >= 0 ; i--) {            System.out.printf("stack[%d]=%d\n", i, arr[i]);        }        }    }

入栈操作 top++;arr[top]=value;其实可以直接改写为arr[++top]=value;
出栈操作可以将 int value=arr[top]; top–;return value;改为return arr[top–];

三、链表实现栈

思路分析：

入栈操作：用一个临时节点保存当前栈顶节点，将入栈的新节点作为栈顶元素，并将next域指向原来的旧节点。 node temp=top; top.setNext(temp);

出栈操作：先判断栈是否为空，不为空则将top节点的数据返回，并将top指向top的下一个next域：top=top.getNext();

public class LinkedListStack<V> {      static class Node<V>{        private V data;        private Node<V> next;        public V getData() {            return data;        }        public void setData(V data) {            this.data = data;        }        public Node<V> getNext() {            return next;        }        public void setNext(Node<V> next) {            this.next = next;        }    }    public int stackSize;//栈内元素的个数    public Node<V> top;//栈顶元素    public LinkedListStack() {        stackSize = 0;        top = null;    }    //入栈    public void push(V element){        Node<V> temp=top;        top=new Node<>();        top.setData(element);        top.setNext(temp);        stackSize++;    }    //出栈    public V pop(){        if (isEmpty())            throw new RuntimeException("empty stack");        V value=top.getData();        //栈顶指向下一个元素        top=top.getNext();        stackSize--;        return value;    }    //查看栈顶元素    public V peek(){        return top.getData();    }    //判断是否为空    public boolean isEmpty(){        return stackSize==0;    }    //查看栈内元素个数    public int getStackSize(){        return stackSize;    }    }

四、测试

public class Test {    public static void main(String[] args) {        LinkedListStack<String> stack = new LinkedListStack<>();        stack.push("a");        stack.push("b");        stack.push("c");        System.out.println(stack.pop());        System.out.println(stack.peek());        System.out.println(stack.getStackSize());    }}测试结果:cb2

Java有哪些集合类

Java中的集合主要分为四类：1、List列表：有序的，可重复的；2、Queue队列：有序，可重复的；3、Set集合：不可重复；4、Map映射：无序，键唯一，值不唯一。

以上是“如何使用Java数组和链表实现栈”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注编程网精选频道！