C++数据结构——链栈（基本代码实现与案例）

本文主要是介绍C++数据结构——链栈（基本代码实现与案例），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一：基本代码实现

#include<iostream>
using namespace std;enum error_code {success, underflow
};struct node
{int data;node* next; // 指向下一结点
};class linkStack {
public:linkStack();~linkStack();bool empty()const;error_code get_top(int& x)const;error_code push(const int x);error_code pop();
private:int count;node* top; // 指向自己
};linkStack::linkStack()
{count = 0;top = NULL;
}linkStack::~linkStack()
{while (!empty()) pop();
}bool linkStack::empty()const {return count == 0;
}error_code linkStack::get_top(int& x)const
{if (empty()) return underflow;x = top->data;return success;
}error_code linkStack::push(const int x)
{node* s = new node;s->data = x;s->next = top;top = s;count++;return success;
}error_code linkStack::pop()
{if (empty()) return underflow;node* s = new node;s = top;top = s->next;delete s;count--;return success;
}bool ReferenceError(error_code a)
{if(a == underflow){cout << "underflow!" << endl;return false;}return success;
}int main()
{linkStack s;int top;for(int i = 0; i < 10; i++) // 入栈 ReferenceError(s.push(i));for(int i = 0; i < 3; i++) // 出栈 ReferenceError(s.pop());ReferenceError(s.get_top(top)); // 取栈顶cout << "栈顶元素：" << top << endl; return 0;
}

二：链栈案例

案例一：设计算法将十进制转换为八进制
案例二：符号"{“，”}“，”[“，”]“，”(“,”)"应该是互相匹配的，设计算法对以字符串形式读取的表达式S，判断其中的各括号是否是匹配的
案例三：使用栈结构写一个能计算带括号的四则表达式表达式的计算器

#include<iostream>
using namespace std;enum error_code {success, underflow
};template <class T>
struct node
{T data;node<T>* next;
};template <class T>
class linkStack {
public:linkStack();~linkStack();bool empty()const;error_code getTop(T& x)const;error_code push(const T x);error_code pop();
private:T count;node<T>* top;
};template <class T>
linkStack<T>::linkStack()
{count = 0;top = NULL;
}template <class T>
linkStack<T>::~linkStack()
{while (!empty()) pop();
}template <class T>
bool linkStack<T>::empty()const {return count == 0;
}template <class T>
error_code linkStack<T>::getTop(T& x)const
{if (empty()) return underflow;x = top->data;return success;
}template <class T>
error_code linkStack<T>::push(const T x)
{node<T>* s = new node<T>;s->data = x;s->next = top;top = s;count++;return success;
}template <class T>
error_code linkStack<T>::linkStack::pop()
{if (empty()) return underflow;node<T>* s = new node<T>;s = top;top = s->next;delete s;count--;return success;
}bool ReferenceError(error_code a)
{if (a == underflow) {cout << "underflow!" << endl;return false;}return success;
}// 十进制转八进制
void transform()
{// 初始化题目条件 int num, result = 0;cout << "请输入要转化为八进制的十进制数：";cin >> num;// 初始化栈结构 linkStack<int>s;int top; // 开始运算 while(num != 0){s.push(num % 8);num /= 8;}while(!s.empty()){s.getTop(top);s.pop();result = result * 10 + top; }cout << "转成八进制为：" << result << endl;
}// 检验符号匹配
string symbol()
{// 初始化题目条件string s;cout << "请输入表达式S: ";cin >> s;int length;length = s.length();// 初始化栈结构linkStack<char>a;char top;// 开始运算for(int i = 0; i < length; i++){if(s[i] == '(' || s[i] == '[' || s[i] == '{')a.push(s[i]);if(s[i] == ')'){a.getTop(top);if(top == '(')a.pop();elsereturn "不匹配！！";}if(s[i] == ']'){a.getTop(top);if(top == '[')a.pop();elsereturn "不匹配！！";}if(s[i] == '}'){a.getTop(top);if(top == '{')a.pop();elsereturn "不匹配！！";} }return "匹配！！";
}// 计算器
int getRes(int a, int b, char c) // 计算
{  int result;switch(c){case '+': result = a + b;break;case '-': result = a - b;break;case '*': result = a * b;break;case '/': result = a / b;break;}return result;
}
int getPri(char a) // 获得优先级 
{if(a == ')')return 1; if(a == '+' || a == '-')return 2;if(a == '*' || a == '/')return 3;if(a == '(')return 4;elsecout << "输入错误！！" << endl;
}
void calculator()
{// 初始化题目条件string s;cout << "请输入计算式：";cin >> s;int i = 0, k = 1, num1, num2;char sign;// 初始化栈结构linkStack<int>num;int top_n;linkStack<char>oper;char top_o;// 开始计算if(s[(s.length() - 1)] != '='){cout << "算式请以 '=' 结尾";return;	} while(s[i] != '='){if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '(' || s[i] == ')'){l:if(!oper.empty()){oper.getTop(top_o);if(getPri(s[i]) > getPri(top_o) || top_o == '(')oper.push(s[i]);else{oper.getTop(top_o);if(top_o != '('){num.getTop(top_n);num1 = top_n;num.pop();num.getTop(top_n);  num.pop();num.push(getRes(top_n, num1, top_o));oper.pop();oper.getTop(top_o);if(top_o == '('){oper.pop();i++;continue;	}goto l;  	}}}if(oper.empty())oper.push(s[i]); k = 1;}else{if(k == 0){num.getTop(top_n);num.pop();num.push(top_n * 10 + s[i] - 48);	}if(k == 1){num.push(s[i] - 48);k = 0;}}i++;}num.getTop(top_n);num1 = top_n;num.pop();num.getTop(top_n);oper.getTop(top_o);cout << "计算结果为：" << getRes(top_n, num1, top_o) << endl;
}int main()
{// 十进制转八进制transform();// 检验符号匹配cout << symbol() << endl;// 计算器calculator();return 0;
}