栈是一种只能在表的顶端进行插入和删除运算的线性表，其主要特点是后进先出（LIFO）或先进后出（FILO），该数据结构的示意图如下：
| 函数名 | 用途 |
|---|---|
| bool empty() | 判断栈是否为空 |
| int size(); | 求栈的长度 |
| int top() | 求栈顶元素 |
| void push(int data) | 在栈顶插入元素 |
| void pop() | 从栈顶弹出元素 |
| void display() | 遍历打印栈元素 |
class Stack1 {
private:
int data[10];
int length;
public:
Stack1();
~Stack1();
bool empty();
int size();
int top();
void push(int value);
void pop();
void display();
};
#include<iostream>
#include"Stack_By_Array.h"
using namespace std;
Stack1::Stack1() {
length = 0;
}
Stack1::~Stack1() {}
bool Stack1::empty() {
return length == 0;
}
int Stack1::size() {
return length;
}
void Stack1::push(int value) {
if (length < 10) {
data[length++] = value;
}
else {
cout << "栈已满，无法继续添加元素。" << endl;
}
}
int Stack1::top() {
return data[length - 1];
}
void Stack1::pop() {
length -= 1;
}
void Stack1::display() {
if (length == 0) {
cout << "栈为空!" << endl;
return;
}
for (int i = length - 1; i >= 0; i--) {
cout << data[i] << endl;
}
cout << "-------------------------------" << endl;
}
class Stack2
{
private:
class Node
{
public:
int data;
Node* next;
Node(int data, Node* next);
~Node();
};
Node* head;
size_t length;
public:
Stack2();
~Stack2();
bool empty();
int size();
int top();
void push(int data);
void pop();
void display();
};
#include<iostream>
#include"Stack_By_LinkedList.h"
using namespace std;
Stack2::Node::Node(int data, Node* next) {
this->data = data;
this->next = next;
}
Stack2::Node::~Node() {
}
Stack2::Stack2() {
this->head = nullptr;
this->length = 0;
}
Stack2::~Stack2() {
while (this->head != nullptr) {
Node* temp = this->head;
this->head = this->head->next;
delete temp;
}
}
bool Stack2::empty() {
return this->head == nullptr;
}
int Stack2::size() {
return this->length;
}
int Stack2::top() {
if (head != nullptr) {
return this->head->data;
}
}
void Stack2::push(int data) {
Node* new_node = new Node(data, nullptr);
new_node->next = head;
head = new_node;
this->length++;
}
void Stack2::pop() {
if (head == nullptr) {
return;
}
Node* p = head;
head = head->next;
delete p;
this->length--;
}
void Stack2::display() {
if (this->head == nullptr) {
cout << "栈为空!" << endl;
return;
}
Node* p = this->head;
while (p != nullptr) {
cout << p->data << endl;
p = p->next;
}
cout << "-------------------------------" << endl;
}
在"Stack Testing.cpp"中的代码如下：
#include<iostream>
#include"Stack_By_Array.h"
#include"Stack_By_LinkedList.h"
using namespace std;
void test_Stack_By_Array() {
Stack1 stack;
cout << "测试1：数组实现的栈：" << endl;
cout << "---------------------------------" << endl;
cout << "将1-6依次入栈后，打印栈元素如下：" << endl;
for (int i = 1; i <= 6; i++) {
stack.push(i);
}
stack.display();
cout << "栈顶元素为：" << stack.top() << endl;
cout << "-------------------------------" << endl;
for (int i = 0; i < 2; i++) {
stack.pop();
}
cout << "弹出两个元素后，栈元素如下：" << endl;
stack.display();
for (int i = 0; i < 4; i++) {
stack.pop();
}
cout << "弹出所有元素后，栈内情况为：" << endl;
stack.display();
}
void test_Stack_By_LinkedList() {
Stack2* stack = new Stack2();
cout << "测试2：链表实现的栈：" << endl;
cout << "---------------------------------" << endl;
cout << "将1-6依次入栈后，打印栈元素如下：" << endl;
for (int i = 1; i <= 6; i++) {
stack->push(i);
}
stack->display();
cout << "栈顶元素为：" << stack->top() << endl;
cout << "-------------------------------" << endl;
for (int i = 0; i < 2; i++) {
stack->pop();
}
cout << "弹出两个元素后，栈元素如下：" << endl;
stack->display();
for (int i = 0; i < 4; i++) {
stack->pop();
}
cout << "弹出所有元素后，栈内情况为：" << endl;
stack->display();
delete stack;
}
int main() {
test_Stack_By_Array();
cout << endl;
test_Stack_By_LinkedList();
return 0;
}
输出结果如下:
可以看出，两中方法实现的数组功能完全一致。