《数据结构、算法与应用C++语言描述》使用C++语言实现数组栈

定义

栈的定义

把线性表的插入和删除操作限制在同一端进行，就得到栈数据结构。因此，栈是一个后进先出（last-in-first-out，LIFO）的数据结构。

栈（stack）是一种特殊的线性表，其插入（也称入栈或压栈）和删除（也称出栈或弹栈）操作都在表的同一端进行。这一端称为栈顶（top），另一端称为栈底（bottom）。

递归工作栈

计算机是如何执行递归函数的呢？

答案是使用递归工作栈（recursionstack）。当一个函数被调用时，一个返回地址（即被调函数一旦执行完，接下去要执行的程序指令的地址）和被调函数的局部变量和形参的值都要存储在递归工作栈中。当执行一次返回时，被调函数的局部变量和形参的值被恢复为调用之前的值（这些值存储在递归工作栈的顶部），而且程序从返回地址处继续执行，这个返回地址也存储在递归工作栈的顶部。

栈的抽象数据类型

代码

_14stack.h

抽象类栈。

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			抽象类栈
*/
#pragma once
#ifndef _STACK_H_
#define _STACK_H_
/*抽象类栈*/
template<class T>
class stack
{
public:virtual ~stack() {}//返回true，当且仅当栈为空virtual bool empty() const = 0;//返回栈中元素个数virtual int size() const = 0;//返回栈顶元素的引用virtual T& top() = 0;//删除栈顶元素virtual T pop() = 0;//将元素theElement压入栈顶virtual void push(const T& theELment) = 0;
};
#endif

_15arrayStack.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			数组存储的栈类的头文件
*/
#pragma once
#ifndef _ARRAYSTACK_H_
#define _ARRAYSTACK_H_
#include "_1myExceptions.h"
#include "_14stack.h"
#include<iostream>
#include<sstream>
#include<cstring>
using std::ostringstream;
using std::endl;
using std::cout;
using std::istream;
using std::ostream;
using std::string;
//测试函数
void arrayStackTest();
/*
作用：将数组的长度加倍
输入：指针a指向需要改变长度的数组，oldLength表示数组原来的长度，newLength表示需要改变的新长度
结果：将数组扩容/缩容 为newLength
*/
template<class T>
void changeLength(T*& a, int oldLength, int newLength)
{if (newLength < 0)throw illegalParameterValue("new length must be >= 0");T* temp = new T[newLength];int number = min(oldLength, newLength);copy(a, a + number, temp);delete[] a;a = temp;
}/*本来可以直接派生arrayList来实现，但是该方法会损失性能。*/
/*因此本节开发一个类，利用数组来包含所有的栈元素*/
template<class T>
class arrayStack :public stack<T>
{
public:arrayStack(int initialCapacity = 10);~arrayStack() { delete[] stack; }bool empty() const { return stackTop == -1; }int size() const { return stackTop + 1; }int capacity() const { return stackLength; }T& top(){if (stackTop == -1)throw stackEmpty();return stack[stackTop];}T pop(){if (stackTop == -1)throw stackEmpty();T temp = stack[stackTop];stack[stackTop--].~T();//T的析构函数while (stackTop + 1 < stackLength / 4){changeLength(stack, stackLength, stackLength / 2);stackLength /= 2;}return temp;}void push(const T& theElement);void clear() { stackTop = -1; }void split(arrayStack<T>& a, arrayStack<T>& b);void merge(arrayStack<T>& a);/*重载操作符*//*重载操作符[]*/T& operator[](int i) { return stack[i]; }/*友元函数*/friend istream& operator>> <T>(istream& in, arrayStack<T>& m);//输出但是不pop()元素friend ostream& operator<< <T>(ostream& out, arrayStack<T>& m);
private:int stackTop;//当前栈顶int stackLength;//栈容量T* stack;//元素数组
};
/*友元函数*/
/*>>操作符*/
template<class T>
istream& operator>>(istream& in, arrayStack<T>& m)
{int numberOfElement = 0;cout << "Please enter the number of element:";while (!(in >> numberOfElement)){in.clear();//清空标志位while (in.get() != '\n')//删除无效的输入continue;cout << "Please enter the number of element:";}T cinElement;for (int i = 0; i < numberOfElement; i++){cout << "Please enter the element " << i + 1 << ":";while (!(in >> cinElement)){in.clear();//清空标志位while (in.get() != '\n')//删除无效的输入continue;cout << "Please enter the element " << i + 1 << ":";}m.push(cinElement);}return in;
}
/*<<操作符*/
template<class T>
ostream& operator<<(ostream& out, arrayStack<T>& m)
{for (int i = 0; i <= m.stackTop; i++)out << m.stack[i] << "  ";out << endl;return out;
}/*构造函数*/
template<class T>
arrayStack<T>::arrayStack(int initialCapacity)
{if (initialCapacity < 1){ostringstream s("");s << "Initial capacity = " << initialCapacity << "Must be > 0";throw illegalParameterValue(s.str());}stackLength = initialCapacity;stack = new T[initialCapacity];stackTop = -1;
}/*将元素theElement压入栈*/
template<class T>
void arrayStack<T>::push(const T& theElement)
{if (stackTop == stackLength - 1){//空间已满，容量加倍changeLength(stack, stackLength, 2 * stackLength);stackLength *= 2;}stack[++stackTop] = theElement;
}
/*将一个栈分裂为两个栈。第一个栈包含从栈底开始的一半元素，第二个栈包含剩余元素*/
template<class T>
void arrayStack<T>::split(arrayStack<T>& a, arrayStack<T>& b)
{//首先清空a,b栈b.clear();a.clear();/*将当前栈中的前一半元素存入a栈中*/int i = 0;for (i = 0; i <= stackTop / 2; i++)a.push(stack[i]);/*将当前栈中的后一半元素存入b栈中*/for (; i <= stackTop; i++)b.push(stack[i]);
}
/*将两个栈合并，把第二个栈的所有元素置于第一个栈的顶部。不改变第二个栈中元素的相对顺序*/
template<class T>
void arrayStack<T>::merge(arrayStack<T>& a)
{for (int i = 0; i <= a.stackTop; i++)push(a.stack[i]);
}
#endif

_15arrayStack.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			测试_15arrayStack.h头文件中的所有函数
*/
// test array based sparse matrix class#include <iostream>
#include "_15arrayStack.h"
using namespace std;/*测试函数*/
void arrayStackTest()
{cout << endl << "*********************************arrayStackTest()函数开始*************************************" << endl;arrayStack<int> a;//测试输入和输出cout << endl << "测试友元函数*******************************************" << endl;cout << "输入输出************************" << endl;cin >> a;cout << "arrayStack a is:" << a;//arrayStack a is:1  2  3  4  5  6cout << endl << "测试成员函数*******************************************" << endl;cout << "empty()*************************" << endl;cout << "a.empty() = " << a.empty() << endl;//a.empty() = 0cout << "size()**************************" << endl;cout << "a.size() = " << a.size() << endl;//a.size() = 6cout << "top()***************************" << endl;cout << "a.top() = " << a.top() << endl;//a.top() = 6cout << "pop()***************************" << endl;cout << "a.capacity() = " << a.capacity() << endl;//a.capacity() = 10cout << "arrayStack a is:" << a;//arrayStack a is:1  2  3  4  5  6cout << "a.pop() = " << a.pop() << endl;//a.pop() = 6cout << "a.pop() = " << a.pop() << endl;//a.pop() = 5cout << "a.pop() = " << a.pop() << endl;//a.pop() = 4cout << "a.pop() = " << a.pop() << endl;//a.pop() = 3cout << "a.pop() = " << a.pop() << endl;//a.pop() = 2cout << "arrayStack a is:" << a;//arrayStack a is:1cout << "a.capacity() = " << a.capacity() << endl;//a.capacity() = 5cout << "push()**************************" << endl;a.push(99);cout << "arrayStack a is:" << a;//arrayStack a is:1  99cout << "split()*************************" << endl;arrayStack<int> b, c;a.split(b, c);cout << "arrayStack a is:" << a;//arrayStack a is:1  99cout << "arrayStack b is:" << b;//arrayStack b is:1cout << "arrayStack c is:" << c;//arrayStack c is:99cout << "merge()*************************" << endl;a.merge(b);cout << "arrayStack a is:" << a;//arrayStack a is:1  99  1cout << "arrayStack b is:" << b;//arrayStack b is:1cout << "*********************************arrayStackTest()函数结束*************************************" << endl;
}

main.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			main()函数，控制运行所有的测试函数
*/
#include <iostream>
#include "_15arrayStack.h"int main()
{arrayStackTest();return 0;
}

_1myExceptions.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include <string>
#include<iostream>using namespace std;// illegal parameter value
class illegalParameterValue
{
public:illegalParameterValue(string theMessage = "Illegal parameter value"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// illegal input data
class illegalInputData
{
public:illegalInputData(string theMessage = "Illegal data input"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// illegal index
class illegalIndex
{
public:illegalIndex(string theMessage = "Illegal index"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// matrix index out of bounds
class matrixIndexOutOfBounds
{
public:matrixIndexOutOfBounds(string theMessage = "Matrix index out of bounds"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// matrix size mismatch
class matrixSizeMismatch
{
public:matrixSizeMismatch(string theMessage ="The size of the two matrics doesn't match"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// stack is empty
class stackEmpty
{
public:stackEmpty(string theMessage ="Invalid operation on empty stack"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// queue is empty
class queueEmpty
{
public:queueEmpty(string theMessage ="Invalid operation on empty queue"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// hash table is full
class hashTableFull
{
public:hashTableFull(string theMessage ="The hash table is full"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// edge weight undefined
class undefinedEdgeWeight
{
public:undefinedEdgeWeight(string theMessage ="No edge weights defined"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};// method undefined
class undefinedMethod
{
public:undefinedMethod(string theMessage ="This method is undefined"){message = theMessage;}void outputMessage() { cout << message << endl; }
private:string message;
};
#endif