Exam #2 Form \"B\" Directions: Answer ONE question from this page and both trace

Question

Exam #2 Form "B" Directions: Answer ONE question from this page and both traces on the pages that follow. Part I. Answer either question A or question B A. There are at least three different ways of implementing stacks. Identify and describe two of the three implementations and describe the advantages and disadvantages of each. Your response must an essay; a series of bullets or an outline is not acceptable. (50 points) B. When representing a stack using an array, Nyhoff suggests that it is wise to store the top element the stack in the last element of the array. In an essay, explain the advantages to essentially storing th stack values in reverse. Specifically indicate how operational efficiencies are achieved by storing the stack values in reverse. (50 points) Fall 2017 CS 240

Explanation / Answer

Stack is ordered group of homogeneous items.A stack is a data structure that stores data in such a way that the last piece of data stored, is the first one retrieved called LIFO[Last In, First Out] Operation.In Stack to add (push) an element :Increment top and store the element in stk[top] and to remove (pop) an element : Get the element from stk[top] and decrement top.

Stack can be implemented :
1. Using arrays
2. Using Linked lists.
3. Using Vector

[1] Array implementation of stack:
Advantages : best performance
Disadvantage : Array having ixed size
Basic implementation :
[1] initially empty array
[2] field to record where the next data gets placed into
[3] if array is full, push() returns false
      otherwise adds it into the correct spot
[4] if array is empty, pop() returns null
      otherwise removes the next item in the stack

[2] Linked-list implementation of stack :

Advantages:
[1] Always constant time to push or pop an element
[2] Can grow to an infinite size

Disadvantages
[1] The common case is the slowest of all the implementations
[2] Can grow to an infinite size

A singly-linked list(SLL) is a way to implement it .The header of the list points to the top of the stack.
Pushing is inserting an element at the front of the list and Popping is removing an element from the front of the list.With a linked-list representation, overflow will not happen (unless you exhaust memory, which is another kind of problem). Underflow can happen, and should be handled the same way as for an array implementation. When a node is popped from a list, and the node references an object, the reference (the pointer in the node) does not need to be set to null.

In SLL
[]->[]->[]->x
^
Head Pointer/ Start

1. It should have a head pointer and a tail.
2. When head points to null then the stack is empty.
3. You can keep an upper limit defined to check stack as full:
#define MAXSIZE 1000
Keep a counter to keep track of the size of current stack.
4. Push() should create a new node at 'start' each time and assign the value (to be pushed) to it.
5. Pop() should return the value of the start/head pointer, move head pointer to the next node and delete the previous node.

[3] Vector

Advantages :
[1] grows to accommodate any amount of data
[2] second fastest implementation when data size is less than vector size

Disadvantage :
[1] slowest method if data size exceeds current vector size
[2] wasted space if anomalous growth
     vectors only grow in size – they don’t shrink

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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