ADT - Abstract Data Type

Stack works on LIFO i.e Last-in First-out principle.
Stack is a collection of elements and these elements are inserted and deleted by following LIFO principle.

Recursion makes use of stacks.
Every recursive function can be converted to an iterative procedure and we might have to use a stack to do so.

It contains data representations and operations.

Data :

Space for storing elements
Top pointer : A pointer which points at the topmost element in a stack.

Operations :

push(x)
pop()
peek(index) : let's you take a peek at the value at some index
stackTop() : Let's you know the topmost value in the stack
isEmpty()
isFull()

Pasted image 20240104163937.png
Pasted image 20240104163947.png

Stack can be implemented using arrays and Linked List
We usually imagine stack to be staged vertically.

Stack Using Array :

We need a fixed size array, it's size and a top pointer on the recently inserted index.
Insertion and deletion is done from the right side of the array :

This helps in reducing the time complexity to O(1) i.e. constant. Otherwise we'd have to shift all the elements if decided to insert from the left side.

Conditions :

Pasted image 20240104172207.png

Operations :

1. Push :

Pasted image 20240104172608.png

2. Deletion :

Pasted image 20240104173201.png

3. Peek :

Pasted image 20240104180218.png

4. stackTop, isEmpty, isFull :

Pasted image 20240104180433.png

Final Code : Stack Using Array

#include<iostream>
using namespace std;

struct Stack
{
    int size; // size of the array
    int top;
    int *s; // pointer to the dynamically created array // we are dynamically creating an array as we do not know the size requirements of the array.
};

void create ( Stack *st)
{
    // scanf("%d ", &st->size); // to take an input for the size of the array
    st->size = 10; // CHANGE ACCORDINGLY
    st->top = -1; // as there is no element inserted yet
    st->s = new int[st->size];
}

void Display(Stack st)
{
    int i;
    for (i=st.top;i>=0;i--)
    {
        printf("%d ", st.s[i]);
    }
    printf("\n");
}

void push(Stack *st, int x)
{
    if(st->top == st->size-1)
        printf("Stack Overflow\n");
    else
    {
        st->top++;
        st->s[st->top] = x;
    }
}

int pop(Stack *st)
{
    int x = -1;
    if(st->top == -1)
        printf("Stack Underflow\n");
    else
    {
        x = st->s[st->top--];
    }
    return x;
}

int peek(Stack st, int index)
{
    int x = -1;
    if(st.top-index+1<0)
        printf("Invalid Index");
    x=st.s[st.top - index +1];
    return x;
}

int isEmpty(Stack st)
{
    if(st.top == -1)
        return 1;
    return 0;
}

int isFull(Stack st)
{
    return (st.top == st.size-1); // will return 0 or 1
}

int stackTop(Stack st)
{
    if(!isEmpty(st))
        return st.s[st.top];
    return -1;
}

int main()
{

    Stack st;
    create(&st);

    push(&st, 10);
    push(&st, 20);
    push(&st, 30);

    Display(st); // → 30 20 10 

    cout << pop(&st); // → 30

    peek(st, 1); // → 30
    cout << isEmpty(st); // → 0
    cout << isFull(st); // → 0
    cout << stackTop(st); // → 20 (as 30 was previously popped)

    return 0;
}

Stack using Linked List :

Pasted image 20240105114703.png

Elements are inserted through left side. i.e first element pushed will be placed at the last index, 2nd element will be at last 2nd index and last element will be at 0th index.

Push :

Pasted image 20240105114859.png

Create a new node to push an element in the stack.
NOTE : Here we can push unlimited elements as it is a linked list, so the stack will only be full when heap is full and we are not allowed to create new nodes

Push Code :

Pasted image 20240105121247.png

Pop Code :

Pasted image 20240105121429.png

Peek Code :

Pasted image 20240105123819.png

stackTop, isEmpty, isFull :

Pasted image 20240105124302.png

Final Code : Stack Using Linked List

inverted LL banayenge and next node me previous node ka address store karenge.

In C lang :

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *next;
}*top = NULL;

void push(int x)
{
    Node *t;
    t = new Node;

    if (t == NULL)
        printf("stack is full\n");
    else
    {
        t->data = x;
        t->next = top;
        top = t;
    }
}

int pop()
{
    Node *t;
    int x = -1;

    if (top == NULL)
        printf("Stack is empty\n");
    else
    {
        t = top;
        top = top->next;
        x = t->data;
        free(t);
    }
    return x;
}

void Display()
{
    Node *p;
    p = top;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
}

int main()
{

    push(10);
    push(20);
    push(30);

    Display(); // → 30 20 10

    cout << pop(); // → 30

    return 0;
}

In C++ : Using Classes

#include<iostream>
using namespace std;

class Node
{
public:
    int data;
    Node *next;
};

class Stack
{
private:
    Node *top;
public:
    //constructor
    Stack(){top=NULL;}
    void push(int x);
    int pop();
    void Display();
};

void Stack::push(int x)
{
    Node *t = new Node;
    if(t==NULL)
        cout << "Stack is Full";
    else
    {
        t->data=x;
        t->next=top;
        top=t;
    }
}

int Stack::pop()
{
    int x= -1;
    if(top==NULL)
        cout << "Stack is Empty\n";
    else
    {
        x=top->data;
        Node *t = top;
        top = top->next;
        delete t;
    }
    return x;
}

void Stack::Display()
{
    Node *p = top;
    while(p!=NULL)
    {
        cout << p->data << " ";
        p=p->next;
    }
    cout << endl;
}

int main()
{
    Stack stk;
    stk.push(10);
    stk.push(20);
    stk.push(30);

    stk.Display();
    cout << stk.pop(); // → 30

    return 0;
}

Parenthesis Matching :

Pasted image 20240114232321.png

Push ( on its encounter and Pop the ) on its encounter.

Code :

#include <iostream>
using namespace std;

struct Node
{
    char data;
    Node *next;
} *top = NULL;

void push(char x)
{
    Node *t;
    t = new Node;
    if (t == NULL)
        printf("Stack is Full\n");
    else
    {
        t->data = x;
        t->next = top;
        top = t;
    }
}

char pop()
{
    Node *t;
    char x = -1;
    if (top == NULL)
        printf("Stack is Empty\n");
    else
    {
        t = top;
        top = top->next;
        x = t->data;
        delete t;
    }
    return x;
}

void Display()
{
    Node *p;
    p = top;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int isBalanced(char *exp)
{
    for (int i=0; exp[i] != '\0'; i++)
    {
        if(exp[i]=='(')
            push('(');
        else if (exp[i] == ')')
        {
            if (top == NULL)
                return 0;
            pop();
        }
    }
    if (top == NULL)
        return 1;
    else
        return 0;
}

int main()
{
    char *exp = "((a+b)*(c-d)))";
    cout << isBalanced(exp); // → 0
    return 0;
}

Multiple Bracket Type Parenthesis matching :

Pasted image 20240115234106.png

#include <iostream>
#include<cstring>
#include <stack>
#include <map>

using namespace std;
 
int isBalanced(char* exp){
 
    // Create map
    map<char, char> mapping;
    mapping['}'] = '{';
    mapping[')'] = '(';
    mapping[']'] = '[';
 
    // Create map iterator
    map<char, char>::iterator itr;
 
    // Create stack
    stack<char> stk;
 
    for (int i=0; i<strlen(exp); i++){
        if (exp[i] == '{' || exp[i] == '[' || exp[i] == '('){
            stk.push(exp[i]);
        } else if (exp[i] == '}' || exp[i] == ']' || exp[i] == ')'){
            if (stk.empty()){
                return false;
            } else {
                char temp = stk.top();
                itr = mapping.find(exp[i]);
                if (temp == itr->second){  // itr->first is key, itr->second is value
                    stk.pop();
                } else {
                    return false;
                }
            }
        }
    }
    return stk.empty() ? true : false;
}
 
int main() {
 
    char A[] = "{([a+b]*[c-d])/e}";
    cout << isBalanced(A) << endl;
 
    char B[] = "{([a+b]}*[c-d])/e}";
    cout << isBalanced(B) << endl;
 
    char C[] = "{([{a+b]*[c-d])/e}";
    cout << isBalanced(C) << endl;
 
    return 0;
}

Infix to Postfix Conversion :

Pasted image 20240116000105.png

Infix to postfix conversion :

Postfix is used more often as compared to prefix
Precedence :
Priority order 3 > 2 > 1

Pasted image 20240116234639.png
Pasted image 20240116235231.png

Associativity :

Pasted image 20240117000011.png
^ : power, - : unary minus,

Post Fix Forms :

Few examples of Unary Operators :
Unary operators have the highest precedence and have right to left associativity

Method 1 :

Pasted image 20240117005409.png

Method 2 :

https://www.udemy.com/course/datastructurescncpp/learn/lecture/13167944#content
Pasted image 20240117010228.png

Code :

Pasted image 20240117011729.png
Pasted image 20240117011852.png

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
struct Node
{
    char data;
    struct Node *next;
} *top = NULL;
void push(char x)
{
    struct Node *t;
    t = (struct Node *)malloc(sizeof(struct Node));
    if (t == NULL)
        printf("stack is full\n");
    else
    {
        t->data = x;
        t->next = top;
        top = t;
    }
}

char pop()
{
    struct Node *t;
    char x = -1;
    if (top == NULL)
        printf("Stack is Empty\n");
    else
    {
        t = top;
        top = top->next;
        x = t->data;
        free(t);
    }
    return x;
}

void Display()
{
    struct Node *p;
    p = top;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
int isBalanced(char *exp)
{
    int i;
    for (i = 0; exp[i] != '\0'; i++)
    {
        if (exp[i] == '(')
            push(exp[i]);
        else if (exp[i] == ')')
        {
            if (top == NULL)
                return 0;
            pop();
        }
    }
    if (top == NULL)
        return 1;
    else
        return 0;
}
int pre(char x)
{
    if (x == '+' || x == '-')
        return 1;
    else if (x == '*' || x == '/')
        return 2;
    return 0;
}
int isOperand(char x)
{
    if (x == '+' || x == '-' || x == '*' || x == '/')
        return 0;
    else
        return 1;
}
char *InToPost(char *infix)
{
    int i = 0, j = 0;
    char *postfix;
    int len = strlen(infix);
    postfix = (char *)malloc((len + 2) * sizeof(char));
    while (infix[i] != '\0')
    {
        if (isOperand(infix[i]))
            postfix[j++] = infix[i++];
        else
        {
            if (pre(infix[i]) > pre(top->data))
                push(infix[i++]);
            else
            {
                postfix[j++] = pop();
            }
        }
    }
    while (top != NULL)
        postfix[j++] = pop();
    postfix[j] = '\0';
    return postfix;
}
int main()
{
    char *infix = "a+b*c-d/e";
    push('#');
    char *postfix = InToPost(infix);
    printf("%s ", postfix); // → abc*+de/-#
    return 0;
}

Infix to Postfix with Associativity and Parenthesis

Pasted image 20240118012615.png

Evaluation of Postfix :

Pasted image 20240118013741.png

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
struct Node
{
    int data;
    struct Node *next;
} *top = NULL;
void push(int x)
{
    struct Node *t;
    t = (struct Node *)malloc(sizeof(struct Node));
    if (t == NULL)
        printf("stack is full\n");
    else
    {
        t->data = x;
        t->next = top;
        top = t;
    }
}
int pop()
{
    struct Node *t;
    int x = -1;
    if (top == NULL)
        printf("Stack is Empty\n");
    else
    {
        t = top;
        top = top->next;
        x = t->data;
        free(t);
    }
    return x;
}
void Display()
{
    struct Node *p;
    p = top;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
int isBalanced(char *exp)
{
    int i;
    for (i = 0; exp[i] != '\0'; i++)
    {
        if (exp[i] == '(')
            push(exp[i]);
        else if (exp[i] == ')')
        {
            if (top == NULL)
                return 0;
            pop();
        }
    }
    if (top == NULL)
        return 1;
    else
        return 0;
}
int pre(char x)
{
    if (x == '+' || x == '-')
        return 1;
    else if (x == '*' || x == '/')
        return 2;
    return 0;
}
int isOperand(char x)
{
    if (x == '+' || x == '-' || x == '*' || x == '/')
        return 0;
    else
        return 1;
}
char *InToPost(char *infix)
{
    int i = 0, j = 0;
    char *postfix;
    long len = strlen(infix);
    postfix = (char *)malloc((len + 2) * sizeof(char));
    while (infix[i] != '\0')
    {
        if (isOperand(infix[i]))
            postfix[j++] = infix[i++];
        else
        {
            if (pre(infix[i]) > pre(top->data))
                push(infix[i++]);
            else
            {
                postfix[j++] = pop();
            }
        }
    }
    while (top != NULL)
        postfix[j++] = pop();
    postfix[j] = '\0';
    return postfix;
}
int Eval(char *postfix)
{
    int i = 0;
    int x1, x2, r = 0;
    for (i = 0; postfix[i] != '\0'; i++)
    {
        if (isOperand(postfix[i]))
        {
            push(postfix[i] - '0');
        }
        else
        {
            x2 = pop();
            x1 = pop();
            switch (postfix[i])
            {
            case '+':
                r = x1 + x2;
                break;
            case '-':
                r = x1 - x2;
                break;
            case '*':
                r = x1 * x2;
                break;
            case '/':
                r = x1 / x2;
                break;
            }
            push(r);
        }
    }
    return top->data;
}
int main()
{
    char *postfix = "234*+82/-";
    printf("Result is %d\n", Eval(postfix));
    return 0;
}