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

Tree traversals, There are three kinds of tree traversals, namely, Postorde...

There are three kinds of tree traversals, namely, Postorder , Preorder and Inorder. Preorder traversal: Each of nodes is visited before its children are visited; first the roo

Draw a b-tree., Q. Draw a B-tree of order 3 for the sequence of keys writte...

Q. Draw a B-tree of order 3 for the sequence of keys written below: 2, 4, 9, 8, 7, 6, 3, 1, 5, 10

Algorithms for push and pop operation, Q. Suggest a method of implementing ...

Q. Suggest a method of implementing two stacks in one array such that as long as space is there in an array, you should be capable to add an element in either stack. Using proposed

Array implementation of a circular queue, A circular queue can be implement...

A circular queue can be implemented through arrays or linked lists. Program 6 gives the array implementation of any circular queue. Program 6: Array implementation of any Circu

Column major representation, Column Major Representation In memory th...

Column Major Representation In memory the second method of representing two-dimensional array is the column major representation. Under this illustration, the first column of

Procedures, what is far and near procedures in system programming?

what is far and near procedures in system programming?

Program for linear search, Program for Linear Search. Program: Linear S...

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

Deletion of a node from a binary search tree, The algorithm to delete any n...

The algorithm to delete any node having key from a binary search tree is not simple where as several cases has to be considered. If the node to be deleted contains no sons,

What is solid modeling, What is Solid modeling Solid modeling is the mo...

What is Solid modeling Solid modeling is the most powerful of the 3-D modeling technique. It provides the user with complete information about the model. Defining an object wit

Need it urgently, Write an assembly program to separate the number of posit...

Write an assembly program to separate the number of positive numbers and negative numbers from a given series of signed numbers.

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