6. Stack

 

Stack

• A stack is a non-primitive linear data structure. It is an ordered list in which addition of a new data item and deletion of already existing data item is done from only one end known as top of stack.
• The element which is added in last will be first to be removed and the element which is inserted first will be removed in last.
• That is why it is called Last In First Out (LIFO) or First In Last Out (FILO) type of list.
• Most frequently accessible element in the stack is the top most element whereas the least accessible element is the bottom of the stack.

1. If the sequence of operations- push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop are performed on a stack, the sequence of popped out values are?
1. 2, 1, 2, 2, 1
2. 2, 1, 2, 2, 2
3. 2, 2, 1, 2, 2
4. 2, 2, 1, 1, 2

iv. 2, 2, 1, 1, 2

2. What is the element of the stack once all the elements listed below are pushed onto? First element -> {4,2,1,4,5,3,7,8} -> Last element. Further operations -> pop, pop, push(3)
1. 3
2. 7
3. 4
4. 1

i. 3

3. The following sequence of operations is performed on a stack: PUSH(10), PUSH(20), POP, PUSH(10), PUSH(20), POP, POP, POP, PUSH(20), POP. The sequence of values popped out is?
1. 20, 10, 20, 10, 20
2. 20, 20, 10, 10, 20
3. 10, 20, 20, 10, 20
4. 20, 20, 10, 20, 10

ii. 20, 20, 10, 10, 20

Stack Implementations

Stack is generally implemented in two ways:

1. Static implementation: Here array is used to create stack. It is a simple technique but is not a flexible way of creation, as the size of stack has to be declared during program design, after that size implementation is not efficient with respect to memory utilization.
2. Dynamic implementation: It is also called linked list representation and uses pointer to implement the stack type of data structure.

1. Which one of the following node is considered the top of the stack if the stack is implemented using the linked list?
1. First Node
2. Second node
3. Last node
4. None of the above

i. First Node
Explanation: Generally the first node and the last node both can be the top of stack but if the questions specifies to choose only one, then first node will be a better answer.

2. Which of the following is true about linked list implementation of stack?
1. In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
2. In push operation, if new nodes are inserted at the end, then pop operation, nodes must be removed from the beginning.
3. Both of the above
4. None of the above

iv. None of the above

Stack Operations

1. Push operation: The process of adding new element to the top of stack is called push operation, the new element will be inserted at the top, after push operation the top is incremented by one. In the case the array is full and no element can be accommodated it is called over-flow condition.
2. Pop operation: The process of deleting an element from the top of stack is called pop operation. After every pop operation the stack top is decremented by one if there is no element in the stack and the pop operation is requested then this will result into a stack underflow condition.

1. What would be the maximum value of the top that does not cause the overflow of the stack, consider the value of top as -1 when the stack is empty.
#define SIZE 11
struct STACK
{
    int arr[SIZE];
    int top;
};
1. 8
2. 9
3. 10
4. 11

iii. 10

2. A stack is implemented as a linear array A[0 ... N-1]. Farhan writes the following functions for pushing an element E into the stack.
PUSH(top, E, N)
{
    if (X)
    {
        top = top + 1
        A[top] = E
    }
    else
    {
        print "overflow"
    }
    return top
}
Fill in the condition X.
1. top < N
2. top < N-1
3. top > 0
4. top > 1

ii. top < N-1

3. A single array A[1 ... MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1≤top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for 'stack full' is _____.
1. (top1 = MAXSIZE/2) and (top2 = MAXSIZE/2 + 1)
2. top1 + top2 = MAXSIZE
3. (top1 = MAXSIZE/2) or (top2 = MAXSIZE)
4. top1 = top2 - 1

iv. top1 = top2 - 1

4. What are the set of functions that are to be executed in a stack to get the following output?
   
   CAT
1. push(C); push(A); push(T); pop(); pop(); pop();
2. push(C); pop() ;push(A); pop(); push(T); pop();
3. pop(C); pop(A); pop(T);
4. push(C); push(A); pop(T);

ii. push(C); pop() ;push(A); pop(); push(T); pop();

5. Which of the following permutations can be obtained in the output (in same order) using a stack assuming that the input is the sequence 1,2,3,4,5 in that order?
1. 5,4,3,1,2
2. 1,5,2,3,4
3. 3,4,5,1,2
4. 3,4,5,2,1

iv. 3,4,5,2,1