How to: Implement Operations on Stack and Queue Data Structures in C++

2 comments - This post in romanian

Stack is a logical data structure, its implementation in physical memory being made by using other data structures.
The components of the stack data structure have the same data type, which means that the stack is a homogeneous data structure.
There are two basic operations with stack: adding and removal of an item.
Manner of implementation for operations is given by the discipline of access: LIFO – Last In First Out.
All adds (push) and extractions (pop) are achieved at the same end of the implementation structure, called the stack top.

In the below example, implementations of push and pop operations are presented, using as implemention structure the simply linked list [...]. The each element structure of the stack is formed by a value of type int and the address of next element of the stack.

struct Nod{
	int val;
	Nod* next;
};
 
Nod* push(Nod* vf, int v){
	Nod* nou=new Nod;
	nou->val=v;
	nou->next=vf;
	return nou;
}
 
Nod* pop(Nod* vf, int *v){
	if(vf){
		*v=vf->val;
		Nod* t=vf;
		vf=vf->next;
		delete t;
		return vf;
	}
	return vf;
}

Queue keeps the characteristics of the stack structure, less the issues regarding the implemention of the insertion and extraction operations. Thus, the implementation way of the operations is given by access discipline: FIFO – First In First Out. All adds (put) are made at one end of the structure of physical implementation, and extractions from the queue (get) are achieved at the other end of the structure.
In the below example, implementations of operations put and get are presented, using as support structure the simply linked list [...]. The each element structure of the queue is formed from a value of type int and address of the successor node from queue structure.

struct Nod{
	int val;
	Nod* next;
};
 
Nod* put(Nod* c,int v){
	Nod* nou=new Nod;
	nou->val=v;
	nou->next=NULL;
	if(!c)
		return nou;
	else{
		Nod* t=c;
		while(t->next)
			t=t->next;
		t->next=nou;
		return c;
	}
}
 
Nod* get(Nod* c,int *v){
	if(c){
		*v=c->val;
		Nod* t=c;
		c=c->next;
		delete t;
		return c;
	}
	return c;
}

, , , ,