Need this as soon as possible C. The table below shows a representation of a sta

Question

Need this as soon as possible

C. The table below shows a representation of a stack. The top row contains the contents of the stack; the bottom row represents the positions in a six element array of ints. The first value placed onto the stack is the 27, the last value placed onto the stack is the 11. 27 What would Nyhoff think about this method of representing the stack? What are its advantages and disadvantages? Identify an alternate way of arranging the stack values in an array and explain why the method you identify is a "better" method. Your response must be an essay; a series of bullets or an outline is not acceptable.

Explanation / Answer

ap per the given stack representation

whenever we need to insert any element in stak we need to shift the entire content of the stack to one place right (ie element at index 0 will become element at index 1 and so on.) starting from the bottom element in stack first then we can insert element at top of stack ie at index 0.

same issue will happen when we have to delete /pop an element fro the given stack design we have to pop element first and then shift all the values to one place left towards index 0 (ie element at index 1 will become element at index 0 and so on) starting from the first element at index 1.

both these operations push/pop in stack(given above) can not be done in O(1) time both needs O(n) time, so using this implementation of stack will have high complexity.

This can be done in O(1) time if we arrange our stack as below.

maintain two index :

Top of stack (TOS) = 4

Bottom of stack (BOS) = 0

PUSH Operation:

initially TOS and BOS are at -1

for push if TOS and BOS == -1 set TOS=BOS=1

push elemet at TOS index

for any push in stack we check if TOS + 1 < size of array then

set TOS = TOS + 1 then

put new element at index TOS

An overflow will be detected if TOS + 1 == array size, then push will fail resulting an error

POP operation:

for any pop operation see if TOS and BOS are at -1 means there is no element in stack. UnderFlow error

if both are at same location ie TOS == BOS then there is only one element pop elelemt from TOS and then set TOS = -1 and BOS = -1 to mark stack as empty.

for all other case pop from index = TOS

then set TOS = TOS - 1

example with 4 size arry initially TOS=-1 and BOS=-1 arraySize=4

PUSH 11     TOS=TOS+1 = 0 and BOS=BOS+1 = 0

PUSH 22     TOS=TOS+1 = 1 and BOS= 0

PUSH 33 TOS=TOS+1 = 2 and BOS= 0

PUSH 44 TOS=TOS+1 = 3 and BOS= 0

PUSH 44 TOS= 3 and BOS = 0   overflow error as TOS + 1 = 3 + 1 == arraySize

POP TOS=TOS - 1 = 2 and BOS=0

POP TOS=TOS - 1 = 1 and BOS=0

POP TOS=TOS - 1 = 0 and BOS=0

POP TOS=TOS - 1 = -1 stack empty so set BOS = -1

POP TOS = -1 and BOS = -1 error underflow

27 1 9 22 11 0 1 2 3 4 5

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.