KEMBAR78
Advanced Stack Implementations | PDF | Subroutine | Class (Computer Programming)
Scribd
Upload
101 views2 pages

Advanced Stack Implementations

The document provides instructions for 7 programming assignments involving stacks. Assignment 1 involves implementing a stack using an array. Assignment 2 implements a stack using a linked list. Assignment 3 modifies Assignment 1 to return the minimum element in constant time using two stacks. Assignment 4 optimizes Assignment 3 to return the minimum without an auxiliary stack. Assignment 5 implements two stacks within a single array. Assignment 6 adds a sort function to Assignment 1. Assignment 7 converts infix expressions to postfix and prefix using a character stack.

Uploaded by

Gump Forest
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
101 views2 pages

Advanced Stack Implementations

The document provides instructions for 7 programming assignments involving stacks. Assignment 1 involves implementing a stack using an array. Assignment 2 implements a stack using a linked list. Assignment 3 modifies Assignment 1 to return the minimum element in constant time using two stacks. Assignment 4 optimizes Assignment 3 to return the minimum without an auxiliary stack. Assignment 5 implements two stacks within a single array. Assignment 6 adds a sort function to Assignment 1. Assignment 7 converts infix expressions to postfix and prefix using a character stack.

Uploaded by

Gump Forest
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Lab 4

Instruction: For each and every assignment, create a project. Define the class, data members and
member functions in .h file. Implementation detail in separate file and driver code in separate file. In
the driver code create an object and perform operations to test the utility of the project.

1. Create a class called Stack, Implement Stack using an array.

class stack

int *arr;

int top;

int capacity;

public:

stack(int size = SIZE); // constructor

~stack(); // destructor

void push(int); // push the element into the stack

int pop(); // pop the element from the top

int peek(); // search the element in the stack

int size(); // Return size of stack

bool isEmpty(); // return true if stack is empty

bool isFull(); // return true if stack is full

};

2. Create a class called stack similar member functions as above. Implement stack using linked
list.
3. Modify question 1, design a stack that returns the minimum element in constant time. Use
two stacks, main stack to store elements and auxiliary stack to store the required elements
needed to determine the minimum number in constant time. Other operations on the stack
remain same (push, pop, peek). If the element is removed from the main stack, similar
element should also be removed from the auxiliary stack if present.
4. Optimize the above code to return the minimum element in constant time without using
auxiliary stack.
5. Implement two stacks in a single array. Both the stacks can grow towards each other with no
fixed capacity (array is not divided into two halves, one for each stack).

class Stack

int *arr;

int capacity;
int top1, top2;

public:

// Constructor

Stack(int n)

capacity = n;

arr = new int[n];

top1 = -1;

top2 = n;

void push1(int key); // Function to insert a given element into the first stack

void push2(int key); // Function to insert a given element into the second stack

int pop1(); // Function to pop an element from the first stack

int pop2(); // Function to pop an element from the second stack

int size1(); // Return size of first stack

int size2(); // Return size of second stack

};

6. Update the assignment 1 with additional member function called sortstack. This function
should be a recursive method to sort a stack in ascending order.
7. Write a program to convert infix expression into postfix and prefix expression using the class
Stack. Stack is of type char.

int main()
{
stack s1;
s1.getInfixExpr(); // function which store expression, "(P+(Q*R)/(S-t))"

s1.infixToPostfix(); // convert infix into postfix

s1.infixToPrefix(); // convert infix to prefix


return 0;
}

You might also like