天道不一定酬所有勤
但是,天道只酬勤

我是一个栈

本站采用[知识共享署名-非商业性使用-相同方式共享 许可协议]进行许可,转载请在正文明显处注明原文地址
阿里大牛珍藏架构资料,点击链接免费获取

我是一个栈,先来跟你介绍一下我的家族,我的家族是一个很古老的家族,家族成员很多,外界称呼我们这个家族为数据结构。我们是计算机世界中存储和组织数据的。数据结构家族在计算机世界中是至关重要的,因为我们家族功能的强大,现代编程语言及其API中都有我们家族成员的身影。

我的家族是一个庞大的家族。家族中也有几大分支,比如说树、图、堆、散列表等。各个分支都有不同的能力,所以很多人选择适当的数据结构是一项很重要的工作。我们家族和算法家族是世交,基本上所有重要场合两家都会一起出现。

我叫栈,我的爸爸叫数组,我的妈妈叫链表,我的双胞胎弟弟叫队列。我们这个家庭是整个数据结构家族中比较重要的家庭。

和你说过了,我们数据结构家族是计算机世界中储存和组织数据的。我的家族之所以这么强大,就是因为我们要应付各种需求,提供不同的数据存储方式。我的四个家庭成员分别可以解决不同的数据存取需求。

数组

说起我的爸爸——数组,他是数据结构家族的族长,人们都说他是数据结构大家族的根基。很多编程语言都内置数组。爸爸是个很富有的人,他有很多土地。每当有人找他来存储数据的时候,他都会预先划分出一块连续的土地(连续的内存),然后把别人交给他的数据按顺序存储在这些连续的土地中,当别人来取这些数据的时候,需要提供给数组要取哪块土地中的数据(数组的位置索引),然后数组就可以直接去那块土地中把数据取出来,交给需要读取这个数据的人。并不是所有数据数组都能帮忙存储的,父亲只会帮别人存储相同类型的数据。

数组

我的家族的所有人都支持几个基本的操作:插入、删除、读取。

因为数组爸爸在存储数据的时候,是按照顺序保存的,他保存数据的土地是一块一块相连的。那么,他的特点就是寻址读取数据比较容易,但是插入和删除比较困难。这个其实比较好理解。读取容易的原因是只要你告诉数组你要从哪块土地读取数据,他就会直接去那块土地中把数据取出来给你。插入和删除比较麻烦,主要是因为这些存储数据的空间都是连着的,比如编号为0-1-2-3-4这五块土地中都保存了数据,但是现在你要往1中插入一块数据,那就意味着从1开始,后面的所有土地中的数据都要往后移一个位置。这是很大的工作量啊。

数组1

链表

人们都说,男女搭配,干活不累。由于数组爸爸有寻址容易,插入和删除困难的问题,他在找老婆的时候特意找了一个和自己互补的姑娘——链表。链表妈妈的特点正好是寻址困难,插入和删除容易。

在帮助别人存储数据这件事上,链表的方式和数组有很大不同。数组是提前划分了一大片连续的土地,用来存储数据。但是链表不是这么做的,因为链表妈妈家里并没有数组爸爸家里那么富有。他的数据存储并不是连续的,能这么做的原因是妈妈存储数据的土地中有两块区域,一块用来保存数据,一块用来记录下一个数据保存在哪块土地中(指针)。这样,别人找他存储数据的时候,她就要根据指示先找到下一块空余的土地,然后把数据保存在里面。链表这样的数据存储方式可以把一些碎片空间利用起来。

链表

通过上面的这种保存数据的方式,链表在插入和删除数据的时候比较容易,比如编号为0-1-2-3-4这五块土地中都保存了数据,但是现在你要往1中插入一块数据,那么只需要依次更改0号土地和1号土地中记录下一块土地地址的值就行了。对于其他的数据存储没有任何影响。但是,如果你想从数据中取出一块数据那可就麻烦了,因为这意味着链表妈妈要帮你从第一块土地开始挨个帮你找。一直找到你要的数据为止。

链表1

我和我的胞弟

栈,也就是我,一个英俊潇洒的数据结构。我和队列是一堆孪生兄弟。我们两个都可以用数组和链表来实现。虽然是双胞胎,但是我们两个都是有性格的,我们要求别人存储数据和取出数据的顺序要按照我们的规矩来。

我的原则是:先进后出(栈)

stack

弟弟的原则是:先进先出(队列)

queue

我给你举个例子你就明白了,我和弟弟每个人都有一个管子,用来帮你们保存数据,当然这个管子可能是用数组爸爸是实现的也可能是链表妈妈实现的。我们握住管子的两头,我的这个管子只能通过管子左面的口子放入东西,也只能从左面的口子取出东西。右面的口子是不开的。而弟弟队列呢,他的管子的左面的口子放东西,管子的右面的口子取东西。

爸爸妈妈是如何生出我和弟弟的

上面说过了,栈和队列都是可以通过数组或者链表实现的。当然了,父母创造孩子,天经地义嘛。那么,先来看看我是如何实现的。作为一种数据结构,我接口有isEmpty()、size()、push()、pop()、peek()以及迭代。

先来看看如何通过数组实现栈:

public class Stack<Item> implements Iterable<Item> {
    private Item[] a;         // 数组表示栈,栈顶在最大的下标。
    private int n;            // 栈内元素的个数

    /**
     * 初始化一个空栈
     */
    public Stack() {
        a = (Item[]) new Object[2];
        n = 0;
    }

    /**
     * 判断栈内是否有元素
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * 返回栈内元素个数
     */
    public int size() {
        return n;
    }

    // 改变栈的大小
    private void resize(int capacity) {
        assert capacity >= n;
        // 注意不能直接创建泛型数组
        Item[] temp = (Item[]) new Object[capacity];
        for (int i = 0; i < n; i++) {
            temp[i] = a[i];
        }
        a = temp;
       // 也可以选择下面这种方式改变数组大小
       // a = java.util.Arrays.copyOf(a, capacity);
    }

    /**
     * 压入元素
     */
    public void push(Item item) {
        //先判断n的大小,如果栈满则改变栈的大小
        if (n == a.length) resize(2*a.length);    
        a[n++] = item;                
    }

    /**
     * 弹出并返回元素
     */
    public Item pop() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        Item item = a[n-1];
        a[n-1] = null;   //防止对象游离
        n--;
        // 如果有必要则调整栈的大小
        if (n > 0 && n == a.length/4) resize(a.length/2);
        return item;
    }


    /**
     * 返回但不弹出栈顶元素
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return a[n-1];
    }

    /**
     * 返回一个可以进行先进后出迭代的迭代器
     */
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }

    // 用内部类实现迭代器接口,实现从栈顶往栈底的先进后出迭代,没有实现remove()方法。 
    private class ReverseArrayIterator implements Iterator<Item> {
        private int i;
        public ReverseArrayIterator() {
            i = n-1;
        }
        public boolean hasNext() {
            return i >= 0;
        }
        public void remove() {
            throw new UnsupportedOperationException();
        }
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            return a[i--];
        }
    }


    /**
     * 测试
     */
    public static void main(String[] args) {
        Stack<String> stack = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) stack.push(item);
            else if (!stack.isEmpty()) StdOut.print(stack.pop() + " ");
        }
        StdOut.println("(" + stack.size() + " left on stack)");
    }
}

再来看看如何使用链表实现栈:

public class Stack<Item> implements Iterable<Item> {
    private Node<Item> first;     //栈顶节点
    private int N;                // 栈内元素数量

    // 辅助类Node,用于形成链表
    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    /**
     * 初始化栈
     */
    public Stack() {
        first = null;
        N = 0;
    }

    /**
     * 判断栈是否为空
     */
    public boolean isEmpty() {
        return first == null;
        //return N == 0;
    }

    /**
     * 返回栈内元素数量
     */
    public int size() {
        return N;
    }

    /**
     * 压入元素
     */
    public void push(Item item) {
        Node<Item> oldfirst = first;
        first = new Node<Item>();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    /**
     * 弹出元素
     */
    public Item pop() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        Item item = first.item;        // 需弹出的元素
        first = first.next;            // 删除头节点
        N--;
        return item;       
    }


    /**
     * 返回但不弹出元素
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");
        return first.item;
    }

    /**
     * 从栈顶到栈底打印元素
     */
    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    }


    /**
     * 实现Iterable接口
     */
    public Iterator<Item> iterator() {
        return new ListIterator<Item>(first);
    }

    // 实现Iterator接口用于迭代,没有实现remove方法
    private class ListIterator<Item> implements Iterator<Item> {
        private Node<Item> current;

        //初始化时,current指向栈顶
        public ListIterator(Node<Item> first) {
            current = first;
        }

        public boolean hasNext() {
            return current != null;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }


    /**
     * 测试
     */
    public static void main(String[] args) {
        Stack<String> s = new Stack<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) s.push(item);
            else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
        }
        StdOut.println("(" + s.size() + " left on stack)");
    }
}

同样作为数据结构的弟弟,也有些接口需要实现:isEmpty()、size()、enqueue()、dequeue()、peek()以及迭代。队列和栈不同的是,入列和出列是在两个地方,所以需要维护两个变量来表示队头和队尾。

使用数组实现队列:

public class Queue<Item> implements Iterable<Item> {
    private Item[] q;       
    private int N;          // 队列中元素的数量
    private int first;      // 队头元素的下标
    private int last;       // 队尾元素的后一个位置的下标,也就是元素入列时可以放置的位置


    /**
     * 初始化队列,此时头尾下标重合
     */
    public Queue() {
        q = (Item[]) new Object[2];
        N = 0;
        first = 0;
        last = 0;
    }

    /**
     * 依旧用N判断队列是否为空
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * 队列中元素数量
     */
    public int size() {
        return N;
    }

    // 调整数组大小
    private void resize(int max) {
        assert max >= N;
        Item[] temp = (Item[]) new Object[max];
        //注意这里:把N个元素放入总大小为max的队列(max>=N)
        //因为循环使用数组,从first开始的第i个元素可能保存在了first
        //前面(即last在first前面)。
        for (int i = 0; i < N; i++) {
            temp[i] = q[(first + i) % q.length];
        }
        q = temp;
        //把小队列按顺序复制到大队列后重置队头和队尾
        first = 0;
        last  = N;
    }

    /**
     * 元素入列
     */
    public void enqueue(Item item) {
        if (N == q.length) resize(2*q.length);  
        q[last++] = item;   // 元素入列
        if (last == q.length) last = 0;  // 如果last超出数组下标,把last置零,循环利用数组
        N++;
    }

    /**
     * 元素出列
     */
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = q[first];
        q[first] = null;       // 防止对象游离
        N--;
        first++;
        if (first == q.length) first = 0; // 循环利用数组,下一个队头在下标为0的地方
        if (N > 0 && N == q.length/4) resize(q.length/2); 
        return item;
    }

    /**
     * 返回队头元素但不出列
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return q[first];
    }
    /**
     * 实现Iterable接口
     */
    public Iterator<Item> iterator() {
        return new ArrayIterator();
    }

    //实现迭代器
    private class ArrayIterator implements Iterator<Item> {
        //维护一个i用于迭代
        private int i = 0;
        public boolean hasNext()  { return i < N; }
        public void remove()      { throw new UnsupportedOperationException();  }

        //直接利用first进行遍历,注意可能存在数组的循环利用
        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = q[(i + first) % q.length];
            i++;
            return item;
        }
    }

   /**
     * 测试
     */
    public static void main(String[] args) {
        Queue <String> q = new Queue <String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) q.enqueue(item);
            else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
        }
        StdOut.println("(" + q.size() + " left on queue)");
    }

}

使用链表实现队列:

public class Queue<Item> implements Iterable<Item> {
    private Node<Item> first;    // 队头节点
    private Node<Item> last;     // 队尾节点(注意和上面的last区分,last并不是队尾元素的下标)
    private int N;               // 队列元素的数量

    // 辅助类Node
    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    /**
     * 初始化队列
     */
    public Queue() {
        first = null;
        last  = null;
        N = 0;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;     
    }

    /**
     * 返回但不删除头元素
     */
    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return first.item;
    }

    /**
     * 元素入列
     */
    public void enqueue(Item item) {
        //记录尾节点
        Node<Item> oldlast = last;
        //创建新的尾节点
        last = new Node<Item>();
        last.item = item;
        last.next = null;
        //如果队列是空的,将first置为last,因为这时候队列中只有一个元素
        if (isEmpty()) first = last;
        //否则执行正常的在尾节点插入新节点的操作
        else           oldlast.next = last;
        N++;
    }

    /**
     *元素出列 
     */
    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        //队头元素出列
        Item item = first.item;
        first = first.next;
        N--;
        //如果这时候队列为空,表示原来只有一个元素,这时候也将last置为null
        if (isEmpty()) last = null;  
        return item;
    }

    public String toString() {
        StringBuilder s = new StringBuilder();
        for (Item item : this)
            s.append(item + " ");
        return s.toString();
    } 
    public Iterator<Item> iterator()  {
        return new ListIterator<Item>(first);  
    }

    // 实现迭代
    private class ListIterator<Item> implements Iterator<Item> {

        private Node<Item> current;
        //要实现迭代,我们只需要维护一个节点,并在开始的时候将它置为first
        public ListIterator(Node<Item> first) {
            current = first;
        }

        public boolean hasNext()  { return current != null;}
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next; 
            return item;
        }
    }


    /**
     * 测试
     */
    public static void main(String[] args) {
        Queue<String> q = new Queue<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) q.enqueue(item);
            else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
        }
        StdOut.println("(" + q.size() + " left on queue)");
    }
}

我是一个栈,我的双胞胎弟弟叫队列。我的爸爸是数组,我的妈妈是链表。 你们可以使用数组和链表来实现栈和队列。

好了,今天关于我和我的家族的故事就先给你介绍到这里了。偷偷告诉你一个秘密,其实我和弟弟之间是可以互相转换的。也就是说可以使用栈来实现队列,同样也可以使用队列来实现栈。关于这个小秘密,我下次再给你介绍哦。

参考资料

“数组、堆栈”与“链表、队列”的区别

赞(0)
如未加特殊说明,此网站文章均为原创,转载必须注明出处。HollisChuang's Blog » 我是一个栈
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

HollisChuang's Blog

联系我关于我