C + + stack (implementation of linked list)

First, basic concepts

The elements in the stack follow the principle of "first in first out" (LIFO,Last In First Out)

You can only insert and delete at the top of the stack

Push (or push or push) is push, put the data on the top of the stack and add a pointer to the top of the stack

Pop (Pop-Up) is pop. Delete the data from the top of the stack and decrease the top pointer by one

The basic operations of the stack are: pop, push, judge empty, obtain the top element of the stack, and calculate the stack size

Second, implementation mode

Generally, the stack is implemented in array or linked list 2, each with its own characteristics. Here, I use the inverted linked list implementation

Third, code implementation

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

template <typename T> class Stack {
    int length; //Number of stacks
    node<T> *head; //Header of a stack
public:
    Stack() { length = 0; head = new node<T>; }
    void push(T arg); //Push
    T pop();  //Stack out
    T top(); //Get stack top element

    void print(); //Print stack
    int size(); //Get the number of elements in the stack
    bool isEmpty(); //Judgement empty
};

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;
}

test

#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"; 
}

Tags: C++

Posted on Mon, 02 Dec 2019 23:35:05 -0800 by PHPnewby!