利用LinearList类定义Stack

设计思路

首先定义了Linear List类使得其能够实现线性表的各项操作。声明线性表类的三个成员变量Address（整形指针），size（表内存储的数据量），capacity（线性表的容量），默认第一个元素的位置为1。实现成员函数，insert函数pos位置之后插入一个元素x，remove函数删除位置pos处的元素，element函数返回位置pos处的元素，search函数查找值为x的元素并返回元素的位置，若未找到返回0，length函数返回元素的个数。

定义Linear List类的派生类Stack，继承的方式为私有，防止用户调用Linear List类的函数，而破坏栈数据结构的稳定性。在实现Stack类的成员函数时，使用作用域解析运算符，调用Linear List类的成员函数，以实现代码的复用。

实现成员函数，push函数将元素x推入栈中，pop函数弹出栈顶元素，top函数返回栈顶元素，is Empty函数判断栈是否为空，get size函数返回栈中元素的个数。

代码实现：

linearlist.hpp

#pragma once
#include<iostream>
using namespace std;
class LinearList
{
public:
	LinearList(int);
	LinearList(const LinearList& arr);
	LinearList(LinearList&& arr)noexcept;
	~LinearList();
	bool insert(int x, int pos);
	bool remove(int& x, int pos);
	int element(int pos)const;
	int search(int x)const;
	int length()const;
private:
	int* Address;
	int size;
	int capacity;
};
class Stack:private LinearList
{
public:
	Stack(int capacity = 10) : LinearList(capacity) {}
	void push(int x);
	bool pop(int& x);
	int top();
	bool isEmpty();
	int get_size();
};

stack.cpp

#include "linearlist.hpp"
#include<algorithm>
using namespace std;
LinearList::LinearList(int c):size(0),capacity(c){
	Address = new int[capacity];
}
LinearList::LinearList(const LinearList& arr):size(arr.size),capacity(arr.capacity)
{
	Address = new int[capacity];
	copy(arr.Address, arr.Address + size, Address);
}
LinearList::LinearList(LinearList&& arr)noexcept:Address(arr.Address), size(arr.size), capacity(arr.capacity)
{
    arr.Address = nullptr;
    arr.size = 0;
    arr.capacity = 0;
}
LinearList::~LinearList(){
    delete[] Address;
}
bool LinearList::insert(int x, int pos)
{
    if (pos < 0 || pos > size || size >= capacity) return false;
    for (int i = size; i > pos; --i) {
        Address[i] = Address[i - 1];
    }
    Address[pos] = x;
    ++size;
    return true;
}
bool LinearList::remove(int& x, int pos)
{
    pos -= 1;//由于第一个元素位置为1，所以设置偏置
    if (pos < 0 || pos >= size) return false;
    x = Address[pos];
    for (int i = pos; i < size - 1; ++i) {
        Address[i] = Address[i + 1];
    }
    --size;
    return true;
}
int LinearList::element(int pos)const
{
    pos -= 1;//偏置
    if (pos < 0 || pos >= size) throw std::out_of_range("Index out of range");
    return Address[pos];
}
int LinearList::search(int x)const
{//第一个元素位置为1
    int pos = 0;
    for (int i = 0; i < size; ++i) {
        if (Address[i] == x) { pos = i + 1; break; }
    }
    return pos;
}
int LinearList::length()const { return size; }

void Stack::push(int x)
{
    if (!LinearList::insert(x, LinearList::length())) {
        cout << "The Stack is Full!" << endl;
    }
}
bool Stack::pop(int& x)
{
    if (this->isEmpty()) {
        return false; // 如果栈为空，则无法执行出栈操作
    }
    return LinearList::remove(x, LinearList::length());
}
int Stack::top()
{
    if (isEmpty()) {
        cout << "The Stack is Empty!" << endl; return -1;
    }
    return LinearList::element(LinearList::length());
}
bool Stack::isEmpty(){return LinearList::length() == 0;}
int Stack::get_size() { return LinearList::length(); }