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
How do you rotate a Binary Tree?  Rotations in the tree: If after inserting a node in a Binary search tree, the balancing factor (height of left subtree - height of right

implement multiple stacks in a single dimensional array. write algorithm for various stack operation for them

The  total  of  time  needed  by  an algorithm to run to its completion is termed as time complexity. The asymptotic running time of an algorithm is given in terms of functions. Th

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Determine in brief the Painter Algorithm a) The farthest polygon, namely the rectangle PQRS, is stored first. (b) The next farthest, the quadrilateral ABCD, is superpo

In the earlier unit, we have discussed about the arrays. Arrays are data structures of fixed size. Insertion & deletion involves reshuffling of array elements. Thus, arraymanipulat

Need help with Data Structures assignment requiring C++ program

What is bubble sort? Bubble Sort: The basic idea in bubble sort is to scan the array to be sorted sequentially various times. Every pass puts the largest element in its corr

You are supposed to do the following: Write a parallel implementation of the raytracer using pthreads. Measure and compare the execution times for (i) the sequential ver

Hi, can you give me a quote for an E-R diagram