首页 > > 程序设计 > C/C++ >

C++ 栈（链表实现）

2018-12-24 09:01:57来源：博客园阅读 ()

第一、基本概念

栈中的元素遵守“先进后出”的原则(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"; 
}