簡介

堆疊 (Stack) 是資料結構的一種,是一種很基本常見的資料結構,首先利用現實生活中的例子來說明,如下圖
堆疊 (Stack)

假設你有一些書把他們疊起來,一層一層的往上疊,所以每次新的書本會放在最上面,而當想要拿取書本的時候,也是從最上面的開始拿。當然現實生活會有可能從中間抽出書本,不過在程式中是不可以的,在程式世界下圖會更貼切。
堆疊 (Stack)

所以他是一種後進先出 (Last-In-First-Out, LIFO) 的排程,而在此資料結構中至少會實作兩個操作:

  1. push:將資料放入堆疊頂端
  2. pop:取出堆疊頂端之資料

有時候也會多實作一些額外的操作以方便使用,例如:

  1. peek:看堆疊頂端的資料而不取出。。(註:也有 top 等不同的用字)
  2. 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) {
// TODO Auto-generated method stub
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() {
// TODO Auto-generated method stub
T value = array[--count];
array[count] = null;
return value;
}

@Override
public T peek() {
// TODO Auto-generated method stub
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) {
// TODO Auto-generated method stub
Node<T> node = new Node<T>(value);
node.setPrevious(last);
last = node;
++count;
}

@Override
public T pop() {
// TODO Auto-generated method stub
Node<T> node = last;
last = last.getPrevious();
node.setPrevious(null);
--count;
return node.getValue();
}

@Override
public T peek() {
// TODO Auto-generated method stub
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 // STACK_H

陣列

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 // ARRAYSTACK_H

連結串列

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 // LINKEDLISTSTACK_H

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)