# 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. MyStack.h

```#ifndef _MY_STACK_H
#define _MY_STACK_H

template<typename T>

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(){};
private:
T data;
};

template<typename T>
{
public:

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>
:top(nullptr), size(0)
{
}
template <typename T>
{
while (!Empty()){
Pop();
}
}

//push function
template <typename T>
{
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>
{
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>
{
if (!Empty())
else
exit(1);
}

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

#endif
```

main.cpp

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

using namespace std;

int main()
{

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.

Keywords: C++ data structure stack

Added by social_experiment on Sat, 12 Feb 2022 05:52:15 +0200