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

What is assertions, What is Assertions Introduction At every point...

What is Assertions Introduction At every point in a program, there are generally constraints on the computational state that should hold for program to be correct. For ins

Define big oh notation, Big oh notation (O) : The upper bound for the funct...

Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real

What is diffuse illumination, Diffuse Illumination Diffuse illuminatio...

Diffuse Illumination Diffuse illumination means light that comes from all directions not from one particular source. Think about the light of a grey cloudy day as compared to

Process of accessing data stored in a serial access memory, The process of ...

The process of accessing data stored in a serial access memory is same to manipulating data on a By using stack  method.

Explain insertion procedure into a b-tree, Ans: I nsertion into the B...

Ans: I nsertion into the B-tree: 1.  First search is made for the place where the new record must be positioned. As soon as the keys are inserted, they are sorted into th

Structural Induction, Let a be a well-formed formula. Let c be the number o...

Let a be a well-formed formula. Let c be the number of binary logical operators in a. (Recall that ?, ?, ?, and ? are the binary logical operators). Let s be the number of proposit

Use a random number generator to create 10 numbers, Use a random number gen...

Use a random number generator to create 10 numbers between 1 and 1000 and store them in 2 different arrays.  The first array should contain the numbers as they are generated.  The

Sorting, explain quick sort algorithm

explain quick sort algorithm

Asymptotic notation, Asymptotic notation Let us describe a few function...

Asymptotic notation Let us describe a few functions in terms of above asymptotic notation. Example: f(n) = 3n 3 + 2n 2 + 4n + 3 = 3n 3 + 2n 2 + O (n), as 4n + 3 is of

FOLDING METHOD, 12345 SOLVE BY USING FOLDING METHOD

12345 SOLVE BY USING FOLDING METHOD

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