双栈:数组实现
结构描述:
#include <iostream>
#include <cstdlib>
#define MAX 100
using namespace std;
typedef int DataType;
class DoubleStack {
public:
DataType *A;
//两个栈的栈顶
int TP;
int TB;
//建立一个空栈
void Init();
//判空、判满
bool IsEmpty();
bool IsFull();
//入栈,根据Top的值入栈
void Push(DataType X, int Top);
//出栈,根据Top的值出栈
void Pop(int Top);
//摧毁栈
void MakeEmpty();
//获取栈顶元素,根据栈顶的值
DataType GetTopValue(int Top);
//获取两个栈顶的指针
int GetTP();
int GetTB();
};
初始化
栈顶指针分别置为 -1
和 MAX
即可;
为 A
分配空间
void DoubleStack::Init() {
A = (DataType *)malloc(sizeof (DataType) * MAX);
TP = -1;
TB = MAX;
}
判空、判满
栈空时即两个栈顶都是初始位置
栈满时,TP + 1 == TB
bool DoubleStack::IsFull() {
return TP + 1 == TB;
}
bool DoubleStack::IsEmpty() {
return TP == -1 && TB == MAX;
}
入栈
- 栈满:报错
- 非满:
- 根据传入的参数,选择对哪个栈进行操作;
Top == TP
则A[++TP] = X;
Top == TB
则A[--TB] = X;
void DoubleStack::Push(DataType X, int Top) {
//栈非空
if (IsFull()) {
cout << "Stack Is Full!" << endl;
exit(-1);
}
if (Top == TP) {
A[++TP] = X;
}
else if (Top == TB) {
A[--TB] = X;
}
else {
cout << "This is not the top of the stack!" << endl;
exit(-1);
}
}
出栈
- 栈空:报错
- 非空:
- 根据栈顶的值来进行操作:
if (Top == TP) TP--;
if (Top == TB) TB++;
else Err;
- 根据栈顶的值来进行操作:
void DoubleStack::Pop(int Top) {
if (IsEmpty()) {
cout << "Stack is Empty!" << endl;
exit(-1);
}
if (Top == TP) {
TP--;
}
else if (Top == TB) {
TB++;
}
else {
cout << "This is not the top of stack!" << endl;
exit(-1);
}
}
获取栈顶元素
- 栈空:报错
- 非空:根据传入的栈顶信息,直接返回
DataType DoubleStack::GetTopValue(int Top) {
if (IsEmpty()) {
cout << "Stack is empty!\n";
exit(-1);
}
else {
return A[Top];
}
}
摧毁
- 栈空:报错
- 非空:一直出栈,直至栈空
void DoubleStack::MakeEmpty() {
if (IsEmpty()) {
cout << "Stack is empty!\n";
exit(-1);
}
while (TP != -1) {
Pop(TP);
}
while (TB != MAX) {
Pop(TB);
}
}
获取栈顶指针
- 栈空:报错
- 非空:返回
int DoubleStack::GetTP() {
if (IsEmpty()) {
cout << "Stack is empty!\n";
exit(-1);
}
return TP;
}
int DoubleStack::GetTB() {
if (IsEmpty()) {
cout << "Stack is empty!\n";
exit(-1);
}
return TB;
}
错误记录
把TP
自增,却用Top
为下标给其赋值,怪不得会出错
void DoubleStack::Push(DataType X, int Top) {
if (Top == TP) {
TP++;
}
else if (Top == TB) {
TB--;
}
else {
cout << "This is not the top of the stack!" << endl;
exit(-1);
}
A[Top] = X;
}
标签:DoubleStack,实现,Top,栈顶,双栈,int,TP,数组,TB
From: https://www.cnblogs.com/codels/p/18309484