算法四習題 1.3

數組實現棧

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;class MyStack {
private:vector<int> data;  // 用于存儲棧元素的數組public:// 構造函數MyStack() {}// 入棧操作void push(int val) {data.push_back(val);  // 在數組末尾添加元素}// 出棧操作void pop() {if (empty()) {throw runtime_error("Stack underflow");}data.pop_back();  // 移除數組末尾元素}// 獲取棧頂元素int top() {if (empty()) {throw runtime_error("Stack is empty");}return data.back();  // 返回數組末尾元素}// 檢查棧是否為空bool empty() const {return data.empty();}// 返回棧中的元素數量int size() const {return data.size();}
};// 測試程序
int main() {return 0;
}

鏈表實現棧

#include <iostream>
#include <stdexcept>
using namespace std;// 鏈表節點結構
class Node {
public:int data;Node* next;// 構造函數Node(int val) : data(val), next(nullptr) {}
};// 使用鏈表實現的棧
class LinkedListStack {
private:Node* top_ptr;  // 指向棧頂的指針int n;          // 棧中元素的數量public:// 構造函數LinkedListStack() : top_ptr(nullptr), n(0) {}// 析構函數，釋放所有節點~LinkedListStack() {while (!empty()) {pop();}}// 入棧操作void push(int val) {Node* new_node = new Node(val);new_node->next = top_ptr;top_ptr = new_node;n++;}// 出棧操作void pop() {if (empty()) {throw runtime_error("Stack underflow");}Node* temp = top_ptr;top_ptr = top_ptr->next;delete temp;n--;}// 獲取棧頂元素int top() {if (empty()) {throw runtime_error("Stack is empty");}return top_ptr->data;}// 檢查棧是否為空bool empty() const {return top_ptr == nullptr;}// 返回棧中的元素數量int size() const {return n;}// 打印棧中的所有元素（用于調試）void printStack() const {if (empty()) {cout << "Stack is empty" << endl;return;}cout << "Stack (top to bottom): ";Node* current = top_ptr;while (current != nullptr) {cout << current->data << " ";current = current->next;}cout << endl;}
};// 測試程序
int main() {return 0;
}

雙向隊列和棧

#include <iostream>
#include <stdexcept>
using namespace std;// 雙向鏈表節點結構
class Node {
public:int data;Node* next;Node* prev;// 構造函數Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};// 使用雙向鏈表實現的雙向隊列
class Deque {
private:Node* front;  // 指向隊列前端的指針Node* back;   // 指向隊列后端的指針int n;        // 隊列中元素的數量public:// 構造函數Deque() : front(nullptr), back(nullptr), n(0) {}// 析構函數，釋放所有節點~Deque() {while (!empty()) {removeFront();}}// 檢查隊列是否為空bool empty() const {return n == 0;}// 返回隊列中的元素數量int size() const {return n;}// 在隊列前端添加元素void addFront(int val) {Node* new_node = new Node(val);if (empty()) {front = back = new_node;} else {new_node->next = front;front->prev = new_node;front = new_node;}n++;}// 在隊列后端添加元素void addBack(int val) {Node* new_node = new Node(val);if (empty()) {front = back = new_node;} else {new_node->prev = back;back->next = new_node;back = new_node;}n++;}// 從隊列前端移除元素int removeFront() {if (empty()) {throw runtime_error("Deque underflow");}Node* temp = front;int val = temp->data;if (front == back) {// 隊列中只有一個元素front = back = nullptr;} else {front = front->next;front->prev = nullptr;}delete temp;n--;return val;}// 從隊列后端移除元素int removeBack() {if (empty()) {throw runtime_error("Deque underflow");}Node* temp = back;int val = temp->data;if (front == back) {// 隊列中只有一個元素front = back = nullptr;} else {back = back->prev;back->next = nullptr;}delete temp;n--;return val;}// 獲取隊列前端元素int peekFront() const {if (empty()) {throw runtime_error("Deque is empty");}return front->data;}// 獲取隊列后端元素int peekBack() const {if (empty()) {throw runtime_error("Deque is empty");}return back->data;}// 打印隊列中的所有元素（用于調試）void printDeque() const {if (empty()) {cout << "Deque is empty" << endl;return;}cout << "Deque (front to back): ";Node* current = front;while (current != nullptr) {cout << current->data << " ";current = current->next;}cout << endl;}
};// 使用雙向隊列實現的棧
class DequeStack {
private:Deque deque;  // 使用雙向隊列作為底層數據結構public:// 入棧操作（在隊列前端添加元素）void push(int val) {deque.addFront(val);}// 出棧操作（從隊列前端移除元素）int pop() {return deque.removeFront();}// 獲取棧頂元素int top() const {return deque.peekFront();}// 檢查棧是否為空bool empty() const {return deque.empty();}// 返回棧中的元素數量int size() const {return deque.size();}// 打印棧中的所有元素（用于調試）void printStack() const {cout << "Stack (via Deque): ";deque.printDeque();}
};// 使用雙向隊列實現的隊列
class DequeQueue {
private:Deque deque;  // 使用雙向隊列作為底層數據結構public:// 入隊操作（在隊列后端添加元素）void enqueue(int val) {deque.addBack(val);}// 出隊操作（從隊列前端移除元素）int dequeue() {return deque.removeFront();}// 獲取隊頭元素int front() const {return deque.peekFront();}// 檢查隊列是否為空bool empty() const {return deque.empty();}// 返回隊列中的元素數量int size() const {return deque.size();}// 打印隊列中的所有元素（用于調試）void printQueue() const {cout << "Queue (via Deque): ";deque.printDeque();}
};// 測試程序
int main() {cout << "===== Testing Deque =====" << endl;Deque deque;deque.addFront(10);deque.printDeque();deque.addBack(20);deque.printDeque();deque.addFront(5);deque.printDeque();deque.addBack(30);deque.printDeque();cout << "Front element: " << deque.peekFront() << endl;cout << "Back element: " << deque.peekBack() << endl;cout << "Removing front: " << deque.removeFront() << endl;deque.printDeque();cout << "Removing back: " << deque.removeBack() << endl;deque.printDeque();cout << "\n===== Testing Stack implemented with Deque =====" << endl;DequeStack stack;stack.push(10);stack.push(20);stack.push(30);stack.printStack();cout << "Top element: " << stack.top() << endl;cout << "Popping: " << stack.pop() << endl;stack.printStack();cout << "\n===== Testing Queue implemented with Deque =====" << endl;DequeQueue queue;queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);queue.printQueue();cout << "Front element: " << queue.front() << endl;cout << "Dequeuing: " << queue.dequeue() << endl;queue.printQueue();return 0;
}

棧與隊列

#include <iostream>
#include <stack>
#include <queue>
#include <stdexcept>
using namespace std;// 使用兩個棧實現隊列
class StackQueue {
private:stack<int> inbox;   // 用于入隊操作的棧stack<int> outbox;  // 用于出隊操作的棧// 將元素從inbox轉移到outboxvoid transfer() {// 只有當outbox為空時才進行轉移，保證元素順序if (outbox.empty()) {while (!inbox.empty()) {outbox.push(inbox.top());inbox.pop();}}}public:// 入隊操作void enqueue(int val) {inbox.push(val);}// 出隊操作int dequeue() {if (empty()) {throw runtime_error("Queue underflow");}transfer();  // 確保outbox不為空int val = outbox.top();outbox.pop();return val;}// 獲取隊頭元素int front() {if (empty()) {throw runtime_error("Queue is empty");}transfer();  // 確保outbox不為空return outbox.top();}// 檢查隊列是否為空bool empty() const {return inbox.empty() && outbox.empty();}// 返回隊列中的元素數量int size() const {return inbox.size() + outbox.size();}
};// 使用兩個隊列實現棧
class QueueStack {
private:queue<int> q1;  // 主隊列，存儲所有元素queue<int> q2;  // 輔助隊列，用于操作public:// 入棧操作void push(int val) {// 將新元素加入主隊列q1.push(val);}// 出棧操作int pop() {if (empty()) {throw runtime_error("Stack underflow");}// 將q1中除最后一個元素外的所有元素移到q2while (q1.size() > 1) {q2.push(q1.front());q1.pop();}// 保存最后一個元素（棧頂元素）int val = q1.front();q1.pop();// 交換q1和q2的角色swap(q1, q2);return val;}// 獲取棧頂元素int top() {if (empty()) {throw runtime_error("Stack is empty");}// 將q1中除最后一個元素外的所有元素移到q2while (q1.size() > 1) {q2.push(q1.front());q1.pop();}// 保存最后一個元素（棧頂元素）int val = q1.front();// 將最后一個元素也移到q2q2.push(val);q1.pop();// 交換q1和q2的角色swap(q1, q2);return val;}// 檢查棧是否為空bool empty() const {return q1.empty();}// 返回棧中的元素數量int size() const {return q1.size();}
};// 測試程序
int main() {cout << "===== Testing Queue implemented with Stacks =====" << endl;StackQueue queue;cout << "Enqueuing: 10, 20, 30" << endl;queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);cout << "Queue size: " << queue.size() << endl;cout << "Front element: " << queue.front() << endl;cout << "Dequeuing: " << queue.dequeue() << endl;cout << "Front element after dequeue: " << queue.front() << endl;cout << "Queue size after dequeue: " << queue.size() << endl;cout << "Enqueuing: 40" << endl;queue.enqueue(40);cout << "Queue size: " << queue.size() << endl;cout << "Emptying queue..." << endl;while (!queue.empty()) {cout << "Dequeued: " << queue.dequeue() << endl;}cout << "\n===== Testing Stack implemented with Queues =====" << endl;QueueStack stack;cout << "Pushing: 10, 20, 30" << endl;stack.push(10);stack.push(20);stack.push(30);cout << "Stack size: " << stack.size() << endl;cout << "Top element: " << stack.top() << endl;cout << "Popping: " << stack.pop() << endl;cout << "Top element after pop: " << stack.top() << endl;cout << "Stack size after pop: " << stack.size() << endl;cout << "Pushing: 40" << endl;stack.push(40);cout << "Stack size: " << stack.size() << endl;cout << "Top element: " << stack.top() << endl;cout << "Emptying stack..." << endl;while (!stack.empty()) {cout << "Popped: " << stack.pop() << endl;}return 0;
}

1.3.9

編寫一段程序，從標準輸入得到一個缺少左括號的表達式并打印出補全括號之后的中序表達式。例如，給定輸入：[需要圖示]你的程序應該輸出：[需要圖示]

#include <iostream>
#include <stack>
#include <string>
using namespace std;string fixExpression(string& expr) {stack<string> operands;for (char c : expr) {if (c == ')') {// 遇到右括號，需要添加對應的左括號if (!operands.empty()) {string top = operands.top();operands.pop();top = "(" + top + ")";if (!operands.empty()) {// 將補全的表達式與前面的部分合并string prev = operands.top();operands.pop();operands.push(prev + top);} else {operands.push(top);}}} else if (c == '+' || c == '-' || c == '*' || c == '/') {// 遇到操作符，將其添加到前一個操作數之后if (!operands.empty()) {string top = operands.top();operands.pop();top = top + c;operands.push(top);}} else {// 處理操作數（數字或變量）string operand(1, c);if (!operands.empty()) {string prev = operands.top();operands.pop();operands.push(prev + operand);} else {operands.push(operand);}}}return operands.empty() ? "" : operands.top();
}int main() {string expression;cin >> expression;cout << fixExpression(expression) << endl;return 0;
}

1.3.10

編寫一個過濾器InfixToPostfix，將算術表達式由中序表達式轉為后序表達式。

#include <iostream>
#include <string>
#include <stack>
#include <cctype>using namespace std;class InfixToPostfix {
public:// 獲取操作符的優先級int getPrecedence(char op) {if (op == '+' || op == '-')return 1;if (op == '*' || op == '/')return 2;return 0;  // 括號的優先級最低}// 中序表達式轉后序表達式的主函數string convert(const string& infix) {string postfix = "";stack<char> operatorStack;for (int i = 0; i < infix.length(); i++) {char c = infix[i];// 如果是空格，跳過if (c == ' ')continue;// 如果是操作數(數字或字母)，直接添加到結果中if (isalnum(c)) {postfix += c;}// 如果是左括號，入棧else if (c == '(') {operatorStack.push(c);}// 如果是右括號，彈出棧中元素直到遇到左括號else if (c == ')') {while (!operatorStack.empty() && operatorStack.top() != '(') {postfix += operatorStack.top();operatorStack.pop();}// 彈出左括號if (!operatorStack.empty() && operatorStack.top() == '(') {operatorStack.pop();}}// 如果是運算符else {// 彈出優先級大于或等于當前運算符的所有運算符while (!operatorStack.empty() && operatorStack.top() != '(' && getPrecedence(operatorStack.top()) >= getPrecedence(c)) {postfix += operatorStack.top();operatorStack.pop();}// 當前運算符入棧operatorStack.push(c);}}// 處理棧中剩余的運算符while (!operatorStack.empty()) {if (operatorStack.top() != '(') {postfix += operatorStack.top();}operatorStack.pop();}return postfix;}
};int main() {InfixToPostfix converter;string infix;cout << "請輸入中序表達式: ";getline(cin, infix);string postfix = converter.convert(infix);cout << "后序表達式: " << postfix << endl;return 0;
}

1.3.11

編寫一段程序EvaluatePostfix，從標準輸入中得到一個后序表達式，求值并打印結果（將上一題的程序中得到的輸出用管道傳遞給這一段程序可以得到和Evaluate相同的行為）。

const int maxn = 1e4 + 50;
int st[maxn],idx;
class Solution {
public:int evalRPN(vector<string>& tokens) {idx = -1;for(const auto& t : tokens){if(t != "+" and t != "-" and t != "*" and t != "/"){st[++idx] = stoi(t);}else{auto a = st[idx--];auto b = st[idx--];if(t == "+") st[++idx] = b + a;else if(t == "-") st[++idx] = b - a;else if(t == "*") st[++idx] = b * a;else st[++idx] = b / a;}}return st[idx];}
};

1.3.12

編寫一個可迭代的Stack用例，它含有一個靜態的copy()方法，接受一個字符串的棧作為參數并返回該棧的一個副本。注意：這種能力是迭代器價值的一個重要體現，因為有了它我們無需改變基本API就能夠實現這種功能。

1.3.14

編寫一個類ResizingArrayQueueOfStrings，使用定長數組實現隊列的抽象，然后擴展實現，使用調整數組的方法突破大小的限制。

1.3.15

編寫一個Queue的用例，接受一個命令行參數k并打印出標準輸入中的倒數第k個字符串（假設標準輸入中至少有k個字符串）。

#include <iostream>
#include <string>
#include <deque>
#include <stdexcept>int main(int argc, char* argv[]) {// 檢查命令行參數if (argc != 2) {std::cerr << "用法: " << argv[0] << " k" << std::endl;return 1;}// 解析參數kint k;try {k = std::stoi(argv[1]);if (k <= 0) {throw std::invalid_argument("k必須是正整數");}} catch (const std::exception& e) {std::cerr << "錯誤: " << e.what() << std::endl;return 1;}// 使用deque作為循環緩沖區std::deque<std::string> buffer;std::string line;// 從標準輸入讀取字符串while (std::getline(std::cin, line)) {if (!line.empty()) {// 將字符串加入緩沖區buffer.push_back(line);// 如果緩沖區大小超過k，移除最早的元素if (buffer.size() > k) {buffer.pop_front();}}}// 檢查輸入是否至少有k個字符串if (buffer.size() < k) {std::cerr << "錯誤：輸入中的字符串數量少于" << k << "個" << std::endl;return 1;}// 打印倒數第k個字符串// 在含有k個元素的緩沖區中，最前面的元素就是倒數第k個std::cout << buffer.front() << std::endl;return 0;
}

鏈表練習

struct Node{String item;int val;Node* next;Node(string s, Node* nxt = nullptr) : item(s), val(0), next(nxt) {} Node(int v, Node* nxt = nullptr) : item(""), val(v), next(nxt) {}
};

1.3.19

給出一段代碼，刪除鏈表的尾結點，其中鏈表的首結點為first。

void removeTail(Node* first){Node* cur = first;if(first == nullptr || first->next ==nullptr){delete first;first = nullptr;return;}while(cur->next->next!=nullptr){cur = cur->next;}delete cur->next;cur->next = nullptr;
}

1.3.20

編寫一個方法delete()，接受一個int參數k，刪除鏈表的第k個元素（如果它存在的話）。


void delete(int k,Node* first){if(first ==nullptr) return;if(k==1){Node *tmp = first;first = first->next;delete tmp;return;}// 尋找第k-1個結點Node* cur = first;int i = 1;while(i<k-1&&cur!=nullptr){cur = cur->next;i++;}// 如果找不到第k個節點說明鏈表比k短if(cur==nullptr||cur->next == nullptr) return;Node* tmp = cur->next;cur->next = tmp->next;delete tmp;
}

1.3.21

編寫一個方法find()，接受一條鏈表和一個字符串key作為參數。如果鏈表中的某個結點的item域的值為key，則方法返回true，否則返回false。

bool find(Node* first, const string& key) {Node* cur = first;while (cur != nullptr) {if (cur->item == key) {return true;}cur = cur->next;}return false;
}

1.3.24

編寫一個方法 removeAfter()，接受一個鏈表結點作為參數并刪除該結點的后續結點（如果參數結點或參數結點的后續結點為空則什么也不做）。

void removeAfter(Node* node) {// 如果結點為空或結點的后續結點為空，什么也不做if (node == nullptr || node->next == nullptr) return;// 保存后續結點的引用Node* toDelete = node->next;// 更新鏈接，跳過后續結點node->next = toDelete->next;// 刪除后續結點delete toDelete;
}

1.3.25

編寫一個方法 insertAfter()，接受兩個鏈表結點作為參數，將第二個結點插入鏈表并使之成為第一個結點的后續結點（如果兩個參數為空則什么也不做）。

void insertAfter(Node* first, Node* second) {// 如果任一結點為空，什么也不做if (first == nullptr || second == nullptr) return;// 將second插入到first之后second->next = first->next;first->next = second;
}

1.3.26

編寫一個方法 remove()，接受一條鏈表和一個字符串 key 作為參數，刪除鏈表中所有 item 域為 key 的結點。

void remove(Node* head,const string& key){if(head!=nullptr&&head->item==key){{Node* toDelete = head;head = toDelete->next;delete toDelete;}if(head==nullptr) return;Node* cur = head;while(cur->next!=nullptr){if(cur->next->item==key){Node* tmp = cur->next;cur->next = tmp->next;delete tmp;// cur = cur->next;  }else {cur = cur->next;}}
}

void remove(Node* &head, const string& key) {// 處理頭部節點while (head != nullptr && head->item == key) {Node* toDelete = head;head = head->next;delete toDelete;}// 如果鏈表變為空if (head == nullptr) return;// 處理剩余節點Node* cur = head;while (cur->next != nullptr) {if (cur->next->item == key) {Node* toDelete = cur->next;cur->next = toDelete->next;delete toDelete;// 注意這里不移動cur，因為cur->next已經變成了新的節點} else {cur = cur->next;}}
}

1.3.27

編寫一個方法 max()，接受一條鏈表的首結點作為參數，返回鏈表中最大的節點的值。假設所有鏈接均為正整數，如果鏈表為空則返回0。

// 1.3.27 返回鏈表中最大的節點值（假設為整數）
int max(Node* first) {// 如果鏈表為空，返回0if (first == nullptr) return 0;int maxVal = first->val;Node* cur = first->next;while (cur != nullptr) {if (cur->val > maxVal) {maxVal = cur->val;}cur = cur->next;}return maxVal;
}

1.3.28

用遞歸解答上一題。

int max(Node* first) {// 基本情況：如果鏈表為空，返回0if (first == nullptr) return 0;// 遞歸計算剩余鏈表中的最大值int restMax = max(first->next);// 返回當前節點值和剩余最大值中的較大者return (first->val > restMax) ? first->val : restMax;
}

1.3.29

用環形鏈表實現 Queue。環形鏈表也是一條鏈表，只是沒有任何結點的鏈接為空，且只需鏈接非空則 last.next 的值為 first。只能使用一個 Node 類型的實例變量（last）。

struct Node{string item; // 節點存儲的數據 Node* next; // 指向下一個節點的指針 // 構造函數 Node(const string& data) : item(data), next(nullptr) {}
}class MyQueue{Node* last;int n;
public:CircularQueue() : last(nullptr), n(0) {}// 檢查隊列是否為空bool isEmpty() const {return last == nullptr;}// 返回隊列中的元素數量int size() const {return n;}// 入隊操作（在隊尾添加元素）void enqueue(const string& item) {Node* newNode = new Node(item);if (isEmpty()) {// 如果隊列為空，創建一個只有一個節點的環newNode->next = newNode;last = newNode;} else {// 將新節點插入到環中，成為新的last->next之后的節點newNode->next = last->next;last->next = newNode;// 更新last指向新節點last = newNode;}n++;}// 出隊操作（從隊頭移除元素）string dequeue() {if (isEmpty()) {throw runtime_error("Queue underflow");}// 獲取隊頭元素（last->next）Node* first = last->next;string item = first->item;if (first == last) {// 如果隊列中只有一個元素delete first;last = nullptr;} else {// 從環中移除隊頭元素last->next = first->next;delete first;}n--;return item;}// 獲取隊頭元素（不移除）string peek() const {if (isEmpty()) {throw runtime_error("Queue underflow");}return last->next->item;}
}

1.3.31

在兩個有序鏈表中的三個變量的作用：reverse、first 和 second。在遞歸實現中，我們從原鏈表中提取結點 first 并將它插入到逆鏈表的開頭。我們需要一直保持 first 指向原鏈表中所有剩余結點的首結點，second 指向原鏈表中所有剩余結點的第二個結點。

提取的題目還包括兩個關于鏈表反轉的實現：

使用迭代方法實現鏈表反轉函數 reverse()
使用遞歸方法實現鏈表反轉函數 reverse()

#include <iostream>
using namespace std;// 單向鏈表節點結構
class Node {
public:int data;Node* next;// 構造函數Node(int val) : data(val), next(nullptr) {}
};// 打印鏈表（用于測試）
void printList(Node* head) {Node* current = head;while (current != nullptr) {cout << current->data << " -> ";current = current->next;}cout << "nullptr" << endl;
}// 創建測試鏈表
Node* createTestList() {Node* head = new Node(1);head->next = new Node(2);head->next->next = new Node(3);head->next->next->next = new Node(4);head->next->next->next->next = new Node(5);return head;
}// 釋放鏈表內存
void freeList(Node* head) {while (head != nullptr) {Node* temp = head;head = head->next;delete temp;}
}// 使用迭代方法實現鏈表反轉
Node* reverseIterative(Node* head) {Node* reverse = nullptr;  // 反轉后的鏈表頭Node* first = head;       // 指向原鏈表中所有剩余結點的首結點while (first != nullptr) {Node* second = first->next;  // 指向原鏈表中所有剩余結點的第二個結點// 將 first 插入到反轉鏈表的開頭first->next = reverse;reverse = first;// 移動到下一個節點first = second;}return reverse;
}// 使用遞歸方法實現鏈表反轉
Node* reverseRecursive(Node* head) {// 基本情況：空鏈表或只有一個節點if (head == nullptr || head->next == nullptr) {return head;}// first 指向原鏈表的第一個節點Node* first = head;// second 指向原鏈表的第二個節點Node* second = first->next;// 遞歸反轉剩余的鏈表（從第二個節點開始）Node* rest = reverseRecursive(second);// 將第一個節點連接到反轉后鏈表的末尾second->next = first;first->next = nullptr;return rest;
}// 另一種遞歸實現（更接近題目描述）
Node* reverseRecursiveAlt(Node* first) {// 基本情況：空鏈表if (first == nullptr) return nullptr;// 基本情況：只有一個節點if (first->next == nullptr) return first;// second 指向原鏈表的第二個節點Node* second = first->next;// 遞歸反轉剩余的鏈表（從第二個節點開始）Node* rest = reverseRecursiveAlt(second);// 將第二個節點指向第一個節點second->next = first;// 將第一個節點指向 nullptr（它將成為新鏈表的最后一個節點）first->next = nullptr;return rest;
}int main() {// 測試迭代方法return 0;
}

1.3.32

實現一個泛型類 DoubleNode 用來構造雙向鏈表，其中每個結點都含有一個指向前面元素的引用和一項指向后面元素的引用（如果不存在則為 null）。為以下任務實現若干靜態方法：在表頭插入結點、在表尾插入結點、從表頭刪除結點、從表尾刪除結點、在指定結點之前插入新結點、在指定結點之后插入新結點、刪除指定結點。

#include <iostream>
#include <stdexcept>
using namespace std;// 泛型雙向鏈表節點類
template <typename T>
class DoubleNode {
public:T data;DoubleNode<T>* prev;DoubleNode<T>* next;// 構造函數DoubleNode(T val) : data(val), prev(nullptr), next(nullptr) {}
};// 雙向鏈表操作的靜態方法類
template <typename T>
class DoublyLinkedList {
public:// 在表頭插入結點static DoubleNode<T>* insertAtHead(DoubleNode<T>* head, T val) {DoubleNode<T>* newNode = new DoubleNode<T>(val);if (head == nullptr) {return newNode;}newNode->next = head;head->prev = newNode;return newNode;}// 在表尾插入結點static DoubleNode<T>* insertAtTail(DoubleNode<T>* head, T val) {DoubleNode<T>* newNode = new DoubleNode<T>(val);if (head == nullptr) {return newNode;}// 找到鏈表的尾結點DoubleNode<T>* current = head;while (current->next != nullptr) {current = current->next;}current->next = newNode;newNode->prev = current;return head;}// 從表頭刪除結點static DoubleNode<T>* removeFromHead(DoubleNode<T>* head) {if (head == nullptr) {throw runtime_error("Cannot remove from empty list");}DoubleNode<T>* newHead = head->next;if (newHead != nullptr) {newHead->prev = nullptr;}delete head;return newHead;}// 從表尾刪除結點static DoubleNode<T>* removeFromTail(DoubleNode<T>* head) {if (head == nullptr) {throw runtime_error("Cannot remove from empty list");}// 如果只有一個節點if (head->next == nullptr) {delete head;return nullptr;}// 找到尾結點和倒數第二個結點DoubleNode<T>* current = head;while (current->next != nullptr) {current = current->next;}// 刪除尾結點DoubleNode<T>* newTail = current->prev;newTail->next = nullptr;delete current;return head;}// 在指定結點之前插入新結點static DoubleNode<T>* insertBefore(DoubleNode<T>* head, DoubleNode<T>* node, T val) {if (head == nullptr || node == nullptr) {throw runtime_error("Invalid operation");}// 如果在頭結點之前插入if (node == head) {return insertAtHead(head, val);}DoubleNode<T>* newNode = new DoubleNode<T>(val);DoubleNode<T>* prevNode = node->prev;newNode->next = node;newNode->prev = prevNode;node->prev = newNode;prevNode->next = newNode;return head;}// 在指定結點之后插入新結點static DoubleNode<T>* insertAfter(DoubleNode<T>* head, DoubleNode<T>* node, T val) {if (head == nullptr || node == nullptr) {throw runtime_error("Invalid operation");}DoubleNode<T>* newNode = new DoubleNode<T>(val);DoubleNode<T>* nextNode = node->next;newNode->prev = node;newNode->next = nextNode;node->next = newNode;if (nextNode != nullptr) {nextNode->prev = newNode;}return head;}// 刪除指定結點static DoubleNode<T>* remove(DoubleNode<T>* head, DoubleNode<T>* node) {if (head == nullptr || node == nullptr) {throw runtime_error("Invalid operation");}// 如果刪除的是頭結點if (node == head) {return removeFromHead(head);}DoubleNode<T>* prevNode = node->prev;DoubleNode<T>* nextNode = node->next;prevNode->next = nextNode;if (nextNode != nullptr) {nextNode->prev = prevNode;}delete node;return head;}// 查找指定值的節點static DoubleNode<T>* find(DoubleNode<T>* head, T val) {DoubleNode<T>* current = head;while (current != nullptr) {if (current->data == val) {return current;}current = current->next;}return nullptr;}// 打印鏈表（用于測試）static void printList(DoubleNode<T>* head) {cout << "Forward: nullptr <-> ";DoubleNode<T>* current = head;while (current != nullptr) {cout << current->data << " <-> ";current = current->next;}cout << "nullptr" << endl;// 從尾到頭打印鏈表（驗證prev指針）cout << "Backward: nullptr <-> ";if (head != nullptr) {// 找到尾結點current = head;while (current->next != nullptr) {current = current->next;}// 從尾到頭打印while (current != nullptr) {cout << current->data << " <-> ";current = current->prev;}}cout << "nullptr" << endl;}// 釋放鏈表內存static void freeList(DoubleNode<T>* head) {while (head != nullptr) {DoubleNode<T>* temp = head;head = head->next;delete temp;}}
};// 測試程序
int main() {DoubleNode<int>* list = nullptr;return 0;
}