首页 > Java资讯 > 正文

Java编程基础之数据结构栈

2020-07-20 16:24:10
2103次动力节点

栈：一种仅允许在一端进行插入和删除操作的线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来），允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为后进先出表（LIFO,Last In First Out）。

栈一次只允许操作一个数据项，即最后插入的数据项。

下面是用Java数组实现的顺序存储结构的栈。

package cn.zhf.list;
 class MyStack {
    private int maxSize;//定义栈的最大容量
    private int[] stackArray;//以数组方式存储元素
    private int top;//栈顶
 
    //构造器，初始化
    public MyStack(int x){
        maxSize = x;
        stackArray = new int[x];
        top = -1;
    }
    //插入元素
    public void push(int x){
        stackArray[++top] = x;
    }
    //删除顶部元素
    public int pop(){
        return stackArray[top--];
    }
    //查看栈顶部元素
    public int peek(){
        return stackArray[top];
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return (top == -1);
    }
    //判断栈是否已满
    public boolean isFull(){
        return (top == maxSize-1);
    }
}

下面是使用链表实现的栈。

package cn.zhf.list;
//链表内存放的数据对象包装
public class Link {
    public int idata;//存放int 类型的数据
    public double ddata;//double类型的数据
    public Link next;//对下一个Link对象的引用
    public Link(int id, double dd) {
        idata = id;
        ddata = dd;
    }
    public void diaplay() {
        System.out.println(idata + "," + ddata);
    }
}
//链表
public class LinkList {
    private Link first;//链表中保存的数据
    public LinkList() {
        first = null;
    }
    public boolean isEmpty() {
        return (first == null);
    }
    //插入一个元素
    public void insertFirst(int id, double dd) {
        Link link = new Link(id, dd);
        link.next = first;//next元素链接first
        first = link;//first元素链接link
    }
    //删除一个元素
    public Link deleteFirst() {
        Link temp = first;
        first = first.next;
        return temp;
    }
    //显示链表的元素
    public void displayLink() {
        Link current = first;
        while (current != null) {
            current.diaplay();
            current = current.next;
        }
    }
}
//用链表实现的栈
public class LinkStack {
        private LinkList list;
        public LinkStack(){
            list = new LinkList();
        }
        public void push(int id,double dd){
            list.insertFirst(id, dd);
        }
        public Link pop(){
            return list.deleteFirst();
        }
        public boolean isEmpty(){
            return list.isEmpty();
        }
        public void display(){
            list.displayLink();
        }
    public static void main(String[] args) {
        LinkStack ls = new LinkStack();
        ls.push(1, 2.1);
        ls.push(2, 2.2);
        ls.push(3, 2.3);
        ls.display();
                ls.pop();
                ls.display();
    }
 
}

栈中的基本操作是：入栈、出栈和查看栈顶元素，以上两种实现方式不一样，但是方法名一样，实现的功能也相同，因此可以将Stack定义为一个接口，两个类分别实现这个接口，这样，对于调用者完全隐藏了实现的细节，但不影响使用，这大概就是接口的抽象优势。

Java编程基础之数据结构栈