Push and pop operations, Data Structure & Algorithms

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.

 

 

Posted Date: 7/10/2012 3:57:51 AM | Location : United States







Related Discussions:- Push and pop operations, Assignment Help, Ask Question on Push and pop operations, Get Answer, Expert's Help, Push and pop operations Discussions

Write discussion on Push and pop operations
Your posts are moderated
Related Questions
Each of the comparison in the binary search decrease the number of possible candidates where the key value can be searched by a factor of 2 as the array is divided into two halves

characteristics of a good algorithm

Your program should include three components selling, buying and managing for the use of sellers, buyers and the Manager, respectively. Provide a menu for a user to enter each comp

A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

Q. Give the algorithm to build a binary tree where the yields of preorder and post order traversal are given to us.

Which data structure is required to change infix notation to postfix notation?    Stack function is used to change infix notation to postfix notatio n

List various problem solving techniques. There are two techniques:- 1.  Top down 2.  Bottom- up

nested for loop for (i = 0; i for (j = 0; j sequence of statements } } Here, we observe that, the outer loop executes n times. Every time the outer loop execute

CMY Model  The cyan, magenta, yellow (CMY) colour model is a subtractive model based on the colour absorption properties of paints and inks. As such it has become the standard

I =PR/12 Numbers of years .Interest rate up to 1yrs . 5.50 up to 5yrs . 6.50 More than 5 yrs . 6.75 design an algorithm based on the above information