第3篇 C++数据结构--Stack实现

前言

本篇会使用最终实现的LinkedList作为Stack的基类，因为LinkedList有高效的push_front头部插入方法，一般来说，栈是不讲究排序和中间插入操作的，那么使用LinkedList可以给我们的Stack实现简化了很多代码。LinkedList的详细内容见下面链接

• 《第2篇 C++ 数据结构-链表概述》
• 《第2篇 C++ 数据结构-单链表(多图杀猫)》
• 《第2篇 C++ 数据结构-LinkedList的性能优化》

像栈是FIFO这些废话我就不多说了,我以前花了大部分时间讨论到它《C/C++内存管理》，再说我要呕吐囧....

直接入正题

Stack类接口

Stack的类接口是由LinkedList扩展而来，我们使用了protected的继承模式，因为我们不想Stack的类实现向外部调用代码暴露LinkedList的成员方法和数据成员.如果你对继承不了解的话可以查看《C++ 面向对象》文集

#ifndef __STACK_HH__
#define __STACK_HH__
#include "./LinkedList.hh"

template <class T>
class Stack : protected LinkedList<T>
{
private:
    size_t d_maxsize;

public:
    Stack();
    Stack(size_t);
    ~Stack();

    Node<T> *top();
    void push(const T &v);
    T pop();
    T peek();
    bool is_empty();
    bool is_full();

    //打印链表
    template <class R>
    friend std::ostream &operator<<(std::ostream &, const LinkedList<R> &);
};
#endif

Stack类实现

#include "../headers/Stack.hh"
#include "./LinkedList.cpp"
#include <iostream>
#include <stdlib.h>

//自定义构造函数
template <class T>
Stack<T>::Stack() : d_maxsize(10)
{
    LinkedList<T>::d_head = nullptr;
    LinkedList<T>::d_size = 0;
    LinkedList<T>::d_last = nullptr;
}

//用户构造函数
template <class T>
Stack<T>::Stack(size_t n) : d_maxsize(n)
{
    LinkedList<T>::d_head = nullptr;
    LinkedList<T>::d_last = nullptr;
}

template <class T>
Stack<T>::~Stack()
{
    LinkedList<T>::clear();
}

template <class T>
void Stack<T>::push(const T &v)
{
    LinkedList<T>::push_head(v);
}

template <class T>
Node<T> *Stack<T>::top()
{
    return LinkedList<T>::d_head;
}

template <class T>
T Stack<T>::pop()
{
    if (LinkedList<T>::d_size)
    {
        LinkedList<T>::pop_front();
    }
}

//窥视栈定的数据
template <class T>
T Stack<T>::peek()
{
    if (LinkedList<T>::d_size)
    {
        return LinkedList<T>::front();
    }
}

//检测栈是否为空
template <class T>
bool Stack<T>::is_empty()
{
    if (LinkedList<T>::d_head == nullptr || LinkedList<T>::d_size == 0)
    {
        return true;
    }
    return false;
}

//检查栈是否已满
template <class T>
bool Stack<T>::is_full()
{
    if (LinkedList<T>::d_size > d_maxsize)
    {
        return true;
    }
    else
    {
        return false;
    }
}

template <class R>
std::ostream &operator<<(std::ostream &os, Stack<R> &st)
{
    Node<R> *nod = st.top();
    os << "————top————" << std::endl;
    while (nod->next())
    {
        os << nod->elem() << std::endl;
        std::cout << "_________" << std::endl;
        nod = nod->next();
    }
    os << "————base————" << std::endl;
    return os;
}

测试代码

void test_stack()
{
    Stack<int> st;
    for (size_t i = 0; i < 5; i++)
    {
        st.push(i);
    }
    std::cout << "入栈操作" << std::endl;
    std::cout << st << std::endl;

    std::cout << "栈定的元素是" << st.peek() << std::endl;

    std::cout << "开始出栈操作" << std::endl;

    st.pop();
    st.pop();

    std::cout << "栈是否为空" << st.is_empty() << std::endl;
    std::cout << st << std::endl;
    st.pop();
    st.pop();
    st.pop();
    std::cout << "栈是否为空" << st.is_empty() << std::endl;
}

输出结果