preface

The third part of self-made type, stack type. Stack refers to stack. In fact, I personally think stack is the best type to write. There is no one. The queue type needs to involve a circular queue to avoid wasting memory, but the insertion and deletion of stack are easier to write at the top of the stack.
The main purpose of self-made type is to practice data structure and improve the ability of writing code.

Common functions

s.empty() determines whether the stack s is empty
s.size() returns the size of stack s
s.push(a) push a onto the stack
s.pop() pop up stack top element
s.top() returns the top element of the stack

generic paradigm

We are using the stack of the standard library, which is written as follows:

stack<int> stk;

Specifying a type with angle brackets is one kind of generics. If you change int to char, or even structure, you can.
The simplest example:

#include<iostream>
#include<vector>
using namespace std;
int main(){
	int a=5,b=10;cout<<max(a,b);
	float c=3.14,d=9.99;cout<<max(c,d);
	char e='x',f='*';cout<<max(e,f);
}

Here, the max function can handle both int and float,char type maxima. This is generics. The max function operates the same regardless of the type. Therefore, we use generic types so that functions do not focus on types, but only on specific operations.
Some people will ask, in fact, can't it be completed by using function overloading? However, it is inconvenient to write function overloads repeatedly several times.

Generic functions can be written using the template keyword:

#include<iostream>
#include<vector>
using namespace std;
template<typename T>
T MAX(T a,T b){
	if(a>b)return a;
	else return b;
}
int main(){
	int a=5,b=10;cout<<MAX(a,b);
	float c=3.14,d=9.99;cout<<MAX(c,d);
	char e='x',f='*';cout<<MAX(e,f);
}

template means to define a type called T, which is a general type. This statement tells the compiler to start generic programming, where T is the generic type to use.
During execution, the compiler will automatically convert T into int,float and other types for calculation according to the type of parameters.
Note that generic functions do not undergo automatic type conversion, such as cout < < max ('a ', 100); If this statement uses a generic type, it will compile an error, but if it uses a common type, it will not report an error, because the function of a common type will carry out automatic type conversion.

Writing method of generic class:

template<typename T>
class Vector{
	T *numbers;
	
};

(transfer to the self-made vector type I wrote before)
In this way, it can be defined like a standard library.
In class functions, for parameters and some class variables, you also need to specify the type as T, which is also T * in the forced transformation of malloc and realloc.

General writing

class Stack{
private:
  T *Data;
  int nData;
public:
  Stack(){
    Data=nullptr;
    nData=0;
  }
  bool empty(){
    if(nData==0)return true;
    else return false;
  }
  int size(){
    return nData;
  }
  void push(T a){
    nData++;
    if(Data==nullptr)Data=(T*)malloc(sizeof(T));
    Data=(T*)realloc(Data,nData*sizeof(T));
    Data[nData-1]=a;
  }
  void pop(){
    if(nData==0)return;
    nData--;
    Data=(T*)realloc(Data,nData*sizeof(T));
  }
  T top(){
    return Data[nData-1];
  }
};

Writing of constructor

Initialize Data and nData. The meaning of variables is very simple. I won't say more.

empty

Just judge the size of the stack. If the size is 0, it indicates an empty stack.

size

Returns nData.

push

Important play

  void push(T a){
    nData++;
    if(Data==nullptr)Data=(T*)malloc(sizeof(T));
    Data=(T*)realloc(Data,nData*sizeof(T));
    Data[nData-1]=a;
  }

First, add 1 to the size of the stack. Then, if it is a null pointer, use malloc allocation (there was nothing), otherwise use realloc allocation. Dynamic memory allocation can save memory space. Finally, put the push value at the top of the stack.

pop

The operation of pop is also very simple.

  void pop(){
    if(nData==0)return;
    nData--;
    Data=(T*)realloc(Data,nData*sizeof(T));
  }

pop operation requires special judgment on nData. If the size is zero, exit directly, otherwise an error will occur during allocation.
If nData=0, the parameter of realloc is 0, which is equivalent to using free(Data).

top

Returns the stack top element Data[nData-1].