Stack

Stack is a linear data structure which follows a particular order in which the operations are performed. Order is LIFO(Last In First Out) or FILO(First In Last Out)

Three main operations of a stack are :

1. Push
2. Pop
3. Peek or Top

Stack

Push

The Push Operation pushes an element into the stack.

Pop

Pop operation removes the top most element in the stack.

Peek

Peek or top operation returns the top most value of the stack.

To understand stack, you can assume a pile of books placed one over the other.To get the last book in the stack, one needs to take away all the books before the last book.

Applications of Stack

1. Recursion
2. Tower of Hanoi
3. Converting Infix to Postfix.

Stack can be implemented in two different ways: 

1. Stack Implementation using Arrays 
2. Stack Implementation using Linked list

The implemented codes are carried out into separate blogs in the above given links.

More stack related blogs

Stack Implementation Using Linked list

Implementation of a stack using linked list is dynamic and flexible. Yet the space consumed is high and adding or manipulating the linked list is complex.
Refer to the code for more details. The Code language is C++.

Code:

//Implementation of a stack using a Singly Linked List #include<iostream> using namespace std; class stack{ public: struct Node{ int data; struct Node* Link; }; struct Node* top=NULL;//initially my stack is empty void push(){ int x; struct Node* temp=new Node(); cout<<"\nEnter the data: "; cin>>x; temp->data=x; temp->Link=top; top=temp; } void pop(){ if(top==NULL){ cout<<"\nStack underflow"<<endl; }else{ top=top->Link; } } //function to peek into the stack void peek(){ cout<<"\nPeeping into the stack:"<<endl; cout<<top->data; } //function to check if the stack is empty void isEmpty(){ if(top==NULL){ cout<<"\nThe Stack is empty"<<endl; }else{ cout<<"\nThe stack is not empty"<<endl; } } //function to print the elements of the stack void print(){ Node* temp=new Node(); temp=top; cout<<"Printing Elements in a stack"<<endl; while(temp!=NULL){ cout<<temp->data<<endl; temp=temp->Link; } } void sizeofstack(){ Node* temp=new Node(); temp=top; int sizeoftemp; while(temp!=NULL){ temp=temp->Link; sizeoftemp+=sizeof(temp); } cout<<"\nSize of the stack"<<sizeoftemp<<endl; } //function to choose the stack operations void option(){ int x=1; int options; while(x!=0){ cout<<"\nStack operations:"<<endl; cout<<"1.Push"<<endl; cout<<"2.Pop"<<endl; cout<<"3.Peek"<<endl; cout<<"4.Is Empty?"<<endl; cout<<"5.Print Stack"<<endl; cout<<"6.Stack Size"<<endl; cout<<"7.Exit"<<endl; cout<<"Enter option"<<endl; cin>>options; switch(options){ case 1: push(); break; case 2: pop(); break; case 3: peek(); break; case 4: isEmpty(); break; case 5: print(); break; case 6: sizeofstack(); break; case 7: exit(0); break; } } } }; int main(){ stack k; k.option(); }

Output:

Stack Implementation Using Array

This blog will deal with implementation of stack using arrays.The implementation is simple yet we need to allocate a pre-defined size.The allocated size may or may not be utilized completely. This makes the array implementation non-flexible.

Using Array

#include<stdio.h> #include<stdlib.h> #define MAX_SIZE 101 int A[MAX_SIZE]; int top=-1; void Push(int x){ if(top==MAX_SIZE-1){ printf("Error;stack overflow\n"); } A[++top]=x; } void pop(){ if(top==MAX_SIZE-1){ printf("Error: No element to pop\n"); } top--; } int Top(){ return A[top]; } void print(){ int i; printf("Stack :"); for(i=0;i<=top;i++){ printf("\n%d",A[i]); } printf("\n"); } int main(){ Push(2); print(); Push(10); print(); pop(); Top(); Push(7); print(); pop(); }



Output

---