Implementation of stack

Stack is an important data structure. It is a linear structure with the characteristics of last in first out
Because there are two implementations of linear table, there are also two implementations of stack, namely sequential storage structure and chain storage structure
This paper will give an implementation method based on chain storage structure

Storage structure of chain stack

Similar to the storage structure of single linked list, the storage image of chain stack also includes two parts: data field and pointer field The storage structure is shown as follows:

class StackNode
{
	// Here we might as well use T to represent the data type, and we will see its role later
	T data_;
	StackNode* next_;
};

To facilitate the management of a group of Stack nodes, you can define a Stack class as follows:

class Stack
{
private:
	StackNode<T>* ptr_;
	// T here indicates that the stack node data field it points to is of type T
};

Main operations of stack

1. Initialization

The task of initialization is to construct an empty Stack. Unlike the linked list, there is no need to set a header node in the chain Stack, so you only need to empty the pointer at the top of the Stack It can be implemented by using the Stack class constructor, as follows:

	Stack()
	{
		ptr_ = nullptr;
	}

2. Stack

Algorithm steps

1. Create a StackNode object and point to it with pointer ptr
2. Set the node data field to data
3. Insert the new node into the top of the stack
4. Modify the stack top pointer

The specific implementation is as follows:

	bool Stack::push(T data)
	{
		StackNode* ptr = new StackNode(data, ptr_);
		ptr_ = ptr;
		return true;
	}

3. Out of the stack

Algorithm steps

1. Judge whether the stack is empty. If it is empty, return false
2. Assign the stack top element to data
3. Temporarily save the space of the top element of the stack for release
4. Modify the stack top pointer to point to the new stack top element
5. Release the pointer of the original stack top element

The specific implementation is as follows:

	bool Stack::pop(T& data)
	{
		if (ptr_ == nullptr)
		{
			return false;
		}
		data = ptr_->data_;
		StackNode* ptr = ptr_;
		ptr_ = ptr_->next_;
		delete ptr;
		return true;
	}

Where get_data and get_next is a function that returns the data element and pointer of the current node

4. Get stack top element

When the stack is not empty, the value of the current stack top element is returned. The specific implementation is as follows:

	T Stack::get_top()
	{
		if (ptr_ != nullptr)
			return ptr_->data_;
	}

Of course, in addition to these, other interfaces can be defined, such as calculating stack length, clearing stack, etc I will not repeat them here

In fact, so far, the data structure of stack has been basically realized, but there is still room for improvement
For example, if you want to use a stack that stores int data and a stack that stores double data at the same time The above code is powerless Of course, you can define a DoubleStack class to store double data However, it is unrealistic to define classes with the same function separately for each type (because there are user-defined types), and the scope of application is limited Is there a method that can be defined once for all types? have C + + generics

Implementation of stack container

In fact, we can make our stack store any type of data as long as we modify our code a little Like the basic idea, it is integrated as follows:

#pragma once

template <typename T>
// Used to create a stack
class Stack
{
public:
	template <typename T>
	// Used to generate stack nodes
	class StackNode
	{
	public:
		StackNode()
		{
			next_ = nullptr;
		}

		StackNode(T data)
		{
			data_ = data;
			next_ = nullptr;
		}

		StackNode(T data, StackNode* next)
		{
			data_ = data;
			next_ = next;
		}

		// Data field of stack node
		T data_;
		// Pointer field to the next stack node
		StackNode* next_;
	};
	// Insert element at top of stack
	bool push(T);
	// Pop up the top element of the stack and save it
	bool pop(T&);
	// Pop up stack top element
	bool pop();
	// Get stack top element
	T get_top();
	// Empty stack
	void clear();
	// Find stack length
	size_t length();
	// Determine whether the stack is empty
	bool is_empty();

	Stack()
	{
		ptr_ = nullptr;
		length_ = 0;
	}

private:
	// The head pointer of the stack, which can mark a stack
	StackNode<T>* ptr_;
	// Stack length
	size_t length_;
};

template <typename T>
bool Stack<T>::push(T data)
{
	StackNode<T>* ptr = new StackNode<T>(data, ptr_);
	ptr_ = ptr;
	++length_;
	return true;
}

template <typename T>
bool Stack<T>::pop(T& data)
{
	if (ptr_ == nullptr)
	{
		return false;
	}
	data = ptr_->data_;
	StackNode<T>* ptr = ptr_;
	ptr_ = ptr_->next_;
	delete ptr;
	--length_;
	return true;
}

template <typename T>
bool Stack<T>::pop()
{
	if (ptr_ == nullptr)
	{
		return false;
	}
	StackNode<T>* ptr = ptr_;
	ptr_ = ptr_->next_;
	delete ptr;
	--length_;
	return true;
}

template <typename T>
inline T Stack<T>::get_top()
{
	return ptr_->data_;
}

template <typename T>
void Stack<T>::clear()
{
	while (ptr_)
	{
		StackNode<T>* ptr = ptr_;
		ptr_ = ptr_->next_;
		delete ptr;
	}
	length_ = 0;
}

template <typename T>
inline size_t Stack<T>::length()
{
	return length_;
}

template <typename T>
bool Stack<T>::is_empty()
{
	if (ptr_)
	{
		return false;
	}
	return true;
}

test

Test code can be written to test whether the code is correct, as follows:

#include <iostream>
#include "linkstack.h" / / the stack container we wrote is stored here

using namespace std;

int main(void)
{
	Stack<double> double_stack;
	Stack<int> int_stack;
	for (size_t i = 1; i < 10; i++)
	{
		double_stack.push(i * 2.5);
		int_stack.push(i);
	}
	cout << "double Stack length:" << double_stack.length() << endl;
	cout << "int Stack length:" << int_stack.length() << endl;
	cout << "eject double First 5 elements of stack\n";
	for (size_t i = 1; i < 5; i++)
	{
		double data;
		double_stack.pop(data);
		cout << data << " ";
	}
	cout << "\ndouble Stack: my length has changed. become:" << double_stack.length() << endl;
	cout << "int Stack: my length hasn't changed. Or:" << int_stack.length() << endl;
	return 0;
}

The operation results are as follows:

Next, test whether user-defined types can be stored correctly. You can define a plane point set as follows:
Note: do not use the default constructor here

class CPoint
{
private:
	int x_;
	int y_;
public:
	CPoint()
	{
		x_ = 0;
		y_ = 0;
	}
	CPoint(int x, int y)
	{
		x_ = x;
		y_ = y;
	}
	friend std::ostream& operator<<(std::ostream& out, CPoint point)
	{
		out << "(" << point.x_ << "," << point.y_ << ")";
		return out;
	}
};

The test code is as follows:

#include <iostream>
#include "linkstack.h" / / the stack container we wrote is stored here

using namespace std;

int main(void)
{
	Stack<CPoint> stack_point;
	for (size_t i = 1; i < 10; i++)
	{
		CPoint point(i, i * i);
		stack_point.push(point);
	}
	cout << "Now the stack length is:" << stack_point.length() << endl;
	cout << "Pop up all elements:" << endl;
	while (!stack_point.is_empty())
	{
		CPoint point;
		stack_point.pop(point);
		::std::cout <<point << " ";
	}
	cout << "\n Now the stack length is:" << stack_point.length() << endl;
	system("pause");
	return 0;
}

The results are as follows:

This is great. Using generics, our stack can store not only basic data types, but also user-defined types. Well, this may be called one-time programming and benefit for life!