该死!竟然没答案!!我写了半天竟然没答案!!
几种栈的表示:链栈、数组栈，两栈共享空间
纯虚基类 // created on 2020.10.21 by Joe #ifndef STACK_H #define STACK_H_ template <typename T> class stack { public: virtual ~stack() {} virtual bool empty() const = 0; virtual int size() const = 0; virtual T& top() const = 0; virtual void pop() = 0; virtual void push(const T& theElement) = 0; }; #endif 链栈 // created on 2020.10.21 by Joe #ifndef LINKEDSTACK_H_ #define LINKEDSTACK_H_ #include <sstream> #include "pureBaseStack.h" template <typename T> struct stackNode { T element; stackNode* next; stackNode() = default; stackNode(const T& theElement) : element(theElement) {} stackNode(const T& theElement, stackNode<T>* theNext) : element(theElement), next(theNext) {} }; template <typename T> class linkedStack : public stack<T> { public: ~linkedStack(); linkedStack(int initialCapacity = 10); bool empty() const override final { return stackSize == 0; } int size() const override final{ return stackSize; } T& top() const override final; void pop(); void push(const T& theElement); private: stackNode<T>* stackTop; int stackSize; }; template <typename T> linkedStack<T>::~linkedStack() { while (stackTop != nullptr) { stackNode<T>* nextNode = stackTop->next; delete stackTop; stackTop = nextNode; } } template <typename T> linkedStack<T>::linkedStack(int initialCapacity) { if (initialCapacity < 1) { std::ostringstream s; s << "can't creat a stack with capacity <= 0!" << std::endl; throw s.str(); } stackSize = 0; stackTop = nullptr; } template <typename T> T& linkedStack<T>::top() const { if (stackSize == 0) { std::ostringstream s; s << "Stack is empty!" << std::endl; throw s.str(); } return stackTop->element; } template <typename T> void linkedStack<T>::pop() { if (stackSize == 0) { std::ostringstream s; s << "can't pop from an empty stack!" << std::endl; throw s.str(); } stackNode<T>* nextNode = stackTop->next; delete stackTop; stackTop = nextNode; stackSize--; } template <typename T> void linkedStack<T>::push(const T& theElement) { stackTop = new stackNode<T>(theElement, stackTop); stackSize++; } #endif 数组栈 // created on 2020.10.21 by Joe #ifndef ARRAYSTACK_H_ #define ARRAYSTACK_H #include <iostream> #include <sstream> #include <algorithm> #include "pureBaseStack.h" template <typename T> class arrayStack : public stack<T> { public: ~arrayStack() { delete[]element; } arrayStack(int initialCapacity = 10); bool empty() const override final { return stackTop == -1; } int size() const override final { return stackTop + 1; } //void reSetArrayLength(); T& top() const override final; void pop(); void push(const T& theElement); private: T* element; int stackTop; int arrayLength; }; template <typename T> arrayStack<T>::arrayStack(int initialCapacity) { if (initialCapacity < 1) { std::ostringstream s; s << "can't creat a stack with capacity <= 0!" << std::endl; throw s.str(); } element = new T[initialCapacity]; stackTop = -1; arrayLength = initialCapacity; } //template <typename T> //void arrayStack<T>::reSetArrayLength() //{ // T* temp = new T[arrayLength / 2]; // std::cout << "arrayLength/2 = " << arrayLength / 2 << std::endl; // std::copy(element, element + stackTop + 1, temp); // delete[]element; // arrayLength /= 2; // element = temp; //} template <typename T> T& arrayStack<T>::top() const { if (stackTop == -1) { std::ostringstream s; s << "Stack is empty!" << std::endl; throw s.str(); } return element[stackTop]; } template <typename T> void arrayStack<T>::pop() { if (stackTop == -1) { std::ostringstream s; s << "can't pop from an empty stack!" << std::endl; throw s.str(); } element[stackTop--].~T(); //if (stackTop <= arrayLength / 4) //reSetArrayLength(); } template <typename T> void arrayStack<T>::push(const T& theElement) { if (stackTop == arrayLength - 1) { arrayLength *= 2; T* temp = new T[arrayLength]; std::copy(element, element + stackTop + 1, temp); delete[]element; element = temp; } element[++stackTop] = theElement; } #endif 两栈共享空间 // created on 2020.10.21 by Joe #ifndef TWOSTACKS_H_ #define TWOSTACKS_H_ #include <sstream> #include <iostream> template <typename T> class twoStack { public: ~twoStack() { delete[]element; } twoStack(int initialCapacity = 10); bool empty() const { return stackTop1 == -1 && stackTop2 == arrayLength; } int size() const { return stackTop1 - stackTop2 + arrayLength + 1; } T& top(int stackNumber) const; void pop(int stackNumber); void push(int stackNumber, const T& theElement); private: T* element; int stackTop1; int stackTop2; int arrayLength; void check(int stackNumber) const; }; template <typename T> void twoStack<T>::check(int stackNumber) const { if (stackNumber < 1 || stackNumber > 2) { std::ostringstream s; s << "stackNumber input error!" << std::endl; throw s.str(); } } template <typename T> twoStack<T>::twoStack(int initialCapacity) { element = new T[initialCapacity]; arrayLength = initialCapacity; stackTop1 = -1; stackTop2 = arrayLength; } template <typename T> T& twoStack<T>::top(int stackNumber) const { check(stackNumber); switch (stackNumber) { case 1: if (stackTop1 == -1) { std::ostringstream s; s << "stack1 is empty!" << std::endl; throw s.str(); } return element[stackTop1]; break; case 2: if (stackTop2 == arrayLength) { std::ostringstream s; s << "stack2 is empty!" << std::endl; throw s.str(); } return element[stackTop2]; break; } } template <typename T> void twoStack<T>::pop(int stackNumber) { check(stackNumber); switch (stackNumber) { case 1: if (stackTop1 == -1) { std::ostringstream s; s << "stack1 is empty!" << std::endl; throw s.str(); } element[stackTop1--].~T(); break; case 2: if (stackTop2 == arrayLength) { std::ostringstream s; s << "stack2 is empty!" << std::endl; throw s.str(); } element[stackTop2++].~T(); break; } } template <typename T> void twoStack<T>::push(int stackNumber, const T& theElement) { check(stackNumber); if (stackTop1 + 1 == stackTop2) { T* temp = new T[2 * arrayLength]; std::copy(element, element + stackTop1 + 1, temp); std::copy(element + stackTop2, element + arrayLength, temp + arrayLength + stackTop2); delete[]element; element = temp; stackTop2 = arrayLength + stackTop2; arrayLength *= 2; } switch (stackNumber) { case 1: element[++stackTop1] = theElement; break; case 2: element[--stackTop2] = theElement; break; } } #endif几种应用
开关盒布线 // check net and judge #include <iostream> #include "linkedStack.h" bool checkBox(int net[], int n) { linkedStack<int>* s = new linkedStack<int>(n); for (int i = 0; i < n; i++) { if (!s->empty()) { if (net[i] == net[s->top()]) s->pop(); else s->push(i); } else s->push(i); } if (!s->empty()) { std::cout << "box is not routable!" << std::endl; return false; } std::cout << "box is routable!" << std::endl; return true; } 汉诺塔 #include "arrayStack.h" #include <iostream> arrayStack<int> Hanoi[4]; void moveAndShow(int n, int x, int y, int z) { if (n > 0) { moveAndShow(n - 1, x, z, y); int d = Hanoi[x].top(); Hanoi[x].pop(); Hanoi[y].push(d); std::cout << "从" << x << "移动[" << d << "]" << "到" << y << std::endl; moveAndShow(n - 1, z, y, x); } } void HanoiTower(int n) { for (int i = n; i >= 1; i--) Hanoi[1].push(i); moveAndShow(n, 1, 2, 3); } 迷宫老鼠 // find path in a maze #include "arrayStack.h" #include <iostream> const int maxn = 100; int maze[maxn][maxn]; struct position { int row, col; }; bool findPath() { int size; std::cout << "输入迷宫尺寸:"; std::cin >> size; for (int i = 0; i <= size; i++) { maze[0][i] = maze[size + 1][i] = 1; maze[i][0] = maze[i][size + 1] = 1; } arrayStack<position>* path = new arrayStack<position>; int barrRow, barrCol; int n; std::cout << "输入障碍数量:"; std::cin >> n; for (int i = 0; i < n; i++) { std::cin >> barrRow >> barrCol; while(barrRow < 1 || barrCol < 1 || barrRow > size || barrCol > size) { std::cout << "输入的障碍物有误，请输入正确的障碍物坐标:"; std::cin >> barrRow >> barrCol; } maze[barrRow][barrCol] = 1; } position end; std::cout << "输入终点位置:"; std::cin >> end.row >> end.col; while (end.row < 0 || end.col < 0 || end.row > size + 1 || end.col > size + 1) { std::cout << "终点位置不符合规范，请重新输入:"; std::cin >> end.row >> end.col; } position offset[4]; offset[0].row = 0; offset[0].col = 1; offset[1].row = 1; offset[1].col = 0; offset[2].row = 0; offset[2].col = -1; offset[3].row = -1; offset[3].col = 0; position here; here.row = 1; here.col = 1; maze[1][1] = 1; int option = 0; int lastOption = 3; while (here.row != end.row || here.col != end.col) { int r, c; while (option <= lastOption) { r = here.row + offset[option].row; c = here.col + offset[option].col; if (maze[r][c] == 0) break; option++; } if (option <= lastOption) { path->push(here); here.row = r; here.col = c; maze[r][c] = 1; option = 0; } else { if (path->empty()) return false; position next = path->top(); path->pop(); if (next.row == here.row) option = 2 + next.col - here.col; else option = 3 + (next.row - here.row) % 4; here = next; } } while (!path->empty()) { std::cout << "(" << path->top().row << "," << path->top().col << ")" << std::endl; path->pop(); } return true; } 离线等价类 // offline equiralence classes #include <iostream> #include "arrayStack.h" bool offlineEquiralenceClasses() { int n, r; std::cin >> n; if (n < 2) { std::cout << "can't calculate set with elements < 2" << std::endl; return false; } std::cin >> r; if (r < 2) { std::cout << "can't calculate set with relations < 2" << std::endl; return false; } arrayStack<int>* list = new arrayStack<int>[n + 1]; int a, b; for (int i = 1; i <= r; i++) { std::cin >> a >> b; list[a].push(b); list[b].push(a); } arrayStack<int> unprocessedList; bool *out = new bool[n + 1]; for (int i = 1; i <= n; i++) out[i] = false; int tol = 1; for (int i = 1; i <= n; i++) { if (!out[i]) { std::cout << "class " << tol << " is:" << " [" << i << ","; out[i] = true; unprocessedList.push(i); while (!unprocessedList.empty()) { int j = unprocessedList.top(); unprocessedList.pop(); while (!list[j].empty()) { int q = list[j].top(); list[j].pop(); if (!out[q]) { std::cout << q << ","; out[q] = true; unprocessedList.push(q); } } } std::cout << "]" << std::endl; tol++; } } return true; } 括号匹配 #include "arrayStack.h" #include <string> // complexity of time:O(s.size()) // extra complexity of space:O(s.size()) bool matchWithStack(const std::string& s) { arrayStack<char> matchStack; char temp; for (int i = 0; i < s.size(); i++) { if (s[i] == '{' || s[i] == '[' || s[i] == '(') matchStack.push(s[i]); else if (s[i] == '}' || s[i] == ']' || s[i] == ')') { temp = matchStack.top(); if (temp == s[i]) matchStack.pop(); } } if (!matchStack.empty()) return true; return false; } 列车重排 #include "arrayStack.h" arrayStack<int>* rails; int numberOfCars; int numberOfTrails; int smallestCar; int itsTrail; void outputCarFromTrail() { rails[itsTrail].pop(); smallestCar = numberOfCars + 1; for (int i = 1; i <= numberOfTrails; i++) { if (!rails[i].empty() && rails[i].top() < smallestCar) { smallestCar = rails[i].top(); itsTrail = i; } } } bool inputCarToTrail(int n) { int bestTrail = 0; int bestTop = numberOfCars + 1; for (int i = 1; i <= numberOfTrails; i++) { if (!rails[i].empty()) { int d = rails[i].top(); if (n < d && d < bestTop) { bestTop = d; bestTrail = i; } } else bestTrail = i; } if (bestTrail == 0) return false; rails[bestTrail].push(n); if (n < smallestCar) { smallestCar = n; itsTrail = bestTrail; } return true; } bool railRoad(int input[], int theNumberOfCars, int theNumberOfTrails) { numberOfCars = theNumberOfCars; numberOfTrails = theNumberOfTrails; rails = new arrayStack<int>[theNumberOfTrails + 1]; smallestCar = numberOfCars + 1; int nextCarToOutput = 1; for (int i = 1; i <= numberOfCars; i++) { if (input[i] == nextCarToOutput) { nextCarToOutput++; while (smallestCar == nextCarToOutput) { outputCarFromTrail(); nextCarToOutput++; } } else if (!inputCarToTrail(input[i])) return false; } return true; }调用的主函数(屁用没有)
// created on 2020.10.21 by Joe #include <iostream> using namespace std; int main() { return 0; }