STACK AND QUEUE

 STACK AND QUEUE

STACK:-

Stack 1: Array Implementation : Push and Pop

Consider implementing a dynamically sized stack using an array.

Create a structure

struct stack

{

int * a;

int top;

int maxSize;

};

The structure stack has a pointer 'a' to a dynamically allocated array (used to hold the contents of the stack), an integer 'maxSize' that holds the size of this array (i.e the maximum number of data that can be held in this array) and an integer 'top' which stores the array index of the top element in the stack.

Write a program to implement push and pop operation on stack and to display the contents of the stack.

In the initstack function intialize the value of top to -1 and initialize the value of maxSize.

Print the message “Stack is full” in the push function when an attempt is made to push a data into a full stack.

Print the message “Stack is empty” in the pop function and return the value -1000 when an attempt is made to pop data from an empty stack.

Refer function specifications for further details.

Input and Output Format:

Refer sample input and output for formatting specifications.

Note that the statement “The contents of the stack are” is in the main function. In the display function, if the stack is empty, print “ {}”.

[All text in bold corresponds to input and the rest corresponds to output]

Sample Input and Output:

Enter the maximum size of the stack

3

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be pushed

1

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be pushed

2

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be pushed

3

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be pushed

4

Stack is full

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

3

The contents of the stack are 1 2 3

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The popped element is 3

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The popped element is 2

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The popped element is 1

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

Stack is empty

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

3

The contents of the stack are {}

Choice 1 : Push

Choice 2 : Pop

Choice 3 : Display

Any other choice : Exit

Enter your choice

4

Function Definitions: 

void initstack (struct stack * p, int maxSize)

void push (struct stack * p, int item)

int pop (struct stack * p)

void display (struct stack p)

SOLUTION:-

#include<stdio.h>

#include<stdlib.h>

struct stack {

int *a;

int top;

int maxSize;

};

void initstack(struct stack * p, int maxSize);

void push(struct stack * p, int item);

void display(struct stack p);

int pop(struct stack * p);

void printMenu();

int main()  {

struct stack p;

int data,ch, data1, m;

printf("Enter the maximum size of the stack\n");

scanf("%d",&m);

initstack(&p,m);

do {

printMenu();

printf("Enter your choice\n");

scanf("%d",&ch);

switch(ch) {

  case 1:

printf("Enter the element to be pushed\n");

scanf("%d",&data);

push(&p, data);

break;

  case 2:

data1 = pop(&p);

if(data1 != -1000)

printf("The popped element is %d\n",data1);

break;

  case 3:

printf("The contents of the stack are");

display(p);

printf("\n");

break;

  default:

return 0;

}

} while(1);

return 0;

}

void printMenu()

{

printf("Choice 1 : Push\n");

printf("Choice 2 : Pop\n");

printf("Choice 3 : Display\n");

printf("Any other choice : Exit\n");

}

void initstack(struct stack * p, int maxSize) {

p->a=(int *)malloc(sizeof(int)*maxSize);

p->top=-1;

p->maxSize=maxSize;

}

void push(struct stack * p, int item) {

if(p->top==p->maxSize-1)

{

    printf("Stack is full\n");

    return ;

}

    p->top=p->top+1;

    p->a[p->top]=item;

}

void display(struct stack p) {

int i;

if(p.top!=-1)

for(i=0;i<=p.top;i++)

{

    printf(" %d",p.a[i]);

}

else

printf(" {}");

}

int pop(struct stack * p) {

if(p->top==-1)

{

    printf("Stack is empty\n");

    return -1000;

}

    int num=(p->a[p->top]);

    p->top=p->top-1;

    return(num);

}

QUEUE:-

Queue 1 : Array Implementation

Consider implementing a fixed size queue of maximum size 5 using an array.

Create a structure

struct queue {

int contents[5];

int front;

int count;

} ;

Note that the array contents holds the contents of the queue and the integer front stores the index of the front element in the queue.

Write a program to implement enQueue and deQueue operation on queue and to display the contents of the queue.

In the initQueue function intialize the value of front and count to 0.

Print the message “Queue is full” in the enQueue function when an attempt is made to insert a data into a full queue.

Print the message “Queue is empty” in the deQueue function and return the value -1000 when an attempt is made to delete data from an empty queue.

Refer function specifications for further details.

Input and Output Format:

Refer sample input and output for formatting specifications.

Note that the statement “The contents of the queue are” is in the main function. In the display function, if the queue is empty, print “ {}”.

[All text in bold corresponds to input and the rest corresponds to output]

Sample Input and Output:

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

3

The contents of the queue are {}

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be inserted/entered

10

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be inserted/entered

20

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be inserted/entered

30

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be inserted/entered

40

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be inserted/entered

50

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be inserted/entered

60

Queue is full

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The deleted element is 10

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The deleted element is 20

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

1

Enter the element to be inserted/entered

60

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

3

The contents of the queue are 30 40 50 60

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The deleted element is 30

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The deleted element is 40

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The deleted element is 50

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

3

The contents of the queue are 60

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

The deleted element is 60

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

2

Queue is empty

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

3

The contents of the queue are {}

Choice 1 : Enter element into Queue

Choice 2 : Delete element from Queue

Choice 3 : Display

Any other choice : Exit

Enter your choice

4

Function Definitions: 

void initQueue (struct queue * q)

void enQueue (struct queue * q, int element)

int deQueue (struct queue * p)

void display (struct queue q)

SOLUTION:-