What are Stacks ? - data structure tutorial

Today we will be discussing about What are Stacks ? - data structure tutorial.
Stack is a linear data structure in which elements are inserted in LIFO(last in first out) manner. A real life examples of stacks is pile of plates. The plate which was inserted first will be removed last and the plate which was placed at the top will be removed first.

Basic operations performed on a  stack

1. Push() :  This function is used to push/insert elements into the stack.
2. Pop() : This function is used to pop/delete an element from stack.
3. Top() : This function returns the top-most element of the stack.

• When a stack is filled completely then it is known as stack overflow. When a stack is completely empty then it is known as stack underflow (What are Stacks in Data Structure?).
• Stacks allow its operations to be performed only at one end. For example, you can only insert a plate at the top of pile of plates or you can only remove a plate from top of pile of plates.

Implementation of Stack operations

1. Insertion is performed using push() function. Initially, the stack is empty and top is set '-1'. 
2. When an element is inserted into the stack then top is incremented and then the element is inserted at the location top is pointing to.
3. This process continues until value of top exceeds the size of array.

1. Deletion is performed using pop() function. 
2. When an element is to be deleted then we first print the element which is to be deleted if we want to print the element which is deleted. Otherwise, just decrement value of top.
3. This process continues until top becomes less than 0 which denotes that the stack is now empty.

• Note : When top is decremented then the value is not actually removed from the array but we just consider that the value lies outside the range of top and thus it is removed(What are Stacks in Data Structure?) .

Code for implementing Stack

Your Text Here. #include<iostream> using namespace std; class stack { private: //array in which data is stored int arr[10]; //size of array int size; //represents the location of top-most/last element pushed in array int top; public: // constructor to initialize size and top. top is set -1 initially because initially the array is empty. stack(int s) { size=s; top=-1; } // this function pushes the element into the array void push(int data) { // if top exceeds size of array then it is stack overflow and we terminate. if(top>=size) { cout<<"stack overflow!!"; return; } // else enter data into array at top-most location. else { cout<<data<<" pushed in stack"<<endl; //top is pre-incremented so that it can first update top and then assign value to that location. arr[++top]=data; } } int pop() { //if all elements are popped out of stack then top will become -1 and then its stack underflow and we terminate if(top<0) { cout<<"stack underflow!!"; return 0; } //else we return top most element which is popped. Notice we have used post-increment. return arr[top--]; } }; int main() { int size; int x; cout<<"enter size: "; cin>>size; stack s1(size); s1.push(1); s1.push(3); s1.push(5); s1.push(7); x=s1.pop(); cout<<x<<" popped"<<endl; x=s1.pop(); cout<<x<<" popped"<<endl; x=s1.pop(); cout<<x<<" popped"<<endl; x=s1.pop(); cout<<x<<" popped"<<endl; return 0; }

If you have understood the concept of stacks then try out these problems:

1. WAP to convert infix expression to postfix.
2. WAP to convert postfix expression to infix.
3. WAP to solve The Stock Span Problem.
4. Given an array, print the next Greater Element for every element. The Next greater element for an element x is the first greater element on the right side of x in array. Element for which no greater element exist ,consider next greater element an -1.   

          Example : For any array, the rightmost element always has next greater element as -1.
                            For an array which is sorted in decreasing order, all elements have next element                                   as -1.
                           For the input array[4,5,2,25], the next greater elements for each element are as                                     follows:

Element       NGE

   4      -->   5

   5      -->   25

   2      -->   25

   25     -->   -1

2.        

So this was all about What are Stacks ? - data structure tutorial.