簡介
堆疊 (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)