Stack: 以Array與Linked list實作

Posted by Chiu CC on 4 24, 2016


先備知識與注意事項

本篇文章接續Stack: Intro(簡介),介紹以Array與Linked list實作Stack的方法。

如果對Linked list不太熟悉,建議讀者可以先閱讀以下連結之內容做簡單複習:


目錄

以Array實作Stack

在以Array(陣列)實作Stack的程式範例中,class StackArrayprivate data有三項:

  • int top:記錄於stack中,最上面資料的index。
  • int capacity:即為Array的size,也就是實際配置的記憶體大小。
  • int *stack:這裡以int作為資料的形別(type)做示範,所以就以int的Array來表示Stack。

以及Stack的基本處理資料的函式:Push()Pop()IsEmpty()Top()getSize()

比較需要注意的有:

DoubleCapacity():因為利用Array來存放資料,所以有可能在不斷新增資料(Push())時,碰上一開始分配給Array的記憶體空間(capacity)不夠的情況,可以透過重新配置一個capacity為兩倍大的Array來解決。

  • 更理想的做法是,能夠先對欲放進Stack處理的資料數量有個底,在初始化時,就把capacity設定在差不多的範圍,如此一來,不需要重複多次DoubleCapacity(),也不會過分浪費記憶體空間。
  • 本篇文章提供的範例程式碼將capacity初始為\(1\),主要是為了方便測試DoubleCapacity()

Pop():最常見的做法,是「想像地」把資料從Array中移除,意思是,當呼叫Pop()時,其實只是把int top減一,並沒有真的把資料從Array中移除,這麼做的原因是,等到下次Push()新增資料時,自然會把該記憶體位置覆寫(overwrite),見圖二(a):

  • Pop()時,並沒有把\(7\)刪除,只是把top移回到\(3\),讓Stack看起來已經把\(7\)移除,此時「最上面」資料是\(3\)
  • 也有些寫法比較謹慎,會把原先是\(7\)的記憶體位置,以\(0\)覆寫,見圖二(b)。
  • 還有ㄧ些寫法會真的把\(7\)移除,此時就需要呼叫classdestructor。但是這種寫法並不推薦,原因是「向系統要記憶體」需要成本,如果接下來Stack還會新增資料,那麼只要確實更新top使得Stack「看起來」有Pop()就好。

cc

圖二(a)。

cc

圖二(b)。

完整程式範例如下:

// C++ code
#include <iostream>

class StackArray{
private:
    int top;                 // index of top element
    int capacity;            // allocated memory space of array
    int *stack;              // array representing stack
    void DoubleCapacity();   // double the capacity of stack
public:
    StackArray():top(-1),capacity(1){    // constructor
        stack = new int[capacity];       // initial state: top=-1, capacity=1
    }
    void Push(int x);
    void Pop();
    bool IsEmpty();
    int Top();
    int getSize();
};
void StackArray::DoubleCapacity(){

    capacity *= 2;                            // double capacity
    int *newStack = new int[capacity];        // create newStack

    for (int i = 0 ; i < capacity/2; i++) {   // copy element to newStack
        newStack[i] = stack[i];
    }

    delete [] stack;              // release the memory of stack
    stack = newStack;             // redirect stack to newStack
}

void StackArray::Push(int x){

    if (top == capacity - 1) {    // if stack is full, double the capacity
        DoubleCapacity();
    }
    stack[++top] = x;             // update top and put x into stack
}

void StackArray::Pop(){

    if (IsEmpty()) {          // if stack is empty, there is nothing to pop
        std::cout << "Stack is empty.\n";
        return;
    }
    top--;                    // update top
//    stack[top] = 0;         // (*1)
//    stack[top].~T();        // (*2)
}

bool StackArray::IsEmpty(){

    //    if (top == -1) {
    //        return true;
    //    }
    //    else {
    //        return false;
    //    }
    return (top == -1);
}

int StackArray::Top(){

    if (IsEmpty()) {     // check if stack is empty
        std::cout << "Stack is empty.\n";
        return -1;
    }
    return stack[top];   // return the top element
}

int StackArray::getSize(){

    return top+1;        // return the number of elements in stack
}

int main(){

    StackArray s;
    s.Pop();
    s.Push(14);
    s.Push(9);
    std::cout << "\ntop: " << s.Top() << "\nsize: " << s.getSize() << std::endl;
    s.Push(7);
    std::cout << "\ntop: " << s.Top() << "\nsize: " << s.getSize() << std::endl;
    s.Pop();
    s.Pop();
    std::cout << "\ntop: " << s.Top() << "\nsize: " << s.getSize() << std::endl; 
    s.Pop();
    std::cout << "\ntop: " << s.Top() << "\nsize: " << s.getSize() << std::endl;

    return 0;
}

output:

Stack is empty.

top: 9
size: 2

top: 7
size: 3

top: 14
size: 1

top: Stack is empty.
-1
size: 0

main()測試的結果與圖二(c)相同:

cc

圖二(c)。

以Linked list實作Stack

Stack也可以用Linked list實現,以圖三(a)的Linked list為例,原先用來記錄第一個node的指標first,在Stack的實作上,就是用來記錄Stack「最上面」資料的指標top

cc

圖三(a)。

這裡延續Linked List: 新增資料、刪除資料、反轉對Linked list的實作方法,採用兩個class,一個是class StackNode,表示Linked list的node,一個是class StackList,其記錄Stack的「最上面node」,作為整個Stack的存取入口(如同Linked list是以「第一個node」作為存取入口)。

  • 有些寫法是利用struct來建立node,雖然struct StackNode的資料成員(data member)一定是public,不過只要把class StackListStackNode *top設成private,那麼在main()同樣無法更改每個node的資料。
    參考:Code Review:C++ Stack using template



特別注意Push()函式:

  • 因為要保持StackNode *top一直在Linked list的第一個位置,所以Stack在Push()新增資料時,採用Linked list的Push_front()
  • 在程式範例中,有這麼一行StackNode *newnode = new StackNode(x,top);(目前是註解的狀態)是利用class StackNode的第三個constructor,直接把新增的node之next pointer指向top
    其功能等同於「先利用class StackNode的第二個constructor,再手動更新newNodenext pointer」。
    • 小結論:好好利用constructor會更有效率。

完整程式範例如下:

// C++ code
#include <iostream>
class StackList;

class StackNode{
private:
    int data;
    StackNode *next;
public:
    StackNode():data(0){
        next = 0;
    }
    StackNode(int x):data(x){
        next = 0;
    }
    StackNode(int x, StackNode *nextNode):data(x),next(nextNode){};
    friend class StackList;
};

class StackList{
private:
    StackNode *top;     // remember the address of top element 
    int size;           // number of elements in Stack
public:                 
    StackList():size(0),top(0){};
    void Push(int x);
    void Pop();
    bool IsEmpty();
    int Top();
    int getSize();
};

void StackList::Push(int x){

    if (IsEmpty()) {
        top = new StackNode(x);
        size++;
        return;
    }

    StackNode *newnode = new StackNode(x);  // Push_front() in Linked list
    newnode->next = top;                    
//    StackNode *newnode = new StackNode(x,top);
    top = newnode;
    size++;
}

void StackList::Pop(){

    if (IsEmpty()) {
        std::cout << "Stack is empty.\n";
        return;
    }

    StackNode *deletenode = top;
    top = top->next;
    delete deletenode;
    deletenode = 0;
    size--;
}

bool StackList::IsEmpty(){

    return (size == 0);     // if size==0, return true
}

int StackList::Top(){

    if (IsEmpty()) {
        std::cout << "Stack is empty.\n";
        return -1;
    }
    return top->data;
}

int StackList::getSize(){

    return size;
}

int main(){

    StackList s;
    s.Pop();
    s.Push(32);
    s.Push(4);
    std::cout << "\ntop: " << s.Top() << "\nsize: " << s.getSize() << std::endl;        
    s.Push(15);
    std::cout << "\ntop: " << s.Top() << "\nsize: " << s.getSize() << std::endl;         
    s.Pop();
    s.Pop();
    std::cout << "\ntop: " << s.Top() << "\nsize: " << s.getSize() << std::endl;          
    s.Pop();
    std::cout << "\ntop: " << s.Top() << "\nsize: " << s.getSize() << std::endl;

    return 0;
}

output:

Stack is empty.

top: 4
size: 2

top: 15
size: 3

top: 32
size: 1

top: Stack is empty.
-1
size: 0

main()測試的結果與圖三(b)相同:

cc

圖三(b)。


以上是分別以Array和Linked list實作Stack的方法。

兩者的優劣,可以參考Linked List: Intro(簡介)中Array與Linked list的比較。



參考資料:


Stack系列文章

Stack: Intro(簡介)
Stack: 以Array與Linked list實作
Stack: 能夠在O(1)取得最小值的MinStack

回到目錄:

目錄:演算法與資料結構