Stack, shared stack, chained stack (C++ implementation)

Article directory

• Preface
• 1. Sequential storage of stack (sequential stack)
• 2. Basic operations of the stack
• • Push operation
  • Pop operation
  • Get the top element of the stack
  • Get the length of the stack
  • Determine whether the stack is empty
  • Determine whether the stack is full
  • Print the elements in the stack
  • Test function
• 3. Shared stack
• • Code
• 4. Chain stack
• • Code
• 5. Summary

Foreword

The stack is a linear list. However, it can only perform insertion and deletion operations at one end. The data pushed into the stack first can only come out later, and the data pushed into the stack later can only come out first. Therefore, the stack has the characteristics of first in, last out or last in, first out. Generally speaking, we can understand the stack as a restricted linear list.

If we compare the stack to a container like a barrel, the stack has two ends. The end that allows insertion and deletion operations is called the top of the stack (top), which is the mouth of the barrel, or the mouth of the barrel. The tail of the linear table, and the other end is called the bottom of the stack, which is also the bottom of the barrel, or the head of the linear table. A stack that does not contain any data is called an empty stack (empty linear list).

After the overall structure is clarified, let’s talk about the related operations. Inserting elements into the stack can be called Pushing or pushing into the stack, and deleting elements from the stack is called Popping. In addition to being able to insert and delete data at the end of the table, for a data structure like the stack, inserting and deleting data at any other location should not be allowed. You can only provide operation interfaces that comply with this requirement, otherwise the implementation will not be a stack.

The stack is also called a linear list of Last In First Out (LIFO), which means that the last data put into the stack (inserted data) can only be removed from the stack first. Take it out (delete data).

In fact, there are many situations in our lives where the stack is last-in-first-out. For example, when putting things in a drawer, the items put in first will definitely be piled at the end, so they can only be taken out last, and the items put in last are often in the bottom. The front or top, so it will be taken out first.

If you use a schematic diagram to represent the process of using the stack to access data, it will look like the following figure:

In the picture above, if the data a1, a2, a3, a4, and a5 are stored in the stack respectively, then when the data is popped out of the stack, the order should be a5, a4, a3, a2, a1 (the same as the order in which it is pushed into the stack). exactly the opposite).

The stack is a restricted linear list. For example, because elements can only be inserted and deleted at the top of the stack, the location of the insertion and deletion operations cannot be specified. Therefore, the operations supported by the stack can Understood as a subset of linear table operations, it generally includes operations such as stack creation, pushing onto the stack (adding data), popping out of the stack (deleting data), obtaining the top element of the stack (finding data), and determining whether the stack is empty or full.

1. Sequential storage of stack (sequential stack)

The so-called sequential stack means sequential storage (storage in sequence in a continuous memory space) of the data in the stack.

There are 2 options for saving data:

• Save data by statically allocating memory for a one-dimensional array.
• Save data by dynamically allocating memory for a one-dimensional array.

In order to expand the stack when the data in the sequential stack is full, here, I will use the second method of saving data to write the implementation code of the sequential stack.

In addition, in order to take into account the convenience of element access, it is most appropriate to use the end of the array with index 0 as the bottom of the stack.

2. Basic operations of stack

First perform class definition, initialization and release operations.

#define InitSize 10 //Initial size of dynamic array
#define IncSize 5 //When the dynamic array is full of data, the number of data elements that can be saved each time it is expanded.

template <typename T>
classSeqStack
{<!-- -->
public:
SeqStack(int length = InitSize); //Constructor, parameters can have default values
~SeqStack(); //Destructor

public:
bool Push(const T & amp; e); //Push onto the stack (add data)
bool Pop(T & e); //Pop the stack (delete data), that is, delete the data on the top of the stack
bool GetTop(T & amp; e); //Read the top element of the stack, but the element is not popped off the stack but is still on the stack

void DispList(); //Output all elements in the sequence stack
int ListLength(); //Get the length of the sequential stack (actual number of elements)

bool IsEmpty(); //Determine whether the sequence stack is empty
bool IsFull(); //Determine whether the sequence stack is full

private:
void IncreaseSize(); //When the sequential stack is full of data, you can call this function to expand the sequential stack.

private:
T* m_data; //Storage elements in the sequential stack
int m_maxsize; //Maximum capacity of dynamic array
int m_top; //The top pointer of the stack (used as an array subscript) points to the top element of the stack. The value of -1 indicates an empty stack.
};

//Initialize the sequential stack through the constructor
template <typename T>
SeqStack<T>::SeqStack(int length)
{<!-- -->
m_data = new T[length]; //Dynamicly allocate memory for one-dimensional array
m_maxsize = length; //The sequential stack can store up to m_maxsize data elements
m_top = -1; //Empty stack
}

//Release resources of the sequential stack through the destructor
template <typename T>
SeqStack<T>::~SeqStack()
{<!-- -->
delete[] m_data;
}

In the main function, add code to create a sequential stack object with an initial size of 10.

int main()
{<!-- -->
SeqStack<int> st(10);
return 0;
}

After it is created, the sequence stack will look like the following figure, which is an empty stack at this time:

Push operation

Pushing onto the stack and adding data, the usual time complexity is

O

(

1

)

O(1)

O(1), but once expansion is required, the time complexity will become

O

(

n

)

O(n)

O(n)

Code

template <typename T>
bool SeqStack<T>::Push(const T & amp; e)
{<!-- -->
if (IsFull() == true)
{<!-- -->
IncreaseSize(); //Expansion
}

m_data[ + + m_top] = e; //Storage element e, the top pointer of the stack moves backward
return true;
}

When the sequential stack is full of data, you can call this function to expand the sequential stack. The time complexity is

O

(

n

)

O(n)

O(n)

template<class T>
void SeqStack<T>::IncreaseSize()
{<!-- -->
T* p = m_data;
m_data = new T[m_maxsize + IncSize]; //Reallocate larger memory space for the sequential stack
for (int i = 0; i <= m_top; i + + )
{<!-- -->
m_data[i] = p[i]; //Copy data to new area
}
m_maxsize = m_maxsize + IncSize; //The maximum length of the sequential stack increases by IncSize
delete[] p; //Release the original memory space
}

Pop operation

Pop the stack and delete the data, that is, delete the data on the top of the stack. The time complexity is

O

(

1

)

O(1)

O(1)

template <typename T>
bool SeqStack<T>::Pop(T & amp; e)
{<!-- -->
if (IsEmpty() == true)
{<!-- -->
cout << "The current sequence stack is empty and the pop operation cannot be performed!" << endl;
return false;
}

e = m_data[m_top--]; //The value of the top element of the stack is returned to e.
\t
return true;
}

Get the top element of the stack

Read the top element of the stack, but the element is not popped off the stack but is still on the top of the stack, so the value of m_top will not change, and the time complexity is

O

(

1

)

O(1)

O(1)

Code

template <typename T>
bool SeqStack<T>::GetTop(T & amp; e)
{<!-- -->
if (IsEmpty() == true)
{<!-- -->
cout << "The current sequence stack is empty and the top element of the stack cannot be read!" << endl;
return false;
}

e = m_data[m_top]; //The top element of the stack is returned to e.
return true;
}

Get the length of the stack

Get the length of the sequential stack (actual number of elements), the time complexity is

O

(

1

)

O(1)

O(1)

Code

template<class T>
int SeqStack<T>::ListLength()
{<!-- -->
return m_top + 1;
}

Determine whether the stack is empty

Determine whether the sequence stack is empty, the time complexity is

O

(

1

)

O(1)

O(1)

Code

template<class T>
bool SeqStack<T>::IsEmpty()
{<!-- -->
if (m_top == -1)
{<!-- -->
return true;
}
return false;
}

Determine whether the stack is full

Determine whether the sequence stack is full, the time complexity is

O

(

1

)

O(1)

O(1)

Code

template<class T>
bool SeqStack<T>::IsFull()
{<!-- -->
if (m_top >= m_maxsize - 1)
{<!-- -->
return true;
}
return false;
}

Print elements in the stack

Output all elements in the sequential stack, the time complexity is

O

(

n

)

O(n)

O(n)

Code

template<class T>
void SeqStack<T>::DispList()
{<!-- -->
//Display data in order from top of stack to bottom of stack
for (int i = m_top; i >= 0; --i)
{<!-- -->
cout << m_data[i] << " "; //Each data is separated by spaces
}
cout << endl; //Newline
}

Test function

In the main function, add test code.

Code

int main()
{<!-- -->
SeqStack<int> st(10);
\t
//Push to stack
st.Push(10);
st.Push(20);
st.Push(30);
st.Push(40);
st.Push(50);
\t
\t//Print
st.DispList();
\t
//Get the top element of the stack
int elem = 0;
st.GetTop(elem);
cout << elem << endl;
\t
//pop
st.Pop(elem);
st.Pop(elem);
\t
\t//Print
st.DispList();
\t
return 0;
}

The running results are as follows:

In some code that implements the stack, the initial value of m_top will be equal to 0 (pointing to the position of 0), so the code to determine whether the stack is empty (IsEmpty function) is to determine m_top Is it equal to 0, and the condition for judging that the stack is full (IsFull function) should also become if (m_top >= m_maxsize).

This implementation actually lets m_top represent the subscript of the next element that can be put on the stack. When data is pushed onto the stack (Push function), the code line m_top + + The execution order of code> and the code line m_data[m_top] = e needs to be exchanged, and when the data is popped off the stack (Pop function), the code line e = m_data[m_top] and code lines m_top-- also needs to be reversed.

//Shared stack
template <typename T> //T represents the type of elements in the array
class ShareStack
{<!-- -->
public:
ShareStack(int length = InitSize) //Constructor, parameters can have default values
{<!-- -->
m_data = new T[length]; //Dynamicly allocate memory for one-dimensional array
m_maxsize = length; //The shared stack can store up to m_maxsize data elements
m_top1 = -1; //The top pointer of sequential stack 1 is -1, indicating an empty stack
m_top2 = length; //The top pointer of sequential stack 2 is length, indicating an empty stack
}
~ShareStack() //Destructor
{<!-- -->
delete[] m_data;
}

public:
bool IsFull() //Determine whether the shared stack is full
{<!-- -->
if (m_top1 + 1 == m_top2)
{<!-- -->
return true;
}
return false;
}

bool Push(int stackNum, const T & amp; e) //Push onto the stack (add data), the parameter stackNum is used to identify stack 1 or stack 2
{<!-- -->
if (IsFull() == true)
{<!-- -->
//The shared stack is full. You can also add code by yourself to support dynamically increasing the capacity of the shared stack. This is a simple process and returns false directly.
cout << "The shared stack is full and no more push operations can be performed!" << endl;
return false;
}
if (stackNum == 1)
{<!-- -->
//What is to be entered is sequence stack 1
m_top1 + + ; //The top pointer of the stack moves backward
m_data[m_top1] = e;
}
else
{<!-- -->
//What is to be entered is sequence stack 2
m_top2--;
m_data[m_top2] = e;
}
return true;
}

bool Pop(int stackNum, T & amp; e) //Pop the stack (delete data), that is, delete the data on the top of the stack
{<!-- -->
if (stackNum == 1)
{<!-- -->
//To pop from sequence stack 1
if (m_top1 == -1)
{<!-- -->
cout << "The current sequence stack 1 is empty and the pop operation cannot be performed!" << endl;
return false;
}
e = m_data[m_top1]; //The value of the top element of the stack is returned to e
m_top1--;
}
else
{<!-- -->
//To pop from sequence stack 2
if (m_top2 == m_maxsize)
{<!-- -->
cout << "The current sequence stack 2 is empty and the pop operation cannot be performed!" << endl;
return false;
}
e = m_data[m_top2];
m_top2 + + ;
}
return true;
}

private:
T* m_data; //Storage elements in the shared stack
int m_maxsize; //Maximum capacity of dynamic array
int m_top1; //Stack top pointer of sequential stack 1
int m_top2; //Stack top pointer of sequential stack 2
};

//Definition of each node in the chain stack
template <typename T> //T represents the type of data element
struct StackNode
{<!-- -->
T data; //data field, stores data elements
StackNode<T>* next; //Pointer field, pointing to the next node of the same type (same type as this node)
};

//Definition of chain stack
template <typename T>
class LinkStack
{<!-- -->
public:
LinkStack(); //Constructor
~LinkStack(); //Destructor

public:
bool Push(const T & amp; e); //Push element e onto the stack
bool Pop(T & e); //Pop the stack (delete data), that is, delete the data on the top of the stack
bool GetTop(T & amp; e); //Read the top element of the stack, but the element is not popped off the stack but is still on the stack

void DispList(); //Output all elements in the chain stack
int ListLength(); //Get the length of the chain stack
bool Empty(); //Determine whether the chain stack is empty

private:
StackNode<T>* m_top; //Stack top pointer
int m_length; //Current length of chain stack
};


//Initialize the chain stack through the constructor
template <typename T>
LinkStack<T>::LinkStack()
{<!-- -->
m_top = nullptr;
m_length = 0;
}


//Release resources of the chain stack through the destructor
template <typename T>
LinkStack<T>::~LinkStack()
{<!-- -->
T tmpnousevalue = {<!-- --> 0 };
while (Pop(tmpnousevalue) == true) {<!-- -->} //Delete all the elements on the top of the stack, and the while loop will exit. At this time, the stack will be empty.
}


//Push element e onto the stack, the time complexity is O(1)
template <typename T>
bool LinkStack<T>::Push(const T & amp; e)
{<!-- -->
StackNode<T>* node = new StackNode<T>;
node->data = e;
node->next = m_top;
m_top = node;
m_length + + ;
return true;
}


//Pop the stack (delete data), that is, delete the data on the top of the stack. The time complexity is O(1)
template <typename T>
bool LinkStack<T>::Pop(T & amp; e)
{<!-- -->
if (Empty() == true) //The chain stack is empty
return false;

StackNode<T>* p_willdel = m_top;
m_top = m_top->next;
m_length--;
e = p_willdel->data;
delete p_willdel;
return true;
}


//Read the top element of the stack, but the element is not popped off the stack but is still on the stack
template <typename T>
bool LinkStack<T>::GetTop(T & amp; e)
{<!-- -->
if (Empty() == true) //The chain stack is empty
return false;

e = m_top->data;
return true;
}


//Output all elements in the chain stack, the time complexity is O(n)
template<class T>
void LinkStack<T>::DispList()
{<!-- -->
if (Empty() == true) //The chain stack is empty
return;

StackNode<T>* p = m_top;
while (p != nullptr)
{<!-- -->
cout << p->data << " "; //Each data is separated by spaces
p = p->next;
}
cout << endl; //Newline
}


//Get the length of the chain stack, the time complexity is O(1)
template<class T>
int LinkStack<T>::ListLength()
{<!-- -->
return m_length;
}


//Determine whether the chain stack is empty, the time complexity is O(1)
template<class T>
bool LinkStack<T>::Empty()
{<!-- -->
if (m_top == nullptr) //The chain stack is empty
{<!-- -->
return true;
}
return false;
}