Algorithmic implementation of multiple stacks, Data Structure & Algorithms

Assignment Help:

So far, we now have been concerned only with the representation of single stack. What happens while a data representation is required for several stacks? Let us consider an array X whose dimension is m. For convenience, we will assume that the indexes of array commence from 1 and end at m. If we contain only 2 stacks to implement in the similar array X, then the solution is simple.

Assume A and B are two stacks. We may define an array stack A with n1 elements and an array stack B along with n2 elements. Overflow might occur when either stacks A contains more than n1 elements or stack B have more than n2 elements.

Assume, rather than that, we define a single array stack along n = n1 + n2 elements for stack A & B together. Let the stack A "grow" to the right, and stack B "grow" to the left. In this case, overflow will takes place only when A and B together have more than n = n1 + n2 elements. It does not matter how several elements individually are there in each stack.

However, in the case of more than 2 stacks, we cannot represent these in the similar way since a one-dimensional array has two fixed points X(1) and X(m) only and each of stack needs a fixed point for its bottom most element. While more than two stacks, say n, are to be sequentially represented, initially we can divide the obtainable memory X(1:m) into n segments. If the sizes of stacks are known, then, we can assign the segments to them in proportion to the probable sizes of the several stacks. If the sizes of the stacks are not known, then, X(1:m) might be divided into equal segments. For each stack i, we will use BM (i) to represent a position one less than the position in X for the bottom most element of that stack. TM(i), 1 < i < n will point to the topmost element of stack i. We will use the boundary condition BM (i) = TM (i) if the ith stack is empty .If we grow the ith stack in lower memory indexes than i+1st stack, then, with roughly equal initial segments we have

BM (i) = TM (i) =   m/n (i - 1), 1 < i < n, as the initial values of BM (i) & TM (i).

All stacks are empty and memory is divided in roughly equal segments.

Figure illustrates an algorithm to add an element to the ith stack. Figure illustrates an algorithm to delete an element from the ith stack.

ADD(i,e)

Step1: if TM (i)=BM (i+1)

Print "Stack is full" and exit

Step2: [Increment the pointer value through one]

TM (i)← TM (i)+1

X(TM (i))← e

Step3: Exit

//remove the topmost elements of stack i.

DELETE(i,e)

Step1: if TM (i)=BM (i)

Print "Stack empty" and exit

Step2: [remove the topmost item]

e←X(TM (i))

TM (i)←TM(i)-1

Step3: Exit


Related Discussions:- Algorithmic implementation of multiple stacks

Generic doubly linked list, Your objective is to write a generic doubly lin...

Your objective is to write a generic doubly linked list class called CS228LinkedList that implements the List interface and uses a type variable T. All methods except for subList a

Use of asymptotic notation in the study of algorithm, Q. What is the need o...

Q. What is the need of using asymptotic notation in the study of algorithm? Describe the commonly used asymptotic notations and also give their significance.

Recursive function , Q. Write down the recursive function to count the numb...

Q. Write down the recursive function to count the number of the nodes in the binary tree.    A n s . R ecursive Function to count no. of Nodes in Binary Tree is writt

Write a function that performs integer division, Write a function that perf...

Write a function that performs integer division. The function should take the large number in memory location 1 and divide it by the large number in memory location 2 disregarding

Define game trees, Game trees An interesting application of trees is th...

Game trees An interesting application of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can picture the sequence of possible moves by m

A tree having ''m'' nodes has (m-1) branches. prove., Q. Prove the hypothes...

Q. Prove the hypothesis that "A tree having 'm' nodes has exactly (m-1) branches".      Ans: A tree having m number of nodes has exactly (m-1) branches Proof: A root

Which is the most suitable data type, Problem 1. You are asked to store...

Problem 1. You are asked to store Names of all 100 students of class A in your Learning Centre. Which data type will you use? What is its syntax? Explaining the data typ

Aa-trees, Red-Black trees have introduced a new property in the binary sear...

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

Develop a material requirements plan, The below figure illustrates the BOM ...

The below figure illustrates the BOM (Bill of Materials) for product A. The MPS (Material requirements Planning) start row in the master production schedule for product A calls for

Explain open addressing, Open addressing The easiest way to resolve a c...

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.

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