本文已經過時, 最新文章請點擊 : 《【資料結構 – 重構】堆疊與雙邊堆疊》
串列堆疊與鏈結串列具有一定的相似性, 堆疊在操作上是受到限制的線型表
根據堆疊的基本特點 :
- Last In First Out (LIFO)
可以將鏈結串列改造為串列堆疊
本文中的均為 top
指標指向尾部的串列堆疊. 從性質上分析, 這是一種方便推入而不方便彈出的堆疊; 當然, 你亦可以寫成 top
指標指向頭部的串列堆疊, 則性質與上述相反
堆疊的具體操作在之前已經講過, 這裏就不再繼續講解了
首先用一張 SVG 圖像描述串列堆疊
根據圖像描述, 所有的推入彈出都是針對 top
指標的操作. 為了方便判斷, 我將串列堆疊的第一個節點的數據設定為空, 即不寫入數據
下面是本人寫的關於串列堆疊的原始碼
如若有錯誤存在, 可以聯絡我或者直接添加評論. 關於原始碼的註解, 已經給的比較全面, 還有不明白的可以直接評論, 對於註解的建議也可以提出. 直接讀原始碼的函式名稱或者變數名稱可以直接了解作用
LinkedStack.hpp
:
#ifndef LINKEDSTACK_LINKEDSTACK_HPP
#define LINKEDSTACK_LINKEDSTACK_HPP
#include <iostream>
#include <cstdlib>
namespace LinkedStack {
using std::cout;
using std::cin;
using std::endl;
class Node {
protected :
int data;
Node *next;
public :
Node();
~Node();
void insertData(int data);
void insertNext(Node *next);
Node *getNext();
int getData();
};
class Stack : protected Node {
private :
bool isEmpty();
protected :
Node *first;
Node *top;
public :
Stack();
~Stack();
long long int getTop();
void push(int data);
void pop();
void clearStack();
void showStack();
};
}
#endif //LINKEDSTACK_LINKEDSTACK_HPP
LinkedStack.cpp
:
#include "LinkedStack.hpp"
using namespace LinkedStack;
Node::Node() {
}
Node::~Node() {
}
void Node::insertNext(Node *next) {
this->next = next;
}
void Node::insertData(int data) {
this->data = data;
}
int Node::getData() {
return this->data;
}
Node *Node::getNext() {
return this->next;
}
Stack::Stack() {
this->first = new Node();
this->first->insertNext(nullptr);
this->top = this->first;
}
Stack::~Stack() {
this->top = nullptr; //To avoid a pointer is going to be deleted twice.
auto *node = this->first;
/* Delete all node to avoid Memory Leaks. */
while(node->getNext() != nullptr) {
auto *deleteNode = node;
node = node->getNext();
delete deleteNode;
deleteNode = nullptr;
}
delete node;
}
bool Stack::isEmpty() {
if(this->top == this->first) {
return true;
}
return false;
}
long long int Stack::getTop() {
if(this->isEmpty()) {
return INT64_MIN;
}
return (long long int)top->getData();
}
void Stack::push(int data) {
auto *node = new Node();
node->insertData(data);
node->insertNext(nullptr);
this->top->insertNext(node); //Insert new node from the tail of stack.
top = node; //Top point to new node.
}
void Stack::pop() {
if(this->isEmpty()) {
cout << "The stack is empty!" << endl;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
return;
}
Node *node = this->first;
while(node->getNext() != this->top) {
node = node->getNext();
}
node->insertNext(nullptr);
cout << "The element : " << this->top->getData() << " has been popped!" << endl;
/* Delete top and reset top. */
delete this->top;
this->top = node;
node = nullptr;
delete node;
cout << "Press any key to continue!" << endl;
getchar();
getchar();
}
void Stack::clearStack() {
this->top = this->first;
Node *node = this->first->getNext();
/* If node is not nullptr, then delete the node after node. */
if(node) {
while(node->getNext() != nullptr) {
Node *temp = node;
node = node->getNext();
delete temp;
temp = nullptr;
}
}
delete node;
node = nullptr;
this->first->insertNext(nullptr); //Set first node's next to nullptr.
}
void Stack::showStack() {
int count = 0; //To count the number of stack.
Node *node = this->first;
/* Count Module */
while(node->getNext() != nullptr) {
node = node->getNext();
count++;
}
if(!count) {
return;
}
/* Print the index of elements. */
cout << "Index : \t";
for(int i = 1; i <= count; i++) {
cout << i << "\t";
}
/* Print all elements. */
cout << endl << "Element : \t";
node = this->first;
while(node->getNext() != nullptr) {
node = node->getNext();
cout << node->getData() << "\t";
}
cout << endl;
node = nullptr;
delete node;
}
main.cpp
:
#include "LinkedStack.hpp"
using namespace LinkedStack;
void menu();
int main(int argc, char *argv[]) {
auto *stack = new Stack();
long long int top;
int data;
int choice;
do {
system("clear");
stack->showStack();
menu();
cin >> choice;
switch(choice) {
case 1 :
top = stack->getTop();
if(top == INT64_MIN) {
cout << "The stack is empty!" << endl;
cout << "Press any key to continue!" << endl;
}else {
cout << "The top element : " << top << endl;
cout << "Press any key to continue!" << endl;
}
getchar();
getchar();
break;
case 2 :
cout << "Please enter the element you want to push : ";
cin >> data;
stack->push(data);
break;
case 3 :
stack->pop();
break;
case 4 :
stack->clearStack();
break;
case 5 :
delete stack;
exit(0);
default :
break;
}
}while(choice != 5);
}
void menu() {
cout << "------------------------------------------------" << endl;
cout << "1. Get the top element of stack." << endl;
cout << "2. Push." << endl;
cout << "3. Pop." << endl;
cout << "4. Clear the stack." << endl;
cout << "5. Exit." << endl;
cout << "------------------------------------------------" << endl;
cout << "Please enter your choice : ";
}
自創文章, 原著 : Jonny, 如若需要轉發, 在已經授權的情況下請註明出處 :《資料結構 : 串列堆疊》https://jonny.vip/2018/02/09/%e8%b3%87%e6%96%99%e7%b5%90%e6%a7%8b-%e4%b8%b2%e5%88%97%e5%a0%86%e7%96%8a/
Leave a Reply