Push and pop operations, Data Structure & Algorithms

Assignment Help:

Q. Explain that how do we implement two stacks in one array A[1..n] in such a way that neither the stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should be running in O(1) time.                                          

Ans:

Two stacks s1 and s2 can be implemented in one array A[1,2,...,N] as shown in the following figure

     1       2          3       4                                                              n-3     n-2     n-1     n

530_Push and pop operations.png

S1                                         S2

Here we define A[1] as the bottom of stack S1 and let S1 "grow" to the right and we define A[n] as the bottom of the stack S2 and S2 "grow" to the left. In this particular case, overflow will occur, only S1 and S2 together have more than n elements. This technique or method will usually decrease the number of times overflow occurs. There will be separate push1, push2, pop1 and pop2 functions which are to be defined separately for the two stacks S1 and S2.

 

 


Related Discussions:- Push and pop operations

Present the algorithm of binary search. , B i n a ry Search Alg...

B i n a ry Search Algorithm is given as follows 1. if (low > high) 2.     return (-1) 3. mid = (low +high)/2; 4. if ( X = = a [mid]) 5.      return (mid); 6.

Nothing, c++ To calculate the amount to be paid by a customer buying yummy ...

c++ To calculate the amount to be paid by a customer buying yummy cupcakes for his birth day party

What is algorithm, What is Algorithm A finite sequence of steps for a...

What is Algorithm A finite sequence of steps for accomplishing some computational task. An algorithm should Have steps which are simple and definite enough to be done

Procedure of analysis of algorithm, Example 1:  Following are Simple sequen...

Example 1:  Following are Simple sequence of statements Statement 1;  Statement 2; ... ... Statement k; The entire time can be found out through adding the times for

#title.state charts., explain two strategies to implement state charts with...

explain two strategies to implement state charts with the help of an example of each.

#titlestrings, given the string "Data Structures & , Algorithms", write a p...

given the string "Data Structures & , Algorithms", write a program that uses sequential search to return index of ''&''

Data mining assignment, The assignment aims at consolidating your knowledge...

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn

Give example of assertion and abstract data type, Give example of assertion...

Give example of assertion and abstract data type For illustration, consider Natural ADT whose carrier set is the set of non-negative integers and whose operations are the usual

Explain state space tree, Explain State Space Tree If it is convenient ...

Explain State Space Tree If it is convenient to execute backtracking by constructing a tree of choices being made, the tree is known as a state space tree. Its root indicates a

Red black tree, red black tree construction for 4,5,6,7,8,9

red black tree construction for 4,5,6,7,8,9

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd