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

Delete a given specific node from a doubly linked list. , D elete a specif...

D elete a specific Node from Double Linked List as follows DELETEDBL(INFO, FORW, BACK, START, AVAIL,LOC) 1. [Delete Node] Set FORW [ BACK [LOC]]:= FORW[LOC]& BACK [FORW[

Briefly explain the prim''s algorithm, Question 1 Describe the following- ...

Question 1 Describe the following- Well known Sorting Algorithms Divide and Conquer Techniques Question 2 Describe in your own words the different asymptotic func

Algorithm, implement multiple stack in one dimensional array

implement multiple stack in one dimensional array

The various ways in which lc code can be accessed, Problem Your LC code...

Problem Your LC code is stored in a memory location as shown and the variable name is LC                  LC Memory address       Content(LC code)

Internal sorting, In internal sorting, all of the data to be sorted is obta...

In internal sorting, all of the data to be sorted is obtainable in the high speed main memory of the computer. We will learn the methods of internal sorting which are following:

Two sparce matrices multipilcation algorithm, Write an algorithm for multi...

Write an algorithm for multiplication of two sparse matrices using Linked Lists.

Time complexity of merge sort and heap sort algorithms, What is the time co...

What is the time complexity of Merge sort and Heap sort algorithms? Time complexity of merge sort is O(N log2 N) Time complexity of heap sort is   O(nlog2n)

Data Mining and Neural Networks, I am looking for some help with a data min...

I am looking for some help with a data mining class with questions that are about neural networks and decision trees. Can you help? I can send document with questions.

Pseudocodes, how to draw a 5 inch square on the screen using * symbol

how to draw a 5 inch square on the screen using * symbol

If else, design algorithm and flow chart that computes the absolute differe...

design algorithm and flow chart that computes the absolute difference of two values x and y

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