关于数据结构:栈与队列简介

44次阅读

共计 2595 个字符,预计需要花费 7 分钟才能阅读完成。

栈与队列和数组、链表、树这几种数据结构不太一样。栈与队列次要是做为程序员的工具来应用,它们次要做为构思算法的辅助工具,而不是齐全的数据存储工具。

它们的生命周期比数组那些要短得多,在程序执行期间它们才会被创立,工作执行完就会被销毁。

一 栈

栈是一种只能在一端进行插入和删除数据的数据结构,这一端被称为栈顶(top)。其特点简略来讲就是先进后出。栈的次要机制能够用数组来实现,当然也能够用链表来实现。

用数组实现栈,并实现罕用操作——出栈、入栈、查看元素(只能查看栈顶元素)、判断栈是否为空等操作。

public class StackTest {private long[] arr;
    // 栈顶
    private int top;

    public StackTest(){arr = new long[10];
        top = -1;
    }
    public StackTest(int maxsize){arr = new long[maxsize];
        top = -1;
    }

    /**
     * 增加数据
     * @param value
     */
    public void push(int value){arr[++top] = value;
    }

    /**
     * 移除数据
     * @return
     */
    public long pop() {return arr[top--];
    }

    /**
     * 查看数据
     * @return
     */
    public long peek(){return arr[top];
    }
    public boolean isEmpty(){return top == -1;}

    /***
     * 判断是否满了
     * @return
     */
    public boolean isFull(){return top == arr.length-1;}
}

栈的所有操作复杂度都为 O(1),栈的操作不依赖栈中元素大小,栈不须要挪动和比拟操作。

二 队列

队列的特点是先进先出。队列也是用数组来实现。

用数组实现队列,并实现罕用操作——出队、入队、查看元素、判断队列是否为空等操作。

public class QueueTest {private long[] arr;
    // 无效数据的大小
    private int elements;
    // 队头
    private int front;
    // 队尾
    private int end;

    public QueueTest(){arr = new long[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    public QueueTest(int maxsize){arr = new long[maxsize];
        elements = 0;
        front = 0;
        end = -1;
    }

    /**
     * 插入数据
     * @param value
     */
    public void insert(long value){arr[++end] = value;
        elements++;
    }

    /**
     * 删除数据
     * @return
     */
    public long remove(){
        elements--;
        return arr[front++];
    }

    /**
     * 查看数据,从对头查看
     * @return
     */
    public long peek(){return arr[front];
    }

    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpty(){return elements == 0;}

    public boolean isFull(){return elements == arr.length;}
}

队列的插入、删除等操作的复杂度都为 O(1)。

三 优先级队列

优先级队列和一般队列一样,也是一个队头,一个队尾,从队头移除元素,优先级队列中,数据项是有序的,这样插入数据的时候就会依据某种规定去比拟,而后插入到队列适合的地位。因而,优先级队列插入的复杂度为 O(N),删除和查看元素的复杂度为 O(1)。

用数组实现优先级队列,并实现罕用操作——出队、入队、查看元素、判断队列是否为空等操作。

public class FirstQueueTest {private long[] arr;
    // 无效数据的大小
    private int elements;
    // 队头
    private int front;
    // 队尾
    private int end;

    public FirstQueueTest(){arr = new long[10];
        elements = 0;
        front = 0;
        end = -1;
    }

    public FirstQueueTest(int maxsize){arr = new long[maxsize];
        elements = 0;
        front = 0;
        end = -1;
    }

    /**
     * 插入数据
     * @param value
     */
    public void inser(long value){if(elements == 0){arr[++end] = value;
            elements++;
        }else{
            // 按某种规定进行比拟,这里应用 value 的大小比拟,按从小到大排序
            for(int i = elements-1;i>=0;i--){if(value<arr[i]){arr[i+1] = arr[i];
                    arr[i] = value;
                }else{arr[i+1] = value;
                    break;
                }
            }
            elements++;
            end++;
        }
    }

    /**
     * 删除数据
     * @return
     */
    public long remove(){
        elements--;
        return arr[front++];
    }

    /**
     * 查看数据,从对头查看
     * @return
     */
    public long peek(){return arr[front];
    }

    /**
     * 判断是否为空
     * @return
     */
    public boolean isEmpty(){return elements == 0;}

    public boolean isFull(){return elements == arr.length;}
}

四 总结

  1. 栈的特点是先进后出,栈只能查看栈顶的一个元素
  2. 队列的特点是先进先出,只能查看队头的一个元素
  3. 优先级队列插入一条元素,均匀须要挪动 2 / N 个元素,因而插入的复杂度为 O(N)
  4. 栈和队列,能够用数组实现,也能够用其余数据结构实现
  5. 栈和队列是为了实现某些工作,手动结构的数据结构

点关注、不迷路

如果感觉文章不错,欢送 关注 点赞 珍藏,你们的反对是我创作的能源,感激大家。

如果文章写的有问题,请不要悭吝,欢送留言指出,我会及时核查批改。

如果你还想更加深刻的理解我,能够微信搜寻「Java 旅途」进行关注。回复「1024」即可取得学习视频及精美电子书。每天 7:30 准时推送技术文章,让你的下班路不在孤单,而且每月还有送书流动,助你晋升硬实力!

正文完
 0