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
Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

The quick sort algorithm exploit design technique Divide and Conquer

How divide and conquer technique can be applied to binary trees?  As the binary tree definition itself separates a binary tree into two smaller structures of the similar type,

Develop a program that accepts the car registration( hint: LEA 43242010)

What is complexity of an algorithm? What is the basic relation between the time and space complexities of an algorithm? Justify your answer by giving an example.

The time required to delete a node x from a doubly linked list having n nodes is O (1)

include int choice, stack[10], top, element; void menu(); void push(); void pop(); void showelements(); void main() { choice=element=1; top=0; menu()

What do you understand by term structured programming? Explain the structured programming as well.                                 Ans. S tructured Programming is expla

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

What is Keyed Access- Container A collection may allow its elements to be accessed by keys. For instance, maps are unstructured containers which allows their elements to be