C++ 栈 （链表实现）

第一、基本概念

栈中的元素遵守“先进后出”的原则(lifo,last in first out)

　　只能在栈顶进行插入和删除操作

　　压栈（或推入、进栈）即push，将数据放入栈顶并将栈顶指针加一

　　出栈（或弹出）即pop，将数据从栈顶删除并将栈顶指针减一

　　栈的基本操作有：pop，push，判断空，获取栈顶元素，求栈大小

第二、实现方式

 栈一般 采用数组或者链表2中方式实现，各有各的特点，我这里采用倒插法链表实现

第三、代码实现

#pragma once
#include <iostream>
using namespace std;
template<class t> struct node {
    t value;  //储存的值
    node<t>* next;
    node() :next(nullptr) {};
    node(t t) : value(t), next(nullptr) {}
};

template <typename t> class stack {
    int length; //入栈数量
    node<t> *head; //栈的头部
public:
    stack() { length = 0; head = new node<t>; }
    void push(t arg); //入栈
    t pop();  //出栈
    t top(); //获取栈顶元素

    void print(); //打印栈
    int size(); //获取栈内元素个数
    bool isempty(); //判断空
};

template<typename t>
void stack<t>::push(t arg) {
    node<t>* pnode = new node<t>(arg);
    pnode->next = head->next;
    head->next = pnode;
    length++;
}


template<typename t>
t stack<t>::pop() {
    if (head->next!=null)
    {
        node<t>* pnode = head->next;
        t pdata = pnode->value;
        head->next = head->next->next;
        delete pnode;
        return pdata;
    }
}

template<typename t>
t stack<t>::top() {
    while (head->next!=null)
    {
        return head->next->value;
    }
}

template<typename t>
void stack<t>::print() {
    while (head->next != null)
    {
        head = head->next;
        cout << head->value << endl;
    }
}
template<typename t>
int stack<t>::size() {
    return length;
}

template<typename t>
bool stack<t>::isempty() {
    return length == 0;
}

view code

测试

#include "pch.h"
#include "stack.h"
#include <iostream>
using namespace std;

int main()
{
    stack<int> st;
    st.push(1);
    st.push(2);
    st.push(4);

    st.print();

    std::cout << "hello world!\n"; 
}