C++ Linked List Stack Tutorial

[101MUDman101]

Hello all, this snippet is one you will not probably use (Well you might ) because it is essentially showing off the usage of linked lists. This is actually a good way to make a stack as it does not have any limit to how much data it can contain (Abiding Memory Limits).

To start off, lets see the code:

Code: Select all

struct node {
	int data;
	node *link;
};

class lstack {
private:
	node* top;
public:
	lstack() {
		top = NULL;
	}

	void push(int n) {
		node *tmp;
		tmp = new node;
		if (tmp == NULL)
			cout << "\nStack Full.";

		tmp->data = n;
		tmp->link = top;
		top = tmp;
	}

	int pop() {
		if (top == NULL) {
			cout << "\nStack Empty.";
			return NULL;
		}
		node *tmp;
		int n;
		tmp = top;
		n = tmp->data;
		top = top->link;
		delete tmp;
		return n;
	}

	~lstack() {
		if (top == NULL)
			return;

		node *tmp;
		while (top != NULL) {
			tmp = top;
			top = top->link;
			delete tmp;
		}
	}
};

Now lets look at the code I bit more indepth:

Code: Select all

struct node {
	int data;
	node *link;
};

The 'node' class is really just the variable you enter, it has some data and has a 'link', this link is what makes our list linked, everytime we push a variable onto the stack we link the node to the top of the stack so it will be pushed to the top.

Now for the constructor:

Code: Select all

lstack() {
	top = NULL;
}

We are really just setting the top of the stack to nothing as the stack is empty at this current point.

Lets get onto the main chunk of code:

Code: Select all

void push(int n) {
	node *tmp;
	tmp = new node;
	if (tmp == NULL)
		cout << "\nStack Full.";

	tmp->data = n;
	tmp->link = top;
	top = tmp;
}

What we are doing is using the node struct we made earlier to make a temporary holder for the data, we first check to see if the stack is full, we then assign its data to the variable 'n' and then finally we link it to the top of the stack and assign to the top.

Now we wil move onto the 'pop' function:

Code: Select all

int pop() {
	if (top == NULL) {
		cout << "\nStack Empty.";
		return NULL;
	}
	node *tmp;
	int n;
	tmp = top;
	n = tmp->data;
	top = top->link;
	delete tmp;
	return n;
}

So the return type for this function is 'int' as we are returning the value at the top of the stack. First off we check to see if the stack is empty by seeing if 'top' equals NULL. If you notice the next bit is the opposite of the push function. Instead of assigning our node 'tmp' to our variables value, we are assigning our variable to the value of 'tmp' We then delete tmp and return our number.

Now for the final part of the class, the decontructor:

Code: Select all

~lstack() {
	if (top == NULL)
		return;

	node *tmp;
	while (top != NULL) {
		tmp = top;
		top = top->link;
		delete tmp;
	}
}

So first off, we check if the stack is empty, if so, we can be sure it is ok to complete the deconstruction as we have no memory to clean up. However if the stack contains values then we must clear the values and unlink everything. To do this, we once again create our node 'tmp' and while the stack is not empty we assign the top of the stack to 'tmp' and then delete it. Doing this until the stack is empty will make sure everything is cleaned up well.

To end it lets see the class in action:

Code: Select all

int main() {
    lstack s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.pop() << endl;
    cout << s.pop() << endl;
    cout << s.pop() << endl;
    system("PAUSE"); //cin.get()
}

Output:
3
2
1

So thats all for this tutorial, keep in mind, you can edit the code to use any data type you want.

Hope this helps!