1. What is a chain stack?

Since the allocation of each element in the stack in memory is not continuous, the connection between elements is realized through a pointer in each element node. As shown below:

It can be seen that the head of the linked list is used as the top of the stack.

2. Comparison between sequential stack and chain stack

As mentioned earlier, sequential stack is implemented by array. Can refer to Using C + + to realize sequential stack (taking array as the underlying data structure, which can be expanded automatically) . Its disadvantage is obvious: the size of the stack is always a predetermined length, so we can't ignore the problems caused by stack space. Although we add the function of automatic inclusion in the sequential stack, which can well solve the problem that the stack size is fixed in advance, it can be predicted that when the number of elements changes greatly during the use of the stack, sometimes it is small and sometimes it is large, which is a great waste of memory space.

Compared with sequential stack, chained stack does not need to determine the stack size in advance. The stack size changes continuously with the operation of entering and leaving the stack. Moreover, the chain stack is always a radish and a pit. When there is a radish, a pit is generated; When pop is pulled out, the pit is filled, which eliminates the waste of memory space. Of course, the chained stack also has its limitations: each element has a pointer field, which also increases the memory overhead.

3. Common operations of chain stack

The chain stack operates in the same order as the stack:

• i. stack push: put data into the stack
• ii. Out of stack pop: delete the data at the top of the stack
• iii. get the top element of the stack without deleting it: top();
• iV. get the current stack size: size();
• V. judge whether the current state of the stack is empty, i.e. empty();

4. Implementation details of push () and pop()

1. Push():
   Step 1: since the stack element is in the form of nodes, we need to generate a node tmp.
   Step 2: make tmp point to top;
   Part III: modify the value of top to make it top = tmp.

1. Pop():

Step 1: first save the next address at the top of the stack with the temporary variable tmp;
Step 2: free the memory of top,
Step 3: let top point to the address saved in step 1.

5. Example: detailed comments are added to the code

MyStack.h

#ifndef _MY_STACK_H
#define _MY_STACK_H

template<typename T>
class LinkStack;

template<typename T>
class StackNode
{
	friend class LinkStack<T>;//The life stack class is a friend of the node class to access its private data
public:
	StackNode(){};
	StackNode(T _data) :data(_data), link(nullptr){};
	~StackNode(){};
private:
	T data;
	StackNode<T>* link;
};

template<typename T>
class LinkStack
{
public:	
	LinkStack();
	~LinkStack();

	void Push(const T& _data);//Push 
	void Pop();//delete
	T& Top();//Return stack top data
	bool Empty();//Determine whether the stack is empty
	int Size();//Returns the size of the stack

private:
	StackNode<T> *top;//Stack top pointer
	int size;//Current stack size
};


//Constructors and Destructors 
template <typename T>
LinkStack<T>::LinkStack()
:top(nullptr), size(0)
{
}
template <typename T>
LinkStack<T>::~LinkStack()
{
	while (!Empty()){
		Pop();
	}
}


//push function
template <typename T>
void LinkStack<T>::Push(const T& _data)
{
	StackNode<T> *tmp = new StackNode<T>(_data);//Generate a new stack element node and assign an initial value_ data
	tmp->link = top;//The element node of push points to the original stack top
	top = tmp;//The element node of push is the top of the stack

	size++;//Stack size + 1
}

//pop function
template <typename T>
void LinkStack<T>::Pop()
{
	if (!Empty()){
		StackNode<T> *tmp = top->link;//Save the next element at the top of the stack because it will become the top of the stack
		delete top;
		top = tmp;

		size--;//Stack size - 1
	}
	else exit(1);
}

//Return stack top data
template <typename T>
T& LinkStack<T>::Top()
{
	if (!Empty())
		return top->data;//Stack top data returned when stack is not empty
	else
		exit(1);
}

//Check whether the stack is empty
template <typename T>
bool LinkStack<T>::Empty()
{
	if (size > 0)
		return false;
	else
		return true;
}
//Returns the size of the stack
template <typename T>
int LinkStack<T>::Size()
{
	return size;
}

#endif

main.cpp

#include <iostream>
#include "MyStack.h"

using namespace std;

int main()
{
	LinkStack<int> st;
	
	for (int i = 1; i <= 11; i++){
		st.Push(i); //Push 
	}

	while (!st.Empty())
	{
		cout << "size = " << st.Size() << "\t"; //Print the current stack size
		cout << "top = " << st.Top() << endl; //Print current stack top data
		st.Pop();//Out of stack
	}

	system("pause");
	return 0;
}

Test results:

Sequential stack implementation:
Using C + + to realize sequential stack (taking array as the underlying data structure, which can be expanded automatically)

The above is the introduction of chain stack. My level is limited. You are welcome to criticize and correct.