C++实现两栈共享和链栈
语言这个东西不用真的会忘， 我记得前前后后C++的基本语法我也看了好几遍了，一直没有动手写过什么东西，所以一遍遍的看，一遍遍的忘... ...
正好最近在看数据结构，想着自己用C++来实现一下，一方面是熟悉整个逻辑过程，加深对数据结构的理解，另一方面，也熟悉一下C++。
栈（Stack）是一种仅限在表尾进行插入和删除的线性表，允许插入和删除的一端称为栈顶，另一端叫做栈底。栈又被称为先进后出（FILO ：First In Last Out）结构。
由于栈是线性结构，所以同链表一样，可以表示为顺序存储结构和链式存储结构。
0x01 顺序存储结构
下图所示为栈的顺序存储结构示意图：
stack
下图所示为入栈和出栈的示意图：
image.png
我所实现的是两栈共享空间，主要是因为普通的顺序存储栈必须要先确定数组存储大小，一旦分配的内存不够用了就需要进行扩展，所以我们的思路就是将两个栈合并为一个，这样这个数组就有两个栈顶，两个栈底，我们让其中一个栈底为下标0处，另一个栈底为数组长度 length - 1 处，如图所示：
image.png
可见，只要 top1 + 1 不等于 top2，两个栈就可以一直使用。
实现代码：
const int maxSize = 100;
class DoubleStack {
private:
int top1;
int top2;
int data[maxSize]{};
public:
//Constructor
explicit DoubleStack(int top1 = -1, int top2 = maxSize) : top1(top1), top2(top2) {}
/*
* push
* @param stackNum : 表示向哪个栈中存数据
*/
bool push(const int &elem, const int &stackNum) {
if (top1 + 1 == top2) {
cout << "stack is full!" << endl;
return false;
}
if (stackNum == 1) {
data[++top1] = elem;
cout << elem << "已入栈1~" << endl;
return true;
} else if (stackNum == 2) {
data[--top2] = elem;
cout << elem << "已入栈2~" << endl;
return true;
} else {
cout << "stackNum输入有误！！" << endl;
return false;
}
}
//Pop
bool pop(const int &stackNum) {
if (stackNum == 1) {
if (top1 == -1) {
cout << "栈1为空！弹出失败！" << endl;
return false;
} else {
cout << this->data[top1--] << "已弹出栈1!" << endl;
return true;
}
}
if (stackNum == 2) {
if (top2 == maxSize) {
cout << "栈2为空！弹出失败！" << endl;
return false;
} else {
cout << data[top2++] << "已弹出栈2!" << endl;
return true;
}
}
else {
cout << "stackNum输入有误！！" << endl;
return false;
}
}
};
测试代码：
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
int main() {
DoubleStack doubleStack;
doubleStack.push(10, 1);
doubleStack.push(30, 1);
doubleStack.push(40, 1);
doubleStack.push(80, 1);
doubleStack.push(20, 2);
doubleStack.push(50, 2);
doubleStack.pop(1);
doubleStack.pop(1);
doubleStack.pop(1);
doubleStack.pop(1);
doubleStack.pop(2);
doubleStack.pop(2);
doubleStack.pop(1);
doubleStack.pop(2);
return 0;
}
执行结果：
image.png
0x02 链式存储结构
下图所示为栈的链式存储结构示意图：
tCxaZWrn4SGmzI1.png
下图所示为数据入栈以及出栈的示意图：
image.png
下图所示为数据出栈的示意图：
image.png
代码实现：
Stack的代码实现应用到了模板（templa）和友元（friend）
template<typename T>
class Stack;
template<typename T>
class Node {
friend class Stack<T>;
private:
T data;
Node *next;
public:
explicit Node(const T &data = 0) : data{data}, next{nullptr} {}
};
template<typename T>
class Stack {
private:
Node<T> *top;
int length;
public:
//Constructor
Stack() : top(nullptr), length(0) {}
//Default destructor
~Stack() = default;
//Check if the stack is empty
bool isEmpty() const {
if (length == 0)
return true;
else
return false;
}
//Return the length of the stack
int getLength() const {
cout << "The length of the stack is " <<length << endl;
return length;
}
void push(const T &data) {
auto temp = new Node<T>;
temp->data = data;
temp->next = top;
top = temp;
++length;
cout << data << " is pushed!" << endl;
}
void pop() {
if (isEmpty())
cout << "Stack is empty now!" << endl;
else {
auto temp = top;//temp 的类型是Node<T> *
auto elem = temp->data;
top = top->next;
delete temp;
--length;
cout << elem << " is popped!" << endl;
}
}
};
测试代码：
/*
* Software:Jetbrains clion 2022.1
* Created by xiaoxin_zh@foxmail.com
* Implementing Stack with C++
*/
#include <iostream>
using std::cout;
using std::endl;
int main() {
Stack<int> stack;
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
stack.push(9);
stack.getLength();
stack.pop();
stack.pop();
stack.pop();
stack.isEmpty();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
return 0;
}
执行结果：
image.png
