堆疊(Stack)

文章已搬家，請點擊前往👈

REDIRECT_MODE = 1;

簡介

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

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

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

push：將資料放入堆疊頂端 pop：取出堆疊頂端之資料

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

peek：看堆疊頂端的資料而不取出。。(註：也有top等不同的用字) size：取得堆疊的數目。

在實作上一般可以使用陣列或 連結串列(LinkedList) 兩種方式來實作：

陣列

堆疊建立時即建立一個陣列，並使用一個索引來記錄目前所指到的位址，新增或移除資料時，同步修改索引位址；如果有實作堆疊數目的功能時，這數字正好可做為此索引之用。優點是不用處理指標鏈結建立與移除，缺點是容量超過陣列大小時需要額外處理。

連結串列

用指標將資料串起來，將新的東西不斷接在最後面，而取出時則移除最後面的東西即可。優缺點與陣列相反。

語法

C#

抽象類別

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace Stack { abstract class Stack { public int Count { get; protected set; } abstract public void Push(T value); abstract public T Pop(); abstract public T Peek(); } }

陣列

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace Stack { class ArrayStack : Stack { 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]; } } }

連結串列

using System; using System.Collections.Generic; using System.Linq; using System.Text;

namespace Stack { class Node { public Node Previous { get; internal set; } public T Value { get; internal set; }

public Node(T value) { Value = value; } }

class LinkedListStack : Stack { private Node last;

public override void Push(T value) { Node node = new Node (value); node.Previous = last; last = node; ++Count; }

public override T Pop() { Node node = last; last = last.Previous; node.Previous = null; --Count; return node.Value; }

public override T Peek() { return last.Value; } } }

Java

抽象類別

public abstract class Stack { protected int count; abstract public void push(T value); abstract public T pop(); abstract public T peek(); public int size() { return count; } }

陣列

public class ArrayStack extends Stack {

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

}

連結串列

public class Node { private Node previous; private T value; public Node getPrevious() { return previous; } void setPrevious(Node previous) { this.previous = previous; } public T getValue() { return value; } void setValue(T value) { this.value = value; }

public Node(T value) { this.value = value; } }

public class LinkedListStack extends Stack {

private Node last; @Override public void push(T value) { // TODO Auto-generated method stub Node node = new Node (value); node.setPrevious(last); last = node; ++count; }

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

抽象類別

#ifndef STACK_H #define STACK_H

template 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

陣列

#ifndef ARRAYSTACK_H #define ARRAYSTACK_H

#include #include "Stack.h"

template class ArrayStack : public Stack { public: ArrayStack(int capacity = 10240) { cap = capacity; arrayLength = capacity; array = new T[capacity]; } ~ArrayStack() { delete [] array; } void push(T value) { if (Stack ::count == arrayLength) { T* newArray = new T[arrayLength + cap]; memcpy(newArray, array, arrayLength * sizeof(T)); arrayLength += cap; delete [] array; array = newArray; } array[Stack ::count++] = value; }

T pop() { T value = array[--Stack ::count]; array[Stack ::count] = 0; return value; }

T top() { return array[Stack ::count]; } protected: private: int arrayLength; int cap; T* array; };

#endif // ARRAYSTACK_H

連結串列

#ifndef LINKEDLISTSTACK_H #define LINKEDLISTSTACK_H

#include "Stack.h"

template class Node { public: Node(T v) { value = v; previous = 0; } ~Node() { delete previous; } Node * previous; T value; protected: private: };

template class LinkedListStack : public Stack { public: ~LinkedListStack() { delete last; } void push(T value) { Node * node = new Node (value); node->previous = last; last = node; ++Stack ::count; } T pop() { Node * node = last; last = last->previous; node->previous = 0; T value = node->value; delete node; --Stack ::count; return value; }

T top() { return last->value; } protected: private: Node * last; };

#endif // LINKEDLISTSTACK_H

Push和Pop 500000次實測，同時候內建的類別比較

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

下載

VS2010 C#版本

Eclipse Java版本

Code::Blocks C++版本

-->

小殘的程式光廊

提供一些演算法、資料結構、程式題目的整理與說明，PHP和JavaScript的基本教學和一些程式相關問題與解法。

堆疊(Stack)

參觀人氣

熱門文章

文章分類

電腦程式 (10)

最新文章

文章搜尋

文章精選