## Polish Notations

In the early 1920s, a Polish logician, Jan Lukasiewicz invented a special notation for prepositional logic that allows to eliminate all parenthesis from formulas.  The notation is called Polish Notation, which results in a less readable expression.  Depending upon the arrangement of operators and operands in an expression, Polish notation may be classified as:

• Infix Polish Notation
• Prefix Polish Notation
• Postfix Polish Notation

Infix Polish Notation:  In this notation, the operator comes between two operands.  For example: A+B, where A, B are operands and + is an operator.

Prefix Polish Notation:  In this notation, the operator comes before two operands.  For example: +AB.

Postfix Polish Notation:  In this notation, the operator comes after two operands.  For example: AB+.

Application of Stacks:

## Multiple Stacks in an array

### Program for representing multiple stacks in one array

/*Implementing multiple stacks in a single array*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 10

void push(int,int[],int,int);
int pop(int,int[],int);
void display(int,int[],int);

/*array to top index for each stack*/
int t[MAX];
int top[MAX];

void main()
{
int arr[MAX],n,totstk,index;
int i,j,k=0,span,no,ch,num;
/*Input total elements of the array*/
/*This array may be divided into multiple stacks*/
printf(“nEnter size of the array?”);
scanf(“%d”,&n);

/*Input total stacks to be created in above array*/
printf(“nEnter total stacks to create?”);
scanf(“%d”,&totstk);

/*t[] array will contains totstk indexes for top*/
/*since total stacks to be created are totstk*/
/*Initializing t[] array with -1*/
for(i=0;i<totstk;i++)
t[i]=-1;

/*computes size of one stack*/
span=n/totstk;

/*store top of each stack in the array*/
/*this top serves as index for push/pop operations*/

top[k++]=0;
for(i=0;i<totstk-1;i++,k++)
top[k]=top[k-1]+span;

/*displaying elements of indexed array*/
for(i=0;i<totstk;i++)
printf(“%dt”,top[i]);
do{
clrscr();
printf(“n1. Push”);
printf(“n2. Pop”);
printf(“n3. Display”);
printf(“n4. Quit”);
scanf(“%d”,&ch);

if(ch!=4)
{
printf(“nEnter stack number (0 to %d)?”,totstk-1);
scanf(“%d”,&index);
}

switch(ch)
{
case 1:
printf(“nEnter number to push?”);
scanf(“%d”,&no);
push(index,arr,span,no);
break;
case 2:
num=pop(index,arr,span);
printf(“nPopped element from stack %d is %d”,index,num);
break;
case 3:
display(index,arr,span);
break;
case 4:
exit(0);
}
getch();
}while(1);
}

void push(int index,int arr[],int n,int num)
{
int topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==topid+n-1)
{printf(“nStack Full! Overflow.”);
return;
}
topelement=++t[index];
arr[topid+topelement]=num;
}
int pop(int index,int arr[],int n)
{
int topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==-1)
{printf(“nStack Empty! Underflow.”);
return -1;
}
t[index]–;
return(arr[topid+topelement]);
}
void display(int index,int arr[],int n)
{
int i,topid,topelement;
topid=top[index];
topelement=t[index];
if(topelement==-1)
{printf(“nStack Empty! Underflow.”);
return;
}
for(i=topid+topelement;i>=topid;i–)
printf(“%dt”,arr[i]);
}

## Stacks

### Representing two stacks in an array

One array may be considered to be composed of multiple stacks, such that the size of the array is divided by the number of stacks to be created, which results in representing multiple stacks in one array.

For example:  If we wish to represent two stacks in one array of size 10, then the size of the array (10) may be divided by 2, to result in two stacks each of size 5. Thus, when you push or pop an element, you must also state the stack id, along with other required information.

## Stacks

### Program to implement Stack using Linked List:

/*Implementation of stacks using linked list*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#define MAX 10

typedef struct stack
{
int info;
struct stack *next;
}stack;

/*create to allocate memory*/
stack *create()
{stack *temp = (stack *)malloc(sizeof(stack));
if(temp==NULL)
{printf(“nMemory allocation error!”);
exit(1);
}
return temp;
}

/*makenode to initialize new node*/
stack *makenode(int x)
{stack *temp=create();
temp->info=x;
temp->next=NULL;
return temp;
}

/*push to insert an element in list at beginning*/
stack *push(stack *top,int x)
{stack *temp;
stack *ptr=makenode(x);
if(top==NULL)
{top=ptr;
}
else
{ptr->next=top;
top=ptr;
}
}

/*pop to remove top element from stack*/

stack *pop(stack *top)
{stack *temp;
if(top==NULL)
{printf(“nStack Empty! Underflow.”);
return NULL;
}
printf(“nPopped element: %d”,top->info);
temp=top;
top=top->next;
free(temp);
}

/*displays contents of stack*/
void display(stack *top)
{
stack *temp;
if(top==NULL)
{printf(“nStack empty.”);
return;
}
temp=top;
while(temp!=NULL)
{printf(“%d->”,temp->info);
temp=temp->next;
}
printf(“bb “);
}

void main()
{
int ch,num;
stack *top=NULL;
while(1)
{
clrscr();
printf(“nn1. Push”);
printf(“n2. Pop”);
printf(“n3. Display”);
printf(“n4. Exit”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter number to push?”);
scanf(“%d”,&num);
top=push(top,num);
break;
case 2:
top=pop(top);
break;
case 3:
display(top);
break;
case 4:
exit(0);
default:
printf(“nInvalid choice!”);
}
getch();
}
}

## Program to implement Stack using structures

Stack is a Last In First Out linear data structure.  It can be implemented using structures.  An example to illustrate how Stacks can be implemented using structures is given below:

/*Program to implement Stack using structures*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAX 10

struct stack{
int top;
int arr[MAX];
};

/*Push to insert an element at the top of the stack */
void push(struct stack *, int);

/* Pop to return the top-most element of the stack */
int pop(struct stack *);

/* Display the contents of stack */
void display(struct stack *);

int main(){
/* stack object created */
struct stack s;
int ch, num;
s.top = -1;
while(1){
printf(“n1. Pushn2. Popn3. Displayn4. Exit”);
scanf(“%d”,&ch);
switch(ch){
case 1:
printf(“Enter number to push?”);
scanf(“%d”,&num);
push(&s,num);
break;
case 2:
num = pop(&s);
printf(“Popped element = %d”,num);
break;
case 3:
display(&s);
break;
case 4:
exit(0);
default:
printf(“Invalid choice!”);
}
getch();
}
}

void push(struct stack *s, int x){
if(s->top==MAX-1){
printf(“Stack full! Overflow.”);
return;
}
s->arr[++(s->top)]=x;
}

int pop(struct stack *s){
if(s->top==-1){
printf(“Stack empty! Underflow.”);
return -1;
}
return(s->arr[s->top–]);
}

void display(struct stack *s){
int t;
if(s->top==-1){
printf(“Stack empty!”);
return;
}
/*assigning top to another variable*/
for(t=s->top;t>=0;t–)
printf(“%dt”,s->arr[t]);
}

## Stacks

A stack is a linear data structure, which can be operated upon at only one end, which is generally referred to as the top of the stack.  An example to illustrate stack arrangement is keeping a bunch of files in a drawer, which can only be inserted at the top as well as removed from the top.  For this reason, stack is called a LIFO structure i.e. Last In First Out.

The basic operations that may be performed on stacks are push and pop operations.  Push operation refers to putting an element on the top of the stack, whereas pop operation removes the topmost element from the stack.  Stacks are required in situations where data must be stored and then processed in reverse order.  Stack is an abstract data structure.

Example: Push 5, 6, 7 will be represented in fig (i), (ii) & (iii). In the above figures, the downward pointing arrow refers to top that points to the topmost element of the stack.

Pop will be in LIFO order {7,6,5} as shown in fig. (i), (ii) & (iii). The upward pointing arrow indicates element at the top of the stack, which is removed in the order (7,6,5) as shown above.

A stack may be represented using arrays and by keeping an integer variable ‘top’ that points to the topmost element of the stack.  Simply stating, stack may be represented using structures, which is composed of an array of elements and top that refers to the topmost element of the stack.  A stack may also be represented using a linked list.  One end of the stack is considered to be fixed which is the bottom of the stack and top shifts as elements are pushed and popped.  Thus stack may be represented as follows:

struct stack{
int top;
int arr[MAX];
};

The object of the structure stack may be instantiated as follows:

struct stack s;

Example:

x Close