【数据结构】堆栈、队列的原理及java实现

系统管理员 2022-08-21 06:48 222阅读 0赞

一、堆是一个运行时数据区，通过new等指令创建，不需要程序代码显式释放  
<1>优点：  
可动态分配内存大小，生存周期不必事先告诉编译器，Java垃圾回收自动回收不需要的数据；  
<2>缺点：  
运行时需动态分配内存，数据存取速度较慢。  
如：

String str = new String(“abc”);
    String str2 = new String(“abc”);

![这里写图片描述][20160421191345891]

二、栈(stack)又名堆栈，它是一种先进后出(FILO)的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。  
<1>优点：  
存取速度比堆快，仅次于寄存器，栈数据可以共享；  
<2>缺点：  
存在栈中的数据大小与生存期必须是确定的，缺乏灵活性。

String str = “abc”;  
String str2 = “abc”;

表的含义如下图所示：  
![这里写图片描述][20160421191426691]

![这里写图片描述][20160421191435660]

下面介绍两种栈的实现方式：  
1.采用链表中节点的方式实现：

public class MyStackNode<E> {
    
        Node<E> top = null;
    
        public boolean isEmpty() {
            return top == null;
        }
    
        public void push(E data) {
            Node<E> newNode = new Node<E>(data);
            newNode.next = top;
            top = newNode;
        }
    
        public E pop() {
            if (this.isEmpty())
                return null;
            E data = top.data;
            top = top.next;
            return data;
        }
    
        public E peek() {
            if (isEmpty()) {
                return null;
            }
            return top.data;
        }
    }

2.采用数组的方式实现：

public class MyStackArry<E> { 
        private Object[] stack;
        private int size;
    
        public MyStackArry() {
            stack = new Object[10];
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public E peek() {
            if (isEmpty())
                return null;
            return (E) stack[size - 1];// 如果有元素就返回最后一个
        }
    
        /** * 移除栈顶部元素移除 * * @return */
        public E pop() {
            E e = peek();// 保存最后一个元素的备份
            stack[size - 1] = null;// 给数组最后一个元素赋null
            size--;
            return e;
        }
    
        /** * 把项压入栈顶部 * * @param item * @return */
        public E push(E item) {
            ensureCapacity(size + 1);
            stack[size++] = item;
            return item;
        }
    
        /** * 检查容量是否足够，不够再原有的数组基础创建新的数组 * * @param size */
        public void ensureCapacity(int size) {
            int len = stack.length;
            if (size > len) {
                // int newLen = 10;
                // stack = Arrays.copyOf(stack, newLen);
                // 如果栈满，则创建空间为当前栈空间两倍的栈
                Object[] temp = stack;
                stack = new Object[2 * stack.length];
                System.arraycopy(temp, 0, stack, 0, temp.length);
            }
        }
    
        /** * 返回对象在堆栈中的位置，以1 为基数 * * @param o * @return */
        public int search(Object o) {
            int index = lastIndexOf(o);
            return index == -1 ? index : size - index;
        }
    
        /** * 查找下标的方法 * * @param o * @return */
        private int lastIndexOf(Object o) {
            if (isEmpty()) {
                throw new EmptyStackException(); // 如果数组为空，就抛出一个自定义异常
            }
            // 当传进来的元素为空时
            if (o == null) {
                for (int i = size - 1; i >= 0; i--) {
                    if (stack[i] == null) {
                        return i;
                    }
                }
                // 不为空时
            } else {
                for (int i = size - 1; i >= 0; i--) {
                    if (o.equals(stack[i])) {
                        return i;
                    }
                }
            }
            return -1; // 没有找到，返回-1
        }
    
        // 自定义异常
        private static class EmptyStackException extends RuntimeException { 
            public EmptyStackException() {
                super("堆栈为空");
            }
        }

三、队列 是一种先进先出的线性表。其限制仅在表的一端（尾端）进行插入，另一端（首端）进行删除的线性表，先进先出FIFO。  
![这里写图片描述][20160421191449066]  
Quene类尚不在java集合框架中，因此它有很大的灵活性，为了能够进行代码重用，我们试着通过继承（is-a关系）或者合成（have-a关系）一些实现了List接口的类来定义Queue类。直观的选择是ArrayList和LinkedList。  
1.第一种实现方式：LinkedList插入删除效率比较高，可以实现队列的尾部插入和头部删除只需常量次调用，我们首先选择LinkedList来实现Queue。  
这里我们采用采用合成（have-a关系）的方法，通过包含一个LinkedList字段来定义一个Queue类。  
实现方式如下：

public class MyQueueLink<E> {
        private LinkedList<E> list;
    
        public MyQueueLink() {
            list = new LinkedList<E>();
        }
       //入队
        public  void put(E e) {
            list.addLast(e);
        }
       //出队
        public  E pop() {
            return list.removeFirst();
        }
    
        public  boolean isEmpty() {
            return list.isEmpty();
        }
    
        public  int size() {
            return list.size();
        }
       //获得队列的第一个元素
        public  E front() {
            return list.getFirst();
        }
    }

2.第二种可选择的实现方式，用数组的方式实现

public class MyQueneArry {
        protected Object[] data;
        protected int size, head, tail;
    
        public MyQueneArry() {
            final int INTTIAN_LENGTH = 100;
            data = new Object[INTTIAN_LENGTH];
            size = 0;
            head = 0;
            tail = -1;
        }
    
        public int size() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        public Object front() {
            if (size == 0)
                throw new NoSuchElementException();
            return data[head];
        }
    //入队
        public void enquene(Object element) {
            if (size == data.length) {
                Object[] oldData = data;
                data = new Object[data.length * 2];
                System.arraycopy(oldData, head, data, 0, oldData.length - head);
                if (head > 0)
                    System.arraycopy(oldData, 0, data, head + 1, tail - 1);
                head = 0;
                tail = oldData.length - 1;
            }
            tail = (tail + 1) % data.length;
            size++;
            data[tail] = element;
        }
    //出队
        public Object dequene() {
            if (size == 0)
                throw new NoSuchElementException();
            Object element = data[head];
            head = (head + 1) % data.length;
            return element;
        }
    
        public static void main(String[] args) {
            MyQueneArry q = new MyQueneArry();
            for (int i = 0; i < 18; i++) {
                q.enquene(i);
            }
            System.out.println("队列长度：" + q.size());
            System.out.println("队列首元素：" + q.dequene());
            System.out.println("队列首元素：" + q.dequene());
        }
    }

[20160421191345891]: /images/20220724/22c74a4c11fd430dbc998e6ffa04bc99.png
[20160421191426691]: /images/20220724/50bacc2b98834e17bfba37dca13afeb5.png
[20160421191435660]: /images/20220724/aeda19edfd874b19941f050c51049e1d.png
[20160421191449066]: /images/20220724/938eff18a8fc4bb6a9794a9e341dc117.png