MENU

数据结构(一)栈、队列、数组及链表

July 20, 2018 • Code

前言:对数据结构中栈、队列、数组及链表作简单介绍。

数据结构

来自百科:

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

简单来说,数据结构就是一种抽象数据集合,并且在同一集合中的元素存在一定的关系

说「抽象」是因为这种集合关系在计算机内部是不存在的(物理上),只存在于逻辑内存中,并最终通过一定的手段映射到物理机中。

常见的数据结构有数组、链表、队列、栈、树、图等。

数组 & 链表

  • 数组和链表都是线性存储结构。

数组

结构示意图:

数组是最常见的数组结构,用来表示逻辑上一块连续的内存空间,这块内存可以对应物理机中的不连续内存。内存空间中按一定大小划分内存单元,依次存放数据。

特点

随机访问能力强

数组中内存单元连续,并且每个内存单元大小固定,所以通过内存首地址及距内存首地址的相对偏移量可以直接计算出所有内存单元内存地址,随机访问能力强,查找容易,时间复杂度为 O(1)。

删除元素代价大

数组中内存单元存在连续性,所以当需要删除数组中一个元素时,需要将后面的元素向前移,以保证连续性。

  • 因此删除元素最好的情况是在数组的末尾进行操作,时间复杂度是 O(1)。
  • 最坏的情况是在数组开头操作,时间复杂度为 O(n)。
  • 平均时间复杂度为 O(n)。
动态扩容困难

因为数组内存空间是在一开始就确定并分配,并且需要连续,所以一旦容量大小确定下来就很难进行动态扩展。

链表

链表不同于数组,链表是将非连续的内存块通过指针连结起来,形成一条链。

在逻辑上不连续的内存块在物理内存中也可能是连续的。

特点

增删内存单元快

删除元素

新增元素

可看出,新增与删除元素在链表都只需要 O(1) 的时间复杂度。

随机查找性能差

因为链表中某一内存单元的地址只保存在上一个内存单元的指针中,所以随机查找元素时只能遍历整条链。时间复杂度:

  • 最好为 O(1),所查找元素在链表首部。
  • 最坏为 O(n),所查找元素在链表尾部。
  • 平均为 O(n)。
容易动态扩展

与数组相反,链表的增删元素只与局部节点有关,所以动态扩展空间相对容易。

种类

单链表

单链表如图所示,由包含数据及下一结点的指针构成。但一般为了处理方便,需要在头部增加头指针节点。

循环链表

双链表

栈 & 队列

  • 只在栈顶一端操作。
  • 实现先进后出语义

数组实现栈

public class StackByArray<T> implements Iterable<T> {

    /**
     * 表示一个栈,栈顶为最大下标索引
     */
    private T[] stacks;

    /**
     * 记录数组栈中元素的个数
     */
    private int num;

    /**
     * 无参初始化一个空栈,大小默认为8
     */
    public StackByArray() {
        this(8);
    }

    /**
     * 根据参数初始化一个空栈,大小为传入大小
     */
    public StackByArray(int num) {
        this.stacks = (T[]) new Object[num];
        this.num = 0;
    }

    /**
     * 检查栈是否为空
     *
     * @return 为空返回true,否则返回false
     */
    public boolean isEmpty() {
        return num == 0;
    }

    public int size() {
            return num;
        }

        public void resize(int capacity) {
            assert capacity >= num;
            stacks = Arrays.copyOf(stacks, capacity);
        }

        public void push(T element) {
            if (num == stacks.length) {
                resize(2 * stacks.length);
            }
            stacks[num++] = element;
    }

    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack underflow");
        }
        T temp = stacks[num - 1];

        // 防止对象游离
        stacks[num - 1] = null;
        num --;
        if (num > 0 && num <= stacks.length / 4) {
            resize(stacks.length / 2);
        }

        return temp;

    }

    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack underflow");
        }
        return stacks[num - 1];

    }


    @Override
    public Iterator<T> iterator() {
        return new ReverseArrayIterator();
    }


    private class ReverseArrayIterator implements Iterator<T> {

        int i = num;

        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return stacks[--i];
        }
    }


    /**
     * 测试
     */
    public static void main(String[] args) {
        StackByArray<String> stack = new StackByArray<String>();
        Scanner sc = new Scanner(System.in);



        while (sc.hasNextLine()){
            String s = sc.nextLine();
            if (!"-".equals(s)){
                stack.push(s);
            } else if (!stack.isEmpty()) {
                System.out.println(stack.pop() + " ");
            }
        }

        System.out.println("(" + stack.size() + " left on stack)");
    }
}

链表实现栈

/**
 * @author kbrx93
 */
public class StackByList<T> implements Iterable<T> {

    /**
     * 记录栈中元素个数
     */
    private int size = 0;

    /**
     * 指向链表的最后,表示栈顶
     */
    private Node last;

    /**
     * 内部类,表示节点,包含指针及数据
     */
    class Node {
        /**
         * 下一节点指针
         */
        public Node next;

        /**
         * 节点数据
         */
        public T data;

        public Node(Node next, T data) {
            this.next = next;
            this.data = data;
        }
    }

    @Override
    public Iterator<T> iterator() {
        return new ReverseArrayIterator();
    }

    // ============ 几个主要方法 ============
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void push(T element) {
        last = new Node(last, element);
        size++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack underflow");
        }
        Node next = last.next == null ? last : last.next;
        last = next;
        size--;
        return next.data;
    }

    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Stack underflow");
        }
        return last.data;
    }

    class ReverseArrayIterator implements Iterator<T> {

        int i = size;
        Node last1 = last;

        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException("Stack underflow");
            }
            Node temp = last1;
            last1 = last1.next;
            i--;
            return temp.data;
        }
    }

    public static void main(String[] args) {
        StackByList sbl = new StackByList();
        sbl.push("A");
        sbl.push("B");
        sbl.push("C");

        for (Object aSbl : sbl) {
            System.out.println(aSbl);
        }

        sbl.peek();
        sbl.peek();
        sbl.pop();

        for (Object aSbl : sbl) {
            System.out.println(aSbl);
        }
    }
}

队列

  • 在队尾插入元素,在队头删除元素。
  • 实现先进先出语义

双向链表实现队列

/**
 * @author kbrx93
 */
public class QueueByList<T> implements Iterable<T> {

    /**
     * 链表首指针
     */
    private Node first;

    /**
     * 链表首指针
     */
    private Node last;

    /**
     * 队列中元素个数
     */
    private int size;

    public QueueByList() {
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void push(T data) {
        Node newNode = new Node(data, null, last);
        if (last != null) {
            last.next = newNode;
            last = last.next;
        } else {
            first = last = newNode;
        }
        size++;
    }

    public T pop() {
        if (size <= 0) throw new NoSuchElementException("Queue underFlow");
        Node temp = first.next;
        T data = first.data;
        first.next = null; // help GC
        first = temp;
        first.pre = null;
        size--;
        return data;
    }

    public T peek() {
        if (size <= 0) throw new NoSuchElementException("Queue underFlow");
        return first.data;
    }

    @Override
    public Iterator<T> iterator() {
        return new ReverseArrayIterator();
    }

    private class ReverseArrayIterator implements Iterator<T> {

        int i = size;
        Node index = first;

        @Override
        public boolean hasNext() {
            return i > 0;
        }

        @Override
        public T next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            i--;
            Node temp = index;
            index = index.next;
            return temp.data;
        }
    }

    class Node {
        /**
         * 节点数据
         */
        T data;

        /**
         * 下一节点指针
         */
        Node next;

        /**
         * 上一节点指针
         */
        Node pre;

        public Node(T data, Node next, Node pre) {
            this.data = data;
            this.next = next;
            this.pre = pre;
        }
    }

    public static void main(String[] args) {
        QueueByList queueByList = new QueueByList();
        queueByList.push("A");
        queueByList.push("B");
        queueByList.push("C");

        for (Object o : queueByList) {
            System.out.println(o);
        }
        queueByList.peek();
        queueByList.pop();
        for (Object o : queueByList) {
            System.out.println(o);
        }
    }
}

栈与队列异同

相同:

  • 线性存储结构。
  • 插入及删除的时间复杂度为 O(1),空间复杂度也为 O(1)。
  • 都是在表尾插入。
  • 都有链表 + 数组两种实现方式。

不同:

队列
顺序 先进先出 先进后出
删除元素位置 在头部删除 在尾部删除
应用场景 多用于方法调用 多于资源分配等

扩展:用栈实现队列 & 用队列实现栈

用队列实现栈

主要过程:「异常」入,正常出。

代码实现:

/**
 * @author kbrx93
 */
public class StackByQueue {

    private Queue<Integer> a = new LinkedList<Integer>();
    private Queue<Integer> b = new LinkedList<Integer>();

    /**
     * "异常入"
     */
    public void push(int x) {
        Queue<Integer> fill = a.isEmpty() ? b : a;
        Queue<Integer> empty = !a.isEmpty() ? b : a;
        empty.add(x);
        while (!fill.isEmpty()) {
            empty.add(fill.remove());
        }
    }

    /**
     * 正常入
     */
    public int pop() {
        Queue<Integer> fill = a.isEmpty() ? b : a;
        if (fill.isEmpty()) {
            return -1;
        } else {
            return fill.remove();
        }
    }

    public boolean isEmpty() {
        return a.isEmpty() && b.isEmpty();
    }

    public static void main(String[] args) {
        StackByQueue stackByQueue = new StackByQueue();
        stackByQueue.push(1);
        stackByQueue.push(2);
        stackByQueue.push(3);
        stackByQueue.push(4);
        while (!stackByQueue.isEmpty()) {
            System.out.println(stackByQueue.pop());
        }
    }
}

用栈实现队列

主要过程:正常入,「异常」出。

代码实现:

public class QueueByStack {

    private Stack<Integer> in = new Stack<>();
    private Stack<Integer> out = new Stack<>();

    public QueueByStack() {}

    /**
     * 正常入
     */
    public void push(int x) {
        in.push(x);
    }

    /**
     * "异常"出
     */
    public int pop() {
        if (!out.empty()) {
            return out.pop();
        }
        if (in.empty()) {
            return -1;
        } else {
            // 如果in不为空,则一直将数据给out,直到空为止
            while (!in.empty()) {
                out.push(in.pop());
            }
            return out.pop();
        }
    }

    /**
     * empty

     */
    public boolean empty() {
        return in.empty() && out.empty();
    }

    public static void main(String[] args) {
        QueueByStack queueByStack = new QueueByStack();
        queueByStack.push(1);
        queueByStack.push(2);
        queueByStack.push(3);
        queueByStack.push(4);
        queueByStack.push(5);

        while (!queueByStack.empty()) {
            System.out.println(queueByStack.pop());
        }

    }

}

小结

介绍了数据结构中的数组、链表、栈及队列的基本特点及实现。

Last Modified: July 26, 2018
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment