PROWAREtech

C/C++: Stack Data Structure

A stack is important because of its LIFO (Last In, First Out) behavior. This is useful for syntax parsing and evaluating expressions. Some high-level programming languages with recursive functions use stacks like this. The stack has many uses just remember that it has a LIFO behavior.

A queue has the opposite behavior (FIFO) and is used in combination with stacks to solve problems.

This stack is written mostly in C with a little C++ to make the code more readable. A C++ example follows.

#include <iostream>
#include <string>
using namespace std;

class Node
{
private:
	Node() {}
public:
	int data;
	Node *pnext;
	Node(const int dataToStack, Node *pstack)
	{
		pnext = pstack;
		data = dataToStack;
	}
};

Node *pstack = 0;

void Push(const int data)
{
	pstack = new Node(data, pstack);
}

void Pop()
{
	if (pstack)
	{
		Node *p = pstack;
		pstack = pstack->pnext;
		p->pnext = 0;
		delete p;
	}
}

int main()
{
	int n;
	for (int i = 0; i < 20; i++)
	{
		n = i;
		cout << n << endl;
		Push(n);
	}
	cout << endl;
	while (pstack)
	{
		n = pstack->data;
		Pop();
		cout << n << endl;
	}
	return 0;
}

Now a stack written in C++ using templates.

#include <iostream>
#include <string>
using namespace std;

template <class TData> class Node
{
private:
	Node() {}
public:
	TData data;
	Node<TData> *pnext;
	Node(const TData &dataToStack, Node<TData> *pstack);
};

template <class TData> class Stack
{
private:
	Node<TData> *pstack;
	void Copy(Node<TData> *pnext);

public:
	Stack();
	Stack(const Stack<TData> &obj);
	~Stack();
	const Stack<TData> &operator=(const Stack<TData> &obj);
	bool IsEmpty() const;
	void Push(const TData &data);
	bool Pop(TData &output);
	void Clear();
};

template <class TData> Node<TData>::Node(const TData &dataToStack, Node<TData> *pstack)
{
	pnext = pstack;
	data = dataToStack;
}

template <class TData> Stack<TData>::Stack(const Stack<TData> &obj)
{
	pstack = nullptr;
	this->operator=(obj);
}

template <class TData> const Stack<TData> &Stack<TData>::operator=(const Stack<TData> &obj)
{
	if (this != &obj)
	{
		Clear();
		Copy(obj.pstack);
	}
	return (*this);
}

template <class TData> void Stack<TData>::Copy(Node<TData> *pnext)
{
	if (pnext)
	{
		Copy(pnext->pnext);
		pstack = new Node<TData>(pnext->data, pstack);
	}
}

template <class TData> bool Stack<TData>::IsEmpty() const
{
	return(pstack == nullptr);
}

template <class TData> void Stack<TData>::Push(const TData &data)
{
	pstack = new Node<TData>(data, pstack);
}

template <class TData> bool Stack<TData>::Pop(TData &output)
{
	if (pstack)
	{
		output = pstack->data;
		Node<TData> *p = pstack;
		pstack = pstack->pnext;
		p->pnext = nullptr;
		delete p;
		return true;
	}
	return false;
}

template <class TData> void Stack<TData>::Clear()
{
	while (pstack)
	{
		Node<TData> *p = pstack;
		pstack = pstack->pnext;
		p->pnext = nullptr;
		delete p;
	}
}

template <class TData> Stack<TData>::Stack()
{
	pstack = nullptr;
}

template <class TData> Stack<TData>::~Stack()
{
	Clear();
}

int main()
{
	{
		Stack<int> st;
		int n;
		for (int i = 0; i < 20; i++)
		{
			n = i;
			cout << n << endl;
			st.Push(n);
		}
		cout << endl;
		do
		{
			int data;
			if (st.Pop(data))
				cout << data << endl;
		} while (!st.IsEmpty());
	}
	cout << endl;
	{
		Stack<string> st;
		string s;
		for (int i = 0; i < 26; i++)
		{
			char c[4] = { 0,0,0,0 };
			c[0] = c[1] = c[2] = ((i % 26) + 97);
			s = c;
			cout << s << endl;
			st.Push(s);
		}
		cout << endl;
		do
		{
			string data;
			if (st.Pop(data))
				cout << data << endl;
		} while (!st.IsEmpty());
	}
	return 0;
}

Comment