Stacks and Queues · Data Structures · GATE CSE

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below.

Operator	Precedence	Associativity
+	Highest	Left
−	High	Right
*	Medium	Right
/	Low	Right

The value of the expression $3 + 1 + 5 * 2 / 7 + 2 − 4 − 7 − 6 / 2$ as per the above rules is _______

Consider the following sequence of operations on an empty stack.

push(54); push(52); pop(); push(55); push(62); s = pop();

Consider the following sequence of operations on an empty queue.

enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();

The value of s + q is ______

A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT ($$n$$ refers to the number of items in the queue)?

The result evaluating the postfix expression $$10\,\,5\, + 60$$ $$\,\,6/\, * \,8\, - $$ is

A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i. If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?

The best data structure to check whether an arithmetic expression has balanced parentheses is a

Which of the following is essential for converting an infix expression to the postfix form efficiently?

Consider the following statements:
(i) First-in-first out types of computations are efficiently supported by STACKS.
(ii) Implementing LISTS on linked lists is more efficient than implementing LISTS on an array for almost all the basic LIST operations.
(iii) Implementing QUEUES on a circular array is more efficient than implementing QUEUES on a linear array with two indices.
(iv) Last-in-first-out type of computations are efficiently supported by QUEUES.

Consider a stack data structure into which we can PUSH and POP records. Assume that each record pushed in the stack has a positive integer key and that all keys are distinct. We wish to augment the stack data structure with an $\mathrm{O}(1)$ time MIN operation that returns a pointer to the record with smallest key present in the stack

1. without deleting the corresponding record, and

2. without increasing the complexities of the standard stack operations.

Which one or more of the following approach(es) can achieve it?

Consider the following expression: $x[i] = (p + r) * -s[i] + \frac{u}{w}$. The following sequence shows the list of triples representing the given expression, with entries missing for triples (1), (3), and (6).

(0)	+	p	r
(1)
(2)	uminus	(1)
(3)
(4)	/	u	w
(5)	+	(3)	(4)
(6)
(7)	=	(6)	(5)

Which one of the following options fills in the missing entries CORRECTLY?

Let S1 and S2 be two stacks. S1 has capacity of 4 elements. S2 has capacity of 2 elements. S1 already has 4 elements: 100, 200, 300, and 400, whereas S2 is empty, as shown below.

Stack S1
400 (Top)
300
200
100

Stack S2

Only the following three operations are available:

PushToS2: Pop the top element from S1 and push it on S2.
PushToS1: Pop the top element from S2 and push it on S1.
GenerateOutput: Pop the top element from S1 and output it to the user.

Note that the pop operation is not allowed on an empty stack and the push operation is not allowed on a full stack.

Which of the following output sequences can be generated by using the above operations?

Consider a sequence a of elements $$a_0=1,a_1=5,a_2=7,a_3=8,a_4=9$$, and $$a_5=2$$. The following operations are performed on a stack S and a queue Q, both of which are initially empty.

I: push the elements of a from a$$_0$$ to a$$_5$$ in that order into S.

II: enqueue the elements of a from a$$_0$$ to a$$_5$$ in that order into Q.

III: pop an element from S.

IV: dequeue an element from Q.

V: pop an element from S.

VI: dequeue an element from Q.

VII: dequeue an element from Q and push the same

VIII: Repeat operation VII three times.

IX: pop an element from S.

X: pop an element from S.

The top element of S after executing the above operations is ____________.

Consider the queues Q₁ containing four elements and Q₂ containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue (Q, element) and Dequeue (Q). The minimum number of Enqueue operations on Q₁ required to place the elements of Q₁ in Q₂ in reverse order (shown as the Final State in the figure) without using any additional storage is ______________.

Suppose a stack implementation supports an instruction REVERSE, which reverses the order of elements on the stack, in addition to the PUSH and POP instructions. Which one of the following statements is TRUE with respect to this modified stack?

Suppose a circular queue of capacity (n – 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect queue full and queue empty are

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:
i. isEmpty (Q) — returns true if the queue is empty, false otherwise.
ii. delete (Q) — deletes the element at the front of the queue and returns its value.
iii. insert (Q, i) — inserts the integer i at the rear of the queue.
Consider the following function:

void f (queue Q) { 
  int i ; 
  if (!isEmpty(Q)) { 
      i = delete(Q); 
      f(Q); 
      insert(Q, i); 
  } 
} 

What operation is performed by the above function f ?

The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * - Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:

Consider the following C program:

#include 
#define EOF -1 
     void push (int); /* push the argument on the stack */ 
     int pop (void); /* pop the top of the stack */ 
     void flagError (); 
     int main () { 
       int c, m, n, r; 
       while ((c = getchar ()) != EOF) { 
         if (isdigit (c) ) 
           push (c); 
         else if ((c == '+') || (c == '*')) { 
           m = pop (); 
           n = pop (); 
           r = (c == '+') ? n + m : n*m; 
           push (r); 
         } else if (c != ' ') 
           flagError (); 
       } 
       printf("% c", pop ()); 
    } 

What is the output of the program for the following input ? 5 2 * 3 3 2 + * +

The following function computes the value of ^mC_n correctly for all legal values m and n (m≥1,n≥0 and m>n)

int func(int m, int n) 
{ 
     if (E) return 1; 
     else return(func(m -1, n) + func(m - 1, n - 1)); 
} 

In the above function, which of the following is the correct expression for E?

An implementation of a queue Q, using two stacks S1 and S2, is given below:

void insert(Q, X){
  push(S1, X);
}

void delete(Q){
 if(stack - empty(S1)) then {
   print("Q is empty");
   return;
 }else while (!(stack - empty(S1))){
   X = pop(S1);
   push(S2, X);
 }
 X = pop(S2);
}

Let n insert and $$m( \le n)$$ delete operations be performed in an arbitrary order on an empty queue Q. Let x and y be the number of push and pop operations performed respectively in the process. Which one of the following is true for all m and n?

Assume that the operators +, -, ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, ×, +, -. The postfix expression corresponding to the infix expression a + b×c-d^e^f is

A program attempts to generate as many permutation as possible of the string “abcd” by pushing the character a,b,c,d in the same order onto a stack, but it may pop off the top character at any time. Which one of the following a strings CANNOT be generated using this program?

Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

Compute the post fix equivalent of the following expression. 3 * log(x+1) - a/2

What value would the following function return for the input x = 95?

 function fun (x:integer):integer; 
   Begin 
      If x > 100 then fun : x – 10 
      Else fun : fun(fun (x + 11)) 
   End; 

A priority queue Q is used to implement a stack that stores characters. PUSH (C) is implemented INSERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. POP is implemented as DELETEMIN(Q). For a sequence of operations, the keys chosen are in

The postfix expression for the infix expression A + B * (C + D) / F + D * E is:

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

The following sequence of operations is performed on stack: PUSH (10),PUSH (20),POP,PUSH (10),PUSH (20),POP,POP,POP,PUSH (20),POP The sequence of the value popped out is: