Stack

Stacks are linear data structures. This means that their contexts are stored in what looks like a line (although vertically). This linear property, however, is not sufficient to discriminate a stack from other linear data structures. For example, an array is a sort of linear data structure in which you can access any element directly. In contrast, in a stack, you can only access the element at its top. In a stack Last thing In is the First thing Out. Thus, we say that a stack enforces LIFO order.

One disadvantage of implementing stack using an array is wastage of space. Most of the times most of the array is left unused. A better way to implement stack is by using a linked list. By using a single linked list to implement a stack there is no wastage of space.

Implementation of stack using a linked list

/*
A simple implementation of linked list in C plus plus (CPP/C++)
*/
/*
Compiler used: g++
*/
#include<iostream>
using namespace std;
struct node{
	int data;
	node *next;
	};
//This function pushes data(node) to the stack
node * push(node*,node*);
//This function pops data (node) and returns pointer to the poped node
node * pop(node*);
//This function shows the stack
void show_stack(node*);
///These two global variables will help us track the start and end of the list
node *f,*l;
main()
{
	int i,ch;
	f=l=NULL;
	cout<<"\t 1 to push"<<endl;
	cout<<"\t 2 to pop"<<endl;
	cout<<"\t 3 to show stack"<<endl;
	cout<<"\t 0 to exit"<<endl;
	while(1)
	{
		cout<<"Enter your choice:";
		cin>>ch;
		switch(ch)
		{
		case 1:
			{
			if(f==NULL)
			l=f=push(f,l);
			else
			l=push(f,l);
			break;
			}
		case 2:
			{
			cout<<"popped:"<<pop(f)->data<<endl;
			break;
			}

		case 3:
			{
			show_stack(f);
			break;
			}
		case 0:
			break;
		default:
			cout<<"Please enter a proper choice"<<endl;break;
		}
		if(ch==0)
		break;
	}
}
node * push(node *f,node *l)
{
	node *n;
	n=new node;
	cout<<"Enter data:";
	cin>>n->data;
	n->next=NULL;
	if(f==NULL)
	{f=l=n;return f;}
	else
	{
		l->next=n;
		l=n;return l;
	}

}
void show_stack(node *f)
{
	cout<<"showing data"<<endl;
	node *guest=f;
	while(guest!=NULL)
	{
		cout<<"\t"<<guest->data<<endl;
		guest=guest->next;
	}
}
node * pop(node *f)
{
	node *guest,*lb;
	guest=lb=f;
	while(guest->next!=NULL)
	{
		lb=guest;
		guest=guest->next;
	}
	lb->next=NULL;
	l=lb;
	return guest;
}
		
Download the program: Implementation of stack using a single linked list