C/C++ Stack: 以Array與Linked list實作

資料來源: http://alrightchiu.github.io/SecondRound/stack-introjian-jie.html

http://alrightchiu.github.io/SecondRound/stack-yi-arrayyu-linked-listshi-zuo.html
https://openhome.cc/Gossip/AlgorithmGossip/StackByLink.htm

一般的Stack，會有以下幾個處理資料結構的功能：

    1.Push(data)：把資料放進Stack。
    2.Pop：把「最上面」的資料從Stack中移除。
    3.Top：回傳「最上面」的資料，不影響資料結構本身。
    4.IsEmpty：確認Stack裡是否有資料，不影響資料結構本身。
    5.getSize：回傳Stack裡的資料個數，不影響資料結構本身。

使用鏈結實作（C 語言動態記憶體宣告）

#include <stdio.h> 
#include <stdlib.h> 

struct node { 
    int data; 
    struct node *next; 
}; 

typedef struct node Node; 

Node* creates(void);         // 建立堆疊 
int isEmpty(Node*);           // 堆疊已空 
int stacktop(Node*);   // 傳回頂端元素 
Node* add(Node*, int);   // 新增元素 
Node* delete(Node*);     // 刪除元素 
void list(Node*);      // 顯示所有內容 

int main(void) { 
    Node* sTop; 
    int input, select; 

    sTop = creates(); 

    while(1) { 
        printf("\n\n請輸入選項(-1結束)："); 
        printf("\n(1)插入值至堆疊"); 
        printf("\n(2)顯示堆疊頂端"); 
        printf("\n(3)刪除頂端值"); 
        printf("\n(4)顯示所有內容"); 
        printf("\n\$c>"); 
        scanf("%d", &select); 
        
        if(select == -1) 
            break; 

        switch(select) { 
            case 1: 
                printf("\n輸入值："); 
                scanf("%d", &input); 
                sTop = add(sTop, input); 
                break; 
            case 2: 
                printf("\n頂端值：%d", stacktop(sTop)); 
                break; 
            case 3: 
                sTop = delete(sTop); 
                break; 
            case 4: 
                list(sTop); 
                break; 
            default: 
                printf("\n選項錯誤！"); 
        } 
    } 

    printf("\n"); 

    return 0; 
} 

Node* creates() { 
    return NULL; 
} 

int isEmpty(Node* top) { 
    return (top == NULL); 
} 

int stacktop(Node* top) { 
    return top->data; 
} 

Node* add(Node* top, int item) { 
    Node* newnode; 

    newnode = (Node*) malloc(sizeof(Node)); 

    if(newnode == NULL) { 
        printf("\n記憶體配置失敗！"); 
        exit(1); 
    } 

    newnode->data = item; 
    newnode->next = top; 
    top = newnode; 

    return top; 
} 

Node* delete(Node* top) { 
    Node* tmpnode; 

    tmpnode = top; 
    if(tmpnode == NULL) { 
        printf("\n堆疊已空！"); 
        return NULL; 
    } 

    top = top->next; 
    free(tmpnode); 

    return top; 
} 

void list(Node* top) { 
    getnode* tmpnode; 
    tmpnode = top; 

    printf("\n堆疊內容："); 
    while(tmpnode != NULL) { 
        printf("%d ", tmpnode->data); 
        tmpnode = tmpnode->next; 
    } 
}

C++以Array實作Stack

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

C++以Linked list實作Stack

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