classStackArray{ private: int top; //Index of top element of Stack int capacity; // Allocated memory int *stack; voidDoubleCapacity(); public: // Define constructor with initial state: top=-1, capacity=1 StackArray():top(-1),capacity(1) { //Init a int array with capacity=1 stack = newint[capacity]; } voidPush(int x); voidPop(); boolisEmpty(); intTop(); intgetSize(); };
// Return top element of stack intStackArray::Top(){ if(isEmpty()) { cout << "Empty Stack, nothing on the top!" << endl; return-1; } return stack[top]; }
classStackArray{ private: int top; //Index of top element of Stack int capacity; // Allocated memory int *stack; voidDoubleCapacity(); public: // Define constructor with initial state: top=-1, capacity=1 StackArray():top(-1),capacity(1) { //Init a int array with capacity=1 stack = newint[capacity]; } voidPush(int x); voidPop(); boolisEmpty(); intTop(); intgetSize(); };
//copy elements to new stack for(int i = 0; i < capacity/2;i++){ new_stack[i] = stack[i]; } // free memory, this is used to free memory that allocated by new[] delete[] stack; // redrect new_stack to stack stack = new_stack; }
// Return top element of stack intStackArray::Top(){ if(isEmpty()) { cout << "Empty Stack, nothing on the top!" << endl; return-1; } return stack[top]; }
// Define node structure classStackNode{ private: int data; StackNode *next; public: //Define constructor StackNode(): data(0),next(0){ //next = 0; } //Define constructor with initial data StackNode(int x):data(x), next(0){} //Define constructor with initial data and next node address StackNode(int x, StackNode *nextNode):data(x), next(nextNode){}; friendclassStackList; };
// Define first node, and stack-related functions classStackList{ private: StackNode *top; int size; public: StackList():top(0),size(0){}; voidPush(int x); voidPop(); boolisEmpty(); intTop(); intgetSize(); };
voidStackList::Push(int x){ if(isEmpty()){ top = newStackNode(x); size++; return; } //push_front() in linked list StackNode *newNode = newStackNode(x); //Link the new node to the origin top node newNode->next = top; //update top pointer top = newNode; size++; }
voidStackList::Pop(){ if(isEmpty()){ cout << "Empty stack, nothing to pop out!" << endl; return; } StackNode *tempNode = top; top = top->next; delete tempNode; // set tempNode to a null pointer, to prevent dangling pointer // The constructor will set the *next to 0 (NULL) tempNode =0; size--; }
classStackNode{ 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){}; friendclassStackList; };
classStackList{ private: StackNode *top; // remember the address of top element int size; // number of elements in Stack public: StackList():size(0),top(0){}; voidPush(int x); voidPop(); boolIsEmpty(); intTop(); intgetSize(); };
StackNode 部分:
首先一開始就先宣告 class StackList，因為在 class StackNode 中會先將 StackList 作為 friend class
接著就是定義 class StackNode，這裡定義了三個 constructor，分別對應三種狀況:
未給參數，則將node中的 data 和指標初始化為0，這代表有一個single node，其資料為0
voidStackList::Push(int x){ if(isEmpty()){ top = newStackNode(x); size++; return; } //push_front() in linked list StackNode *newNode = newStackNode(x); //Link the new node to the origin top node newNode->next = top; //update top pointer top = newNode; size++; }
Push 函式的部分，首先一樣要確認是否式空的stack，因為這會牽涉到我們要用的constructor 是哪個，如果為空，那就建立一個新節點，new StackNode(x)，也就是建立一個 data=x的新節點，並且將 top 指向該節點，此時stack size 需要加上1，接著就 return main function。若stack非空，則需要實踐push_front 的功能，所以一樣新增一個新節點，這裡有兩種寫法，上面這種是透過第二個constructor 定義節點，在手動將他指向原先的top節點，再更新top指標，這裡也可以改寫成 stackNode *newNode = new StackNode(x, top)，然後再更新 top指標即可
1 2 3 4 5 6 7 8 9 10 11 12 13
voidStackList::Pop(){ if(isEmpty()){ cout << "Empty stack, nothing to pop out!" << endl; return; } StackNode *tempNode = top; top = top->next; delete tempNode; // set tempNode to a null pointer, to prevent dangling pointer // The constructor will set the *next to 0 (NULL) tempNode =0; size--; }
Pop函式部分，一樣會需要先確認是否為空，如果stack是空的，那就return 回 main()
如果非空，那就跟常規 Linked List 刪除節點的步驟一樣，定義暫存節點，暫時保留top節點，接著將 top 更新為下一個節點，然後刪除暫存節點的資料
最重要的一步就是要將暫存節點設為 0，也就是 nullptr (因為 next 被設成0)以防止懸空指標發生，因為指標變數還存在。
