SP Tutorials

The algorithm of infix to postfix conversion using Stack is as follows :

Algorithm Infix_to_Postfix

Input : Infix expression in form of a string

Output : Postfix expression in form of a string

START

Step 1 : Create Stack

Step 2 : for each character 't'  in input             

do                        

if ('t' is an operand) then                                 

output 't'                        

else if ('t' is right parenthesis) then                                  

pop and output tokens until a left parenthesis is popped                        

else   // t is an operator or left parenthesis                                  

pop and output tokens until one of lower priority than 't' is encountered or a left parenthesis is encountered or the stack is empty                                  

Push 't'                       

end if

Step 3 : POP and output all tokens until stack is empty

STOP

Time Complexity : O (n)

The goal of the three-schema architecture, illustrated in above figure, is to separate the user applications from the physical database. In this architecture, schemas can be defined at the following three levels:

1. The internal level has an internal schema,which describes the physical storage structure of the database. The internal schema uses a physical data model and describes the complete details of data storage and access paths for the database.

2. The conceptual level has a conceptual schema, which describes the structure of the whole database for a community of users. The conceptual schema hides the details of physical storage structures and concentrates on describing entities, data types, relationships, user operations, and constraints. Usually, a representational data model is used to describe the conceptual schema when a database system is implemented.

3. The external or view level includes a number of external schemas or user views. Each external schema describes the part of the database that a particular user group is interested in and hides the rest of the database from that user group. Each external schema is typically implemented using a representational data model.

Differences between 3-tier and 2-tier architectures

1) Two tier architecture is similar to client-server model where the application at the client end directly communicates with the database at the server side. In three-tier architecture, the client does not directly communicate with the server. Instead, it interacts with an application server which further communicates with the database system and then the query processing and transaction management takes place. This intermediate layer acts as a medium for exchange of partially processed data between server and client

The basic operations required to manipulate a stack are:

PUSH: To insert an item into stack.

POP: To remove an item from stack.

We describe these two operations as two separate algorithms as shown below-

 Algorithm Push

Input: An element ITEM to be pushed onto the stack.

Output: A stack with a newly pushed ITEM at the TOP position

Data structure: An array A with TOP as the pointer

 Step 1: START

Step 2: If (TOP>=SIZE) then

Step 3:             Print “Stack is full”

Step 4: Else

Step 5:             TOP = TOP + 1

Step 6:             A[TOP] = ITEM

Step 7: EndIf

Step 8: STOP

 Algorithm Pop

Input: A stack with elements.

Output: Removes an ITEM from the top of the stack if it is not empty.

Data structure: An array A with TOP as the pointer.

 Step 1: START

Step 2: If (TOP<1) then

Step 3:             Print “Stack is empty”

Step 4: Else

Step 5:             ITEM = A[TOP]

Step 6:             TOP = TOP – 1

Step 7: EndIf

Step 8: STOP

#define SIZE 10 int st[SIZE]; int tos = -1; void push(int item) {    if(tos == SIZE - 1)    {        printf("\nStack overflow!");    }    else    {        ++tos;        st[tos] = item;    } }

#include<stdio.h> #define SIZE 3

void push(int item);   // declaration void pop();   // declaration void peek();

int st[SIZE]; int tos = -1;

int main() {    int choice, item;    do    {        printf("\n1. PUSH\n2. POP\n3. PEEK\n4. EXIT");        printf("\nEnter your choice : ");        scanf("%d",&choice);        switch(choice)        {            case 1:                printf("\nEnter the item to be pushed : ");                scanf("%d",&item);                push(item);                break;            case 2:                pop();                break;            case 3:                peek();                break;            case 4:                printf("\nGoodbye!");                break;            default:                printf("\nInvalid choice! Try again");        }    }while(choice != 4);    return 0; }

void push(int item) {    if(tos == SIZE - 1)    {        printf("\nStack overflow!");    }    else    {        ++tos;        st[tos] = item;    } }

void pop() {    if(tos == -1)    {        printf("\nStack underflow");    }    else    {        printf("\nPOPPED element is %d",st[tos]);        --tos;    } }

#include<stdio.h> #define LENGTH 3 void enqueue(int item); void dequeue(); void display();

int front = -1, rear = -1; int cq[LENGTH];

int main() {    int choice, item;    do    {        printf("\n1. ENQUEUE\n2. DEQUEUE\n3. DISPLAY\n4. EXIT");        printf("\nEnter choice : ");        scanf("%d",&choice);        switch(choice)        {            case 1:                printf("\nEnter item to insert : ");                scanf("%d",&item);                enqueue(item);                break;            case 2:                dequeue();                break;            case 3:                display();                break;            case 4:                printf("\nEnd of program");                break;            default:                printf("\nInvalid input. Please try again");        }    } while(choice != 4);    return 0; }

void enqueue(int item) {    if((rear == LENGTH - 1 && front == 0) || (front == rear + 1))        printf("\nQueue is full");    else    {        if(front == -1) // same as if (rear == -1)        {            front = rear = 0;            cq[rear] = item;        }        else        {            rear = (rear + 1) % LENGTH;            cq[rear] = item;        }        printf("\nENQUEUE is successful");    } }

void dequeue() {    if(front==-1)   // same as if(rear == -1) printf("\nQueue is empty"); else { if(rear == front) //contains only one element? { front = rear = -1; } else        {            front=(front + 1) % LENGTH;        }        printf("\nDEQUEUE successful"); } }

void display() {    int i;    if (front == -1)    {        printf("\nQueue is Empty");        return;    }    printf("\nElements in Circular Queue are: ");    if (rear >= front)    {        for (i = front; i <= rear; i++)            printf("%d ",cq[i]);    }    else    {        for (i = front; i < LENGTH; i++)            printf("%d ", cq[i]);

struct node

{

int data;

struct node *link;

};

void maximum (struct node *h)

{

     struct node *ptr = h; int max;

    if(h == NULL)  // empty list condition

    {

         printf(“\nList is empty”);

    }

    else

    {  

            max = ptr -> data;   // assuming 1st node to be maximum

            ptr = ptr -> link;      // check starts from next node

            while (ptr != NULL)  // till last node is processed

           {

                   if (ptr -> data > max)   // is current node > max ?

                   {

                          max = ptr -> data;

                   }

                   ptr = ptr ->link;

            }

           printf (”\n Maximum node value = %d”,max);

    }

struct node

{

int data;

struct node *link;

};

void sumOddEven (struct node *h)

{

     struct node *ptr = h; int sumOdd = 0, sumEven = 0;

     if(h == NULL)  // empty list condition

    {

         printf(“\nList is empty”);

    }

    else

    { 

            while (ptr != NULL)  // till last node is processed

           {

                    if (ptr -> data % 2 == 0)

                    {

                          sumEven = sumEven + ptr->data;

                    }

                    else

                    {

                          sumOdd = sumOdd + ptr->data;

                    }

                    ptr = ptr ->link;

            }

            printf (”\n ODD SUM = %d and EVEN SUM = %d”,sumOdd, sumEven);

    }

struct node

{

int data;

struct node *link;

};

int sumOfNodes(struct node *h)

{

 struct node *ptr = h; int sum = 0;

 if(h == NULL)  // empty list condition

 {

     printf(“\nList is empty”);

 }

 else

 {

            while (ptr != NULL)  // till last node is processed

           {

                    sum = sum + ptr->data;

                    ptr = ptr ->link;

            }

 }

return sum;

struct node

{

int data;

struct node *link;

};

int countNodes(struct node *h)

{

 struct node *ptr = h; int count = 0;

 if(h == NULL)  // empty list condition

 {

     printf(“\nList is empty”);

 }

 else

 {

            while (ptr != NULL)  // till last node is processed

           {

                    ++count;

                    ptr = ptr ->link;

            }

  }

 return count;

struct node

{

 int data;

 struct node *link;

};

void display(struct node *h)

{

  struct node *ptr = h;

  if(h == NULL) // empty list condition

  {

      printf(“\nList is empty”);

  }

  else

  {

             while (ptr != NULL) // till last node is processed

            {

                     printf (“%d\t”,ptr->data);

                     ptr = ptr ->link;

             }

       }