Template Class Encapsulation (2) - Sequential Stack and Linked Stack

C++ language, linked stack implementation

Experiment content:

Program to implement the following functions of the stack:
(1) Establish a sequential stack of length n, with element types defined by yourself, and output the values of each element in the stack.
(2) Push data element e onto the stack, and output the values of each element in the sequential stack after the push operation.
(3) Pop the top element from the sequential stack, and output the value of the popped element and the values of each element in the sequential stack after the pop operation.

Program to implement the following functions of the queue:
(1) Establish a circular queue of length n, with element types defined by yourself, and output the values of each element in the queue.
(2) Enqueue data element e, and output the values of each element in the queue after the enqueue operation.
(3) Dequeue the front element of the circular queue, and output the value of the dequeued element and the values of each element in the queue after the dequeue operation.

Program to implement the following functions of the linked stack:
Establish a linked stack of length n, with element types defined by yourself, and implement typical operations such as stack initialization, push, and pop.

Overall, the first is to implement the basic operations of the sequential stack and linked stack: push operation (Push), pop operation (Pop), get top element (Top), check if the stack is empty (IsEmpty), check if the stack is full (IsFull), get the number of elements in the stack (Size), display all elements in the stack (PrintStack), clear all elements in the stack (Clear). The second is to implement the basic operations of the queue: enqueue operation (Push), dequeue operation (Pop), get front element (Front), check if the queue is empty (IsEmpty), check if the queue is full (IsFull), get the number of elements in the queue (Size), display all elements in the queue (PrintQueue), clear all elements in the queue (Clear). It is still encapsulating a template class. Initialization and destruction operations are implemented in the constructor and destructor functions.
@[TOC](Table of Contents)

Sequential Stack#

Definition of Sequential Stack Operation Class#

// Definition of sequential stack
template <class T> class myStack1 {
private:
	int MaxSize;  // Stack capacity
	T* Data;	  // Data
	int top;  // Records the top element of the stack, which is the index after the top element, top is 0 when empty
public:
	myStack1(int maxsize = 100);  // Constructor to allocate space
	~myStack1();				   // Destructor to reclaim space
	void PrintStack();		   // Display all elements in the sequential stack
	void Push(T data);	// Push operation, increment top value, store element item at the top of the stack
	T Pop();			// Pop operation, return the popped element, decrement top value
	T Top();			// Get the top element, do not pop
	int Size();			// Get the number of elements in the stack
	bool IsEmpty();		// Check if the stack is empty
	bool IsFull();		// Check if the stack is full
};

Main Operations#

(1) Constructor and Destructor#

template <class T>
myStack1<T>::myStack1(int maxsize) : MaxSize(maxsize), top(0) {
	Data = new T[maxsize];
};
template <class T> myStack1<T>::~myStack1() {
	if (Data)
		delete[] Data;
}

(2) Check if the Stack is Empty or Full#

// Check if the stack is empty
template <class T> bool myStack1<T>::IsEmpty() {
	return top == 0;
}
// Check if the stack is full
template <class T> bool myStack1<T>::IsFull() {
	return top == MaxSize;
}

(3) Push Operation#

Store element data at the top of the stack, increment top value

template <class T> void myStack1<T>::Push(T data) {
	if (IsFull()) {
		cout << "error: Failed to Push, The Stack is Full!" << endl;
	} else {
		Data[top++] = data;
	}
}

(4) Get Top Element#

Get the top element, do not pop

template <class T> T myStack1<T>::Top() {
	if (IsEmpty()) {
		cout << "error: The Top isn't existed, The Stack is Empty!" << endl;
		return error;  // ERROR is a special value in type T
	} else {
		return Data[top - 1];
	}
}

(5) Get Number of Elements in the Stack#

template <class T> int myStack1<T>::Size() {
	return top;
}

(6) Pop Operation#

Pop the top element, decrement top value

template <class T> T myStack1<T>::Pop() {
	if (IsEmpty()) {
		cout << "error: Failed to Pop, The Stack is Empty!" << endl;
		return error;  // ERROR is a special value in type T
	} else {
		T temp = Data[--top];
		return temp;
	}
}

(7) Display All Elements in the Sequential Stack#

template <class T> void myStack1<T>::PrintStack() {
	if (IsEmpty())
		cout << "This Stack is empty!" << endl;
	for (int i = 0; i < top; ++i) {
		cout << "The " << i + 1 << "th Data is:";
		cout << Data[i] << endl;
	}
	cout << "The Stack has " << top << " elements in total." << endl;
}

Complete Code#

// Sequential Stack
#include <bits/stdc++.h>
#define error -1
using namespace std;
// Definition of sequential stack
template <class T> class myStack1 {
private:
	int MaxSize;  // Stack capacity
	T* Data;	  // Data
	int top;  // Records the top element of the stack, which is the index after the top element, top is 0 when empty
public:
	myStack1(int maxsize = 100);  // Constructor to allocate space
	~myStack1();				   // Destructor to reclaim space
	void PrintStack();		   // Display all elements in the sequential stack
	void Push(T data);	// Push operation, increment top value, store element item at the top of the stack
	T Pop();			// Pop operation, return the popped element, decrement top value
	T Top();			// Get the top element, do not pop
	int Size();			// Get the number of elements in the stack
	bool IsEmpty();		// Check if the stack is empty
	bool IsFull();		// Check if the stack is full
};

// Implementation of sequential stack operation class
// Constructor to allocate space
template <class T>
myStack1<T>::myStack1(int maxsize) : MaxSize(maxsize), top(0) {
	Data = new T[maxsize];
};
// Destructor to release space
template <class T> myStack1<T>::~myStack1() {
	if (Data)
		delete[] Data;
}
// (1) Check if the stack is empty
template <class T> bool myStack1<T>::IsEmpty() {
	return top == 0;
}
// (2) Check if the stack is full
template <class T> bool myStack1<T>::IsFull() {
	return top == MaxSize;
}
// (3) Push operation
// Store element data at the top of the stack, increment top value
template <class T> void myStack1<T>::Push(T data) {
	if (IsFull()) {
		cout << "error: Failed to Push, The Stack is Full!" << endl;
	}
	else {
		Data[top++] = data;
	}
}
// (4) Get top element, do not pop
template <class T> T myStack1<T>::Top() {
	if (IsEmpty()) {
		cout << "error: The Top isn't existed, The Stack is Empty!" << endl;
		return error;  // ERROR is a special value in type T
	}
	else {
		return Data[top - 1];
	}
}
// (5) Get number of elements in the stack
template <class T> int myStack1<T>::Size() {
	return top;
}
// (6) Pop operation
// Pop the top element, decrement top value
template <class T> T myStack1<T>::Pop() {
	if (IsEmpty()) {
		cout << "error: Failed to Pop, The Stack is Empty!" << endl;
		return error;  // ERROR is a special value in type T
	}
	else {
		T temp = Data[--top];
		return temp;
	}
}
// (7) Display all elements in the sequential stack
template <class T> void myStack1<T>::PrintStack() {
	if (IsEmpty())
		cout << "This Stack is empty!" << endl;
	for (int i = 0; i < top; ++i) {
		cout << "The " << i + 1 << "th Data is:";
		cout << Data[i] << endl;
	}
	cout << "The Stack has " << top << " elements in total." << endl;
}
// Functions called in the main function (for testing)
template <class T> void Stack_Push(myStack1<T>& S) {
	T data;
	cout << "Please enter the element to push onto the stack:";
	cin >> data;
	S.Push(data);
	cout << "------------- After Push, Stack S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Pop(myStack1<T>& S) {
	T data = S.Pop();
	if (data != error) {
		cout << "The popped element is:";
		cout << data << endl;
	}
	cout << "------------- After Pop, Stack S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Top(myStack1<T>& S) {
	T data = S.Top();
	if (data != error) {
		cout << "The top element is:";
		cout << data << endl;
	}
}
template <class T> void Stack_Size(myStack1<T>& S) {
	cout << "The number of elements in this stack is:" << S.Size() << endl;
}
template <class T> void Stack_PrintStack(myStack1<T>& S) {
	cout << "---------------------- Stack S --------------------" << endl;
	S.PrintStack();
}
int main() {
	int n;
	cout << "Enter n, to create a sequential stack of length n:";
	cin >> n;
	myStack1<int> S(n);
	cout << "Enter n elements:" << endl;
	for (int i = 0; i < n; ++i) {
		int data;
		cin >> data;
		S.Push(data);
	}
	cout << "1 Push operation" << endl;
	cout << "2 Pop operation" << endl;
	cout << "3 Get top element" << endl;
	cout << "4 Get number of elements in the stack" << endl;
	cout << "5 Output all elements in the sequential stack" << endl;
	cout << "6 Exit" << endl;
	while (1) {
		int choice;
		cout << "Menu selection:";
		cin >> choice;
		getchar();
		switch (choice) {
			case 1: Stack_Push(S); break;
			case 2: Stack_Pop(S); break;
			case 3: Stack_Top(S); break;
			case 4: Stack_Size(S); break;
			case 5: Stack_PrintStack(S); break;
			case 6: break;
			default: cout << "Input error, please re-enter";
		}
		if (choice == 6)
			exit(0);
		cout << "Press Enter to continue…" << endl;
		getchar();
	};
	return 0;
}

Linked Stack#

Definition of Linked Stack Node#

template <class T> class SNode {
private:
	SNode* next;  // Pointer
	T Data;		  // Data
public:
	friend class Stack<T>;
	SNode() { next = nullptr; }	 // Empty node
	SNode(T data) {				 // Node with data
		Data = data;
		next = nullptr;
	}
	void showdata() { cout << Data << endl; }  // Display the data of this node
};

Definition of Linked Stack Operation Class#

template <class T> class Stack {
private:
	int maxsize;  // Stack capacity
	SNode<T>* head;	 // Head pointer with an empty head node, so the top element is always head->next
public:
	Stack(int size = 100);	// Constructor to allocate space, empty head node
	~Stack();				// Destructor to reclaim space
	void PrintStack();		// Display all elements in the stack
	void Clear();			// Clear all elements in the stack
	void Push(T data);		// Push operation to store element data at the top of the stack
	T Pop();		 // Pop operation to pop the top element and delete it from the stack
	T Top();		 // Get the top element, do not pop
	int Size();		 // Get the number of elements in the stack
	bool IsEmpty();	 // Check if the stack is empty
	bool IsFull();	 // Check if the stack is full
};

Main Operations#

(1) Constructor and Destructor#

// Constructor to allocate space, empty head node
template <class T> Stack<T>::Stack(int size) : maxsize(size) {
	head = new SNode<T>;
	head->next = nullptr;
};

// Destructor to release space
template <class T> Stack<T>::~Stack() {
	while (head->next) {
		Pop();
	}
	if (head)
		delete head;
}

(2) Check if the Stack is Empty or Full#

template <class T> bool Stack<T>::IsEmpty() {
	if (head->next) return false;
	else return true;
}
template <class T> bool Stack<T>::IsFull() {
	if (Size() < maxsize) return false;
	else return true;
}

(3) Push Operation#

Store element data at the top of the stack

template <class T> void Stack<T>::Push(T data) {
	if (IsFull()) {
		cout << "error: Failed to Push, The Stack is Full!" << endl;
	} else {
		SNode<T>* p = new SNode<T>;
		p->Data = data;
		p->next = head->next;
		head->next = p;
	}
}

(4) Get Top Element#

template <class T> T Stack<T>::Top() {
	if (IsEmpty()) {
		cout << "error: The Top isn't existed, The Stack is Empty!" << endl;
		return error;
	} else {
		T temp = head->next->Data;
		return temp;
	}
}

(5) Get Number of Elements in the Stack#

template <class T> int Stack<T>::Size() {
	int cnt = 0;
	SNode<T>* p = head;
	while (p->next) {
		cnt++;
		p = p->next;
	}
	return cnt;
}

(6) Pop Operation#

Pop the top element and delete it from the stack

template <class T> T Stack<T>::Pop() {
	if (IsEmpty()) {
		cout << "error: Failed to Pop, The Stack is Empty!" << endl;
		return error;
	} else {
		SNode<T>* temp = head->next;
		T TopData = temp->Data;
		head->next = temp->next;
		delete temp;
		return TopData;
	}
}

(7) Display All Elements in the Stack#

template <class T> void Stack<T>::PrintStack() {
	if (IsEmpty())
		cout << "This Stack is empty!" << endl;
	SNode<T>* p = head;
	int cnt = 0;
	while (p->next) {
		++cnt;
		p = p->next;
		cout << "The " << cnt << "th Data is:";
		cout << p->Data << endl;
	}
	cout << "The Stack has " << Size() << " elements in total." << endl;
}

(8) Clear All Elements in the Stack#

// (8) Clear all elements in the stack
template <class T> void Stack<T>::Clear() {
	while (head->next) {
		Pop();
	}
}

Complete Code#

// Linked Stack
#include <bits/stdc++.h>
#define error -1
using namespace std;
template <class T> class Stack;
// Definition of linked stack node
template <class T> class SNode {
private:
	SNode* next;  // Pointer
	T Data;		  // Data
public:
	friend class Stack<T>;
	SNode() { next = nullptr; }	 // Empty node
	SNode(T data) {				 // Node with data
		Data = data;
		next = nullptr;
	}
	void showdata() { cout << Data << endl; }  // Display the data of this node
};
// Definition of linked stack operation class
template <class T> class Stack {
private:
	int maxsize;  // Stack capacity
	SNode<T>* head;	 // Head pointer with an empty head node, so the top element is always head->next
public:
	Stack(int size = 100);	// Constructor to allocate space, empty head node
	~Stack();				// Destructor to reclaim space
	void PrintStack();		// Display all elements in the stack
	void Clear();			// Clear all elements in the stack
	void Push(T data);		// Push operation to store element data at the top of the stack
	T Pop();		 // Pop operation to pop the top element and delete it from the stack
	T Top();		 // Get the top element, do not pop
	int Size();		 // Get the number of elements in the stack
	bool IsEmpty();	 // Check if the stack is empty
	bool IsFull();	 // Check if the stack is full
};

// Implementation of linked stack operation class
// Constructor to allocate space, empty head node
template <class T> Stack<T>::Stack(int size) : maxsize(size) {
	head = new SNode<T>;
	head->next = nullptr;
};

// Destructor to release space
template <class T> Stack<T>::~Stack() {
	while (head->next) {
		Pop();
	}
	if (head)
		delete head;
}
// (1) Check if the stack is empty
template <class T> bool Stack<T>::IsEmpty() {
	if (head->next)
		return false;
	else
		return true;
}
// (2) Check if the stack is full
template <class T> bool Stack<T>::IsFull() {
	if (Size() < maxsize)
		return false;
	else
		return true;
}
// (3) Push operation
// Store element data at the top of the stack
template <class T> void Stack<T>::Push(T data) {
	if (IsFull()) {
		cout << "error: Failed to Push, The Stack is Full!" << endl;
	}
	else {
		SNode<T>* p = new SNode<T>;
		p->Data = data;
		p->next = head->next;
		head->next = p;
	}
}
// (4) Get top element, do not pop
template <class T> T Stack<T>::Top() {
	if (IsEmpty()) {
		cout << "error: The Top isn't existed, The Stack is Empty!" << endl;
		return error;
	}
	else {
		T temp = head->next->Data;
		return temp;
	}
}
// (5) Get number of elements in the stack
template <class T> int Stack<T>::Size() {
	int cnt = 0;
	SNode<T>* p = head;
	while (p->next) {
		cnt++;
		p = p->next;
	}
	return cnt;
}
// (6) Pop operation
// Pop the top element and delete it from the stack
template <class T> T Stack<T>::Pop() {
	if (IsEmpty()) {
		cout << "error: Failed to Pop, The Stack is Empty!" << endl;
		return error;
	}
	else {
		SNode<T>* temp = head->next;
		T TopData = temp->Data;
		head->next = temp->next;
		delete temp;
		return TopData;
	}
}
// (7) Display all elements in the stack
template <class T> void Stack<T>::PrintStack() {
	if (IsEmpty())
		cout << "This Stack is empty!" << endl;
	SNode<T>* p = head;
	int cnt = 0;
	while (p->next) {
		++cnt;
		p = p->next;
		cout << "The " << cnt << "th Data is:";
		cout << p->Data << endl;
	}
	cout << "The Stack has " << Size() << " elements in total." << endl;
}
// (8) Clear all elements in the stack
template <class T> void Stack<T>::Clear() {
	while (head->next) {
		Pop();
	}
}
// Functions called in the main function (for testing)
template <class T> void Stack_Push(Stack<T>& S) {
	T data;
	cout << "Please enter the element to push onto the stack:";
	cin >> data;
	getchar();
	S.Push(data);
	cout << "------------- After Push, Stack S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Pop(Stack<T>& S) {
	T data = S.Pop();
	if (data != error) {
		cout << "The popped element is:";
		cout << data << endl;
	}
	cout << "------------- After Pop, Stack S ---------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_Top(Stack<T>& S) {
	T data = S.Top();
	if (data != error) {
		cout << "The top element is:";
		cout << data << endl;
	}
}
template <class T> void Stack_Size(Stack<T>& S) {
	cout << "The number of elements in this stack is:" << S.Size() << endl;
}
template <class T> void Stack_PrintStack(Stack<T>& S) {
	cout << "---------------------- Stack S --------------------" << endl;
	S.PrintStack();
}
template <class T> void Stack_ClearStack(Stack<T>& S) {
	S.Clear();
	cout << "Successfully cleared!" << endl;
}
int main() {
	int n;
	cout << "Enter n, to create a linked stack of length n:";
	cin >> n;
	Stack<int> S(n);
	cout << "Enter n elements:" << endl;
	for (int i = 0; i < n; ++i) {
		int data;
		cin >> data;
		S.Push(data);
	}
	cout << "1 Push operation" << endl;
	cout << "2 Pop operation" << endl;
	cout << "3 Get top element" << endl;
	cout << "4 Get number of elements in the stack" << endl;
	cout << "5 Output all elements in the stack" << endl;
	cout << "6 Clear all elements in the stack" << endl;
	cout << "7 Exit" << endl;
	while (1) {
		int choice;
		cout << "Menu selection:";
		cin >> choice;
		getchar();
		switch (choice) {
			case 1: Stack_Push(S); break;
			case 2: Stack_Pop(S); break;
			case 3: Stack_Top(S); break;
			case 4: Stack_Size(S); break;
			case 5: Stack_PrintStack(S); break;
			case 6: Stack_ClearStack(S); break;
			case 7: break;
			default: cout << "Input error, please re-enter";
		}
		if (choice == 7)
			exit(0);
		cout << "Press Enter to continue…" << endl;
		getchar();
	};
	return 0;
}