STACKS: a genesis of data structure

stacks come under linear data structure.They follow LIFO operations.Now lifo operations simply refer that any data elements entered form a sequence and the deletion and insertion can only occur at the top.In a more sophisticated way insertion is called push, and deletion as pop.Now lets directly shift to some example.

stacks can be implemented statically and dynamically:

static implementation refers the use of array’s:

#include<stdio.h>
#define MAX 5
int top = -1;
int stack_arr[MAX];

/*Begin of push*/
void push()
{
int pushed_item;
if(top == (MAX-1))
printf(“Stack Overflow\n”);
else
{
printf(“Enter the item to be pushed in stack : “);
scanf(“%d”,&pushed_item);
top=top+1;
stack_arr[top] = pushed_item;
}
}
/*End of push*/

/*Begin of pop*/
void pop()
{
if(top == -1)
printf(“Stack Underflow\n”);
else
{
printf(“Popped element is : %d\n”,stack_arr[top]);
top=top-1;
}
}
/*End of pop*/

/*Begin of display*/
void display()
{
int i;
if(top == -1)
printf(“Stack is empty\n”);
else
{
printf(“Stack elements :\n”);
for(i = top; i >=0; i — )
printf(“%d\n”, stack_arr[i] );
}
}
/*End of display*/

/*Begin of main*/
main()
{
int choice;

do{
printf(“1.Push\n”);
printf(“2.Pop\n”);
printf(“3.Display\n”);
printf(“4.Quit\n”);
printf(“Enter your choice : “);
scanf(“%d”,&choice);
switch(choice)
{
case 1 :
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
break;
default:
printf(“Wrong choice\n”);
}}while(choice!=4);
}
/*End of main*/

Dynamically stacks are implemented using link list:

#include <bits/stdc++.h>
using namespace std;

// Declare linked list node

struct Node {
int data;
struct Node* link;
};
struct Node* top;

// Utility function to add an element data in the stack
// insert at the beginning
void push(int data)
{
// create new node temp and allocate memory
struct Node* temp;
temp = new Node();

// check if stack (heap) is full. Then inserting an element would
// lead to stack overflow
if (!temp) {
cout << “\nHeap Overflow”;
exit(1);
}

// initialize data into temp data field
temp->data = data;

// put top pointer reference into temp link
temp->link = top;

// make temp as top of Stack
top = temp;
}

// Utility function to check if the stack is empty or not
int isEmpty()
{
return top == NULL;
}

// Utility function to return top element in a stack
int peek()
{
// check for empty stack
if (!isEmpty())
return top->data;
else
exit(1);
}

// Utility function to pop top
// element from the stack

void pop()
{
struct Node* temp;

// check for stack underflow
if (top == NULL) {
cout << “\nStack Underflow” << endl;
exit(1);
}
else {
// top assign into temp
temp = top;

// assign second node to top
top = top->link;

// destroy connection between first and second
temp->link = NULL;

// release memory of top node
free(temp);
}
}

// Function to print all the
// elements of the stack
void display()
{
struct Node* temp;

// check for stack underflow
if (top == NULL) {
cout << “\nStack Underflow”;
exit(1);
}
else {
temp = top;
while (temp != NULL) {

// print node data
cout << temp->data << “ “;

// assign temp link to temp
temp = temp->link;
}
}
}

// Driver Code
int main()
{
// push the elements of stack
push(11);
push(22);
push(33);
push(44);

// display stack elements
display();

// print top elementof stack
cout << “\nTop element is %d\n” << peek();

// delete top elements of stack
pop();
pop();

// display stack elements
display();

// print top elementof stack
cout << “\nTop element is %d\n” << peek();
return 0;
}