簡介
堆疊 (Stack) 是資料結構的一種，是一種很基本常見的資料結構，首先利用現實生活中的例子來說明，如下圖
假設你有一些書把他們疊起來，一層一層的往上疊，所以每次新的書本會放在最上面，而當想要拿取書本的時候，也是從最上面的開始拿。當然現實生活會有可能從中間抽出書本，不過在程式中是不可以的，在程式世界下圖會更貼切。
所以他是一種後進先出 (Last-In-First-Out, LIFO) 的排程，而在此資料結構中至少會實作兩個操作：
- push：將資料放入堆疊頂端
- pop：取出堆疊頂端之資料
有時候也會多實作一些額外的操作以方便使用，例如：
- peek：看堆疊頂端的資料而不取出。。(註：也有 top 等不同的用字)
- size：取得堆疊的數目。
在實作上一般可以使用陣列或連結串列 (LinkedList) 兩種方式來實作：
陣列
堆疊建立時即建立一個陣列，並使用一個索引來記錄目前所指到的位址，新增或移除資料時，同步修改索引位址；如果有實作堆疊數目的功能時，這數字正好可做為此索引之用。優點是不用處理指標鏈結建立與移除，缺點是容量超過陣列大小時需要額外處理。
連結串列
用指標將資料串起來，將新的東西不斷接在最後面，而取出時則移除最後面的東西即可。優缺點與陣列相反。
語法
C#
抽象類別
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Stack
{
abstract class Stack<T>
{
public int Count { get; protected set; }
abstract public void Push(T value);
abstract public T Pop();
abstract public T Peek();
}
}
|
陣列
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
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Stack
{
class ArrayStack<T> : Stack<T>
{
private int capacity;
private T[] array;
public ArrayStack()
: this(10240)
{
}
public ArrayStack(int capacity)
{
this.capacity = capacity;
array = new T[capacity];
}
public override void Push(T value)
{
if (Count == array.Length)
{
T[] newArray = new T[array.Length + capacity];
Array.Copy(array, newArray, array.Length);
array = newArray;
}
array[Count++] = value;
}
public override T Pop()
{
T value = array[--Count];
array[Count] = default(T);
return value;
}
public override T Peek()
{
return array[Count - 1];
}
}
}
|
連結串列
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
| using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Stack
{
class Node<T>
{
public Node<T> Previous { get; internal set; }
public T Value { get; internal set; }
public Node(T value)
{
Value = value;
}
}
class LinkedListStack<T> : Stack<T>
{
private Node<T> last;
public override void Push(T value)
{
Node<T> node = new Node<T>(value);
node.Previous = last;
last = node;
++Count;
}
public override T Pop()
{
Node<T> node = last;
last = last.Previous;
node.Previous = null;
--Count;
return node.Value;
}
public override T Peek()
{
return last.Value;
}
}
}
|
Java
抽象類別
1
2
3
4
5
6
7
8
9
10
11
12
| public abstract class Stack<T> {
protected int count;
abstract public void push(T value);
abstract public T pop();
abstract public T peek();
public int size()
{
return count;
}
}
|
陣列
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
| public class ArrayStack<T> extends Stack<T> {
private int capacity;
private T[] array;
public ArrayStack()
{
this(10240);
}
@SuppressWarnings("unchecked")
public ArrayStack(int capacity)
{
this.capacity = capacity;
array = (T[]) new Object[capacity];
}
@SuppressWarnings("unchecked")
@Override
public void push(T value) {
if (count == array.length)
{
T[] newArray = (T[]) new Object[array.length + capacity];
System.arraycopy(array, 0, newArray, 0, array.length);
array = newArray;
}
array[count++] = value;
}
@Override
public T pop() {
T value = array[--count];
array[count] = null;
return value;
}
@Override
public T peek() {
return array[count - 1];
}
}
|
連結串列
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
| public class Node<T>
{
private Node<T> previous;
private T value;
public Node<T> getPrevious()
{
return previous;
}
void setPrevious(Node<T> previous)
{
this.previous = previous;
}
public T getValue()
{
return value;
}
void setValue(T value)
{
this.value = value;
}
public Node(T value)
{
this.value = value;
}
}
|
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
| public class LinkedListStack<T> extends Stack<T> {
private Node<T> last;
@Override
public void push(T value) {
Node<T> node = new Node<T>(value);
node.setPrevious(last);
last = node;
++count;
}
@Override
public T pop() {
Node<T> node = last;
last = last.getPrevious();
node.setPrevious(null);
--count;
return node.getValue();
}
@Override
public T peek() {
return last.getValue();
}
}
|
C++
抽象類別
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
| #ifndef STACK_H
#define STACK_H
template<typename T>
class Stack
{
public:
Stack()
{
count = 0;
}
int size()
{
return count;
}
virtual void push(T value) = 0;
virtual T pop() = 0;
virtual T top() = 0;
protected:
int count;
private:
};
#endif
|
陣列
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
| #ifndef ARRAYSTACK_H
#define ARRAYSTACK_H
#include <memory.h>
#include "Stack.h"
template<typename T>
class ArrayStack : public Stack<T>
{
public:
ArrayStack(int capacity = 10240)
{
cap = capacity;
arrayLength = capacity;
array = new T[capacity];
}
~ArrayStack()
{
delete [] array;
}
void push(T value)
{
if (Stack<T>::count == arrayLength)
{
T* newArray = new T[arrayLength + cap];
memcpy(newArray, array, arrayLength * sizeof(T));
arrayLength += cap;
delete [] array;
array = newArray;
}
array[Stack<T>::count++] = value;
}
T pop()
{
T value = array[--Stack<T>::count];
array[Stack<T>::count] = 0;
return value;
}
T top()
{
return array[Stack<T>::count];
}
protected:
private:
int arrayLength;
int cap;
T* array;
};
#endif
|
連結串列
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
| #ifndef LINKEDLISTSTACK_H
#define LINKEDLISTSTACK_H
#include "Stack.h"
template<typename T>
class Node
{
public:
Node(T v)
{
value = v;
previous = 0;
}
~Node()
{
delete previous;
}
Node<T>* previous;
T value;
protected:
private:
};
template<typename T>
class LinkedListStack : public Stack<T>
{
public:
~LinkedListStack()
{
delete last;
}
void push(T value)
{
Node<T>* node = new Node<T>(value);
node->previous = last;
last = node;
++Stack<T>::count;
}
T pop()
{
Node<T>* node = last;
last = last->previous;
node->previous = 0;
T value = node->value;
delete node;
--Stack<T>::count;
return value;
}
T top()
{
return last->value;
}
protected:
private:
Node<T>* last;
};
#endif
|
Push和Pop 500000次實測，同時候內建的類別比較
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| C#
Built-in Stack Push Time: 13ms
Built-in Stack Pop Time: 8ms
LinkedListStack Push Time: 67ms
LinkedListStack Pop Time: 29ms
ArrayStack Push Time: 57ms
ArrayStack Pop Time: 17ms
Java
Built-in Stack Push Time: 48ms
Built-in Stack Pop Time: 108ms
LinkedListStack Push Time: 300ms
LinkedListStack Pop Time: 12ms
ArrayStack Push Time: 54ms
ArrayStack Pop Time: 9ms
C++
Built-in Push Time: 17ms
Built-in Pop Time: 26ms
LinkedListStack Push Time: 61ms
LinkedListStack Pop Time: 33ms
ArrayStack Push Time: 40ms
ArrayStack Pop Time: 8ms
|
延伸閱讀
連結串列 (LinkedList)
佇列 (Queue)
