数据结构-背包、队列和栈

发表于 更新于 分类于
本文字数： 6.2k 阅读时长 ≈ 6 分钟

背包、队列和栈三种数据结构的实现（JAVA语言版）

栈

数组实现版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.Iterator;
import java.util.NoSuchElementException;

public class ResizingArrayStack<Item> implements Iterable<Item> 
{
    private static final int INIT_CAPACITY = 8;

    private Item[] a;
    private int n;

    public ResizingArrayStack() 
    {
        a = (Item[]) new Object[INIT_CAPACITY];
        n = 0;
    }

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

    public int size() 
    {
        return n;
    }

    private void resize(int capacity) 
    {
        assert capacity >= n;

        Item[] copy = (Item[]) new Object[capacity];
        for (int i = 0; i < n; i++) {
            copy[i] = a[i];
        }
        a = copy;
    }

    public void push(Item item) 
    {
        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();
    }

    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--];
        }
    }
}

$1.$每项操作的用时都与集合大小无关

$2.$空间需求总是不超过集合大小乘以一个常数

$3.ResizingArrayStack$的缺点在于某些$push()$和$pop()$操作会调整数组的大小：这项操作的耗时与栈的大小成正比

链表实现版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Stack<Item> implements Iterable<Item> 
{
    private Node<Item> first;
    private int n;

    private static class Node<Item> 
    {
        private Item item;
        private Node<Item> next;
    }

    public Stack() 
    {
        first = null;
        n = 0;
    }

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

    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);
            s.append(' ');
        }
        return s.toString();
    }

    public Iterator<Item> iterator() 
    {
        return new LinkedIterator(first);
    }

    private class LinkedIterator implements Iterator<Item> 
    {
        private Node<Item> current;

        public LinkedIterator(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;
        }
    }
}

链表版的堆栈避免了数组版某些$push()$和$pop()$操作调整数组大小的开销

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Queue<Item> implements Iterable<Item>
{
    private Node<Item> first;    
    private Node<Item> last;     
    private int n;               

    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;
        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--;
        if (isEmpty()) last = null;   // to avoid loitering
        return item;
    }

    public String toString()
    {
        StringBuilder s = new StringBuilder();
        for (Item item : this) {
            s.append(item);
            s.append(' ');
        }
        return s.toString();
    }

    public Iterator<Item> iterator()
    {
        return new LinkedIterator(first);
    }

    private class LinkedIterator implements Iterator<Item>
    {
        private Node<Item> current;

        public LinkedIterator(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;
        }
    }
}

背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.Iterator;
import java.util.NoSuchElementException;

public class Bag<Item> implements Iterable<Item> 
{
    private Node<Item> first;    
    private int n;               

    private static class Node<Item> 
    {
        private Item item;
        private Node<Item> next;
    }

    public Bag() 
    {
        first = null;
        n = 0;
    }

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

    public int size() 
    {
        return n;
    }

    public void add(Item item) 
    {
        Node<Item> oldfirst = first;
        first = new Node<Item>();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    public Iterator<Item> iterator()  
    {
        return new LinkedIterator(first);  
    }

    private class LinkedIterator implements Iterator<Item> 
    {
        private Node<Item> current;

        public LinkedIterator(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;
        }
    }
}