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

Answer 1

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("\n\n\n\n1.\tPush\n2.\tPop\n3.\tDisplay\n4.\tExit\n");
printf("\nEnter 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("\n\nInvalid entry. Please try again...\n");
}
} while(ch!=4);
getch();
}

void push()
{
if(top == MAX-1)
printf("\n\nStack is full.");
else
{
printf("\n\nEnter ITEM: ");
scanf("%d", &item);
top++;
stack[top] = item;
printf("\n\nITEM inserted = %d", item);
}
}
void pop()
{
if(top == -1)
printf("\n\nStack is empty.");
else
{
item = stack[top];
top--;
printf("\n\nITEM deleted = %d", item);
}
}
void display()
{
int i;
if(top == -1)
printf("\n\nStack is empty.");
else
{
for(i=top; i>=0; i--)
printf("\n%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 :

1. Linked List is Dynamic data Structure .
2. Linked List can grow and shrink during run time.
3. Insertion and Deletion Operations are Easier
4. Efficient Memory Utilization ,i.e no need to pre-allocate memory
5. Faster Access time,can be expanded in constant time without memory overhead
6. Linear Data Structures such as Stack,Queue can be easily implemetedusing Linked list

Disadvantages of Linked List

1. Memory Usage:- More memory is required to store elements in linked list as compared to array. Because in linked list each node contains a pointer and it requires extra memory for itself.
2. Traversal:- Elements or nodes traversal is difficult in linked list. We can not randomly access any element as we do in array by index. For example if we want to access a node at position n then we have to traverse all the nodes before it. So, time required to access a node is large.
3. Reverse Traversing:- In linked list reverse traversing is really difficult. In case of doubly linked list its easier but extra memory is required for back pointer hence wastage of memory.