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
A queue is a particular type of collection or abstract data type in which the entities in the collection are went in order and the principal functions on the collection are the add

What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n

Question 1 Discuss the advantages of implementation checks preconditions Question 2 Write a ‘C' program to search for an item using binary search Question 3 Show that To

Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

Red-Black trees have introduced a new property in the binary search tree that means an extra property of color (red, black). However, as these trees grow, in their operations such

Write down any four applications of the queues.                                                            Ans. A pp li cation of Queue is given below (i)  Queue is

This algorithm inputs 3 numbers, every number goes through successive division by 10 until its value is less than 1. An output is produced which comprise the number input and a val

Graph Traversal In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do not have any single vertex singled out as spe

What is an algorithm?  What are the characteristics of a good algorithm? An algorithm is "a step-by-step process for accomplishing some task'' An algorithm can be given in many

Insertion: Records has to be inserted at the place dictated by the sequence of keys. As is obvious, direct insertions into the main data file would lead to frequent rebuilding of