C++数据结构之顺序栈

这里我们通过C++实现一个顺序栈结构，内核是数组，但是需要遵循栈的规则，并包含初始化空栈，判断栈是否为空，判断栈是否已满，插入元素，删除元素，获取栈顶元素，具体操作如下所示：

堆栈的基本操作

• 初始化空栈：创建一个空栈，定义栈的大小 size，以及栈顶元素指针 top。
• 判断栈是否为空：当堆栈为空时，返回 True。当堆栈不为空时，返回 False。一般只用于栈中删除操作和获取当前栈顶元素操作中。
• 判断栈是否已满：当堆栈已满时，返回 True，当堆栈未满时，返回 False。一般只用于顺序栈中插入元素和获取当前栈顶元素操作中。
• 插入元素（进栈、入栈）：相当于在线性表最后元素后面插入一个新的数据元素。并改变栈顶指针 top 的指向位置。
• 删除元素（出栈、退栈）：相当于在线性表最后元素后面删除最后一个数据元素。并改变栈顶指针 top 的指向位置。
• 获取栈顶元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该操作并不改变栈顶指针 top 的指向位置。

首先整体结构如下：

template <class T>
class Stack{

public:
    Stack(int size);    //有参构造
    Stack(Stack& sta);    //拷贝构造
    ~Stack();

public:
    bool Empty();    //判空
    bool IsFull();    //判满
    void Push(T &value);  //入栈
    void Push(T &&value);  //常量入栈
    void Pop();  //出栈
    T Top();  //获取栈顶元素

public:
    int size(){ return this->size_; };

private:
    //运算符重载
	T& operator[](int index) {
		return this->pAddr[index];
	}

private:
    int size_;
    int capacity_;  
    T* stack;  //栈
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

如上图所示，这里定义了有参构造和拷贝构造，没定义默认构造，因为这样就涉及动态扩容，这里就不做实现。

然后是堆栈基础操作，判空，判满，入栈，出栈以及获取栈顶元素等操作。

最后还加了size()，和重载了[]运算符，一个共有，一个私有。

数据成员则有三个，分别是当前的元素个数、栈的容量以及栈指针。

接下来，我们看各自的实现。

1.初始化

template <class T>
Stack<T>::Stack(int size):capacity_(size){
    this->size_ = 0;
    this->stack= new T[this->capacity_];
}

template <class T>
Stack<T>::~Stack(){
    if(this->stack!= NULL) delete[] this->stack;
}

template <class T>
Stack<T>::Stack(Stack& sta){
    //容量、大小赋值
	this->capacity_ = sta.capacity_;
	this->size_ = sta.size_;
    //申请空间
	this->stack= new T[this->capacity_];
    //数据拷贝
    for (int i = 0; i < this->size_; i++)
    {
        this->stack[i] = sta.stack[i];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上面三个分别为有参构造，拷贝构造和析构函数。

其中拷贝构造就用到了重载的[]运算符，不过该运算符是私有的，在实例化对象下是不可使用的，因为栈本身就只能索引。

2.判空和判满

template <class T>
bool Stack<T>::Empty(){
    if(0 == this->size_) return true;
    return false;
}

template <class T>
bool Stack<T>::IsFull(){
    if(this->capacity_ == this->size_) return true;
    return false;
}
1
2
3
4
5
6
7
8
9
10
11

判空和判满的实现比较简单，主要以size_和capacity_来进行判断就可以了。

3.压栈

template <class T>
void Stack<T>::Push(T &value){
    if(this->IsFull()){
        cout << "Stack is full"<<endl;
    }
    else{
        this->stack[this->size_++] = value;
    }
}

template <class T>
void  Stack<T>::Push(T&& value) {
    if(this->IsFull()){
        cout << "Stack is full"<<endl;
    }
    else{
        this->stack[this->size_++] = value;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

之所以还需要重载一个Push函数，是因为不能对右值取引用

而解决办法就是使用&&，可以对右值取引用

4.出栈

template <class T>
void Stack<T>::Pop(){
    if(this->Empty()){
        cout << "Stack is empty"<<endl;
    }
    else{
        this->size_--;
    }
}
1
2
3
4
5
6
7
8
9

这里实现的是一个伪出栈，你只需要将size_这个索引-1，就能实现出栈。

5.获取首部元素

template <class T>
T Stack<T>::Top(){
    if(this->Empty()){
        cout << "Stack is empty"<<endl;
    }
    return this->stack[size_-1];
}
1
2
3
4
5
6
7

获取首部元素则只需要通过size_-1即可访问。

最后是测试代码

int main(void){
    Stack<string> s(5);
    cout << s.Empty() <<endl;
    s.Push("nihao");
    s.Push("wohao");
    s.Push("tahao");
    s.Push("dajiahao");
    s.Push("buhao");
    // s.Push("haha");
    cout << s.IsFull() <<endl;
    s.Pop();

    Stack<string> test(s);  //测试拷贝构造函数

    while(!test.Empty()){
        cout << test.Top() << "\t";
        test.Pop();
    }  cout<<endl;

/***************int****************/

    Stack<int> s_int(5);
    cout << s.Empty() <<endl;
    s_int.Push(4);
    s_int.Push(5);
    s_int.Push(6);
    s_int.Push(8);
    s_int.Push(9);
    // s.Push("haha");
    cout << s_int.IsFull() <<endl;
    s.Pop();

    while(!s_int.Empty()){
        cout << s_int.Top() << "\t";
        s_int.Pop();
    }  cout<<endl;


    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

这里对于判满和判空还可以使用异常处理的方式进行，这里不做进一步的拓展。

老规矩，有用二连，感谢大家。