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

Answer:-

There are three or more way to implement stack that is by using Array,Linked List and Queue.

here I am going to describe using Array and Linked List.

Array:-

Implementation of stack using arrays is a very simple technique.Static implementation uses arrays to create stack. Static implementation using arrays is a very simple technique but is not a flexible way, as the size of the stack has to be declared during the program design, because after that, the size cannot be varied (i.e., increased or decreased). Moreover static implementation is not an efficient method when resource optimization is concerned (i.e., memory utilization).

For example a stack is implemented with array size 50. That is before the stack operation begins, memory is allocated for the array of size 50. Now if there are only few elements (say 30) to be stored in the stack, then rest of the statically allocated memory (in this case 20) will be wasted, on the other hand if there are more number of elements to be stored in the stack (say 60) then we cannot change the size array to increase its capacity.
The above said limitations can be overcome by dynamically implementing (is also called linked list representation) the stack using pointers.

/****** Program to Implement Stack using Array ******/
#include <stdio.h>
#define MAX 50
void push();
void pop();
void display();
int stack[MAX], top=-1, item;
main()
{
int ch;
do
{
printf(" 1. Push 2. Pop 3. Display 4. Exit ");
printf(" Enter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf(" Invalid entry. Please try again... ");
}
} while(ch!=4);
getch();
}

void push()
{
if(top == MAX-1)
printf(" Stack is full.");
else
{
printf(" Enter ITEM: ");
scanf("%d", &item);
top++;
stack[top] = item;
printf(" ITEM inserted = %d", item);
}
}
void pop()
{
if(top == -1)
printf(" Stack is empty.");
else
{
item = stack[top];
top--;
printf(" ITEM deleted = %d", item);
}
}
void display()
{
int i;
if(top == -1)
printf(" Stack is empty.");
else
{
for(i=top; i>=0; i--)
printf(" %d", stack[i]);
}
}

Linked List:-

In linked list implementation of a stack, every new element is inserted as 'top' element. That means every newly inserted element is pointed by 'top'. Whenever we want to remove an element from the stack, simply remove the node which is pointed by 'top' by moving 'top' to its next node in the list. The next field of the first element must be always NULL.

Each time a function is called, its local variables and parameters are “pushed onto” the stack. When the function returns,these locals and parameters are “popped.” Because of this, the size of a program’s stack fluctuates constantly as the program is running, but it has some maximum size. stack is as a last in, first out (LIFO) abstract data type and linear data structure. Linked list is a data structure consisting of a group of nodes which together represent a sequence. Here we need to apply the application of linkedlist to perform basic operations of stack.

List of advantages :

Disadvantages of Linked List

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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