bool isstackqueue (stackqueue Q) return Q != NULL && Q->instack != NULL && Q->outstack != NULL ; stackqueue* queue new) //@ensures is stackqueue( esult); stackqueue*Q alloc (stackqueue); Q->instack- stack-new(); Q-outstack stack_new); return Q; bool queue empty (stackqueue*Q) //@requires is stackqueue (Q); //@ensures is stackqueue (Q); return stackempty (0->instack) && stack empty (Q->outstack); void enq (stackqueue* Q, elem x) //@requires is stackqueue (Q); //@ensures is stackqueue (Q); push (Q->nstack, x); elem deq (stackqueue* Q) //@requires is stackqueue (Q); //@requires !queue_empty(Q) //@ensures is stackqueue (Q); if (stack_empty(Q->outstack)) { while stack empty(Q->instack)) push (0->outstack, pop(Q->instack)); return pop Q->outstack); 2.1 Given a queue with k elements in it, exactly how many different ways can this queue be represented using two stacks, as a function of k? way(s). 2.2 We now determine the runtime complexity of the enq and deq operations. Let k be the total number of elements in the queue. What is the worst-case runtime complexity of each of the following queue opera- tions based on the description of the data structure implementation given above? Write ONE sentence that explains each answer. enq: O because deq: O because 2.3 Using amortized analysis, we can show that the worst-case complexity of a valid sequence of n enqueue/ dequeue operations starting from an empty queue is O(n). This means that the amortized cost per operation is case cost of an individual operation may not be constant. Here, a valid sequence of queue operations must start with the empty queue, each operation must be either an enq or a deq, and you must have enough tokens. Assume that push and pop each consume one token (and emptiness tests are free). How many tokens should be charged to enqueue an e dequeue an element? Your answers should be constant integers - recall that the amortized cost is to be . Justify each answer by briefly stating for what purpose of each token is used (you may not need all lines). (1), even though the worst- lement? How many to Cost of enq: token(s), to be used as follows: 1 token to 1 token to 1 token to 1 token to Cost of deq: token(s), to be used as follows: 1 token to 1 token to 1 token to 1 token to bool isstackqueue (stackqueue Q) return Q != NULL && Q->instack != NULL && Q->outstack != NULL ; stackqueue* queue new) //@ensures is stackqueue( esult); stackqueue*Q alloc (stackqueue); Q->instack- stack-new(); Q-outstack stack_new); return Q; bool queue empty (stackqueue*Q) //@requires is stackqueue (Q); //@ensures is stackqueue (Q); return stackempty (0->instack) && stack empty (Q->outstack); void enq (stackqueue* Q, elem x) //@requires is stackqueue (Q); //@ensures is stackqueue (Q); push (Q->nstack, x); elem deq (stackqueue* Q) //@requires is stackqueue (Q); //@requires !queue_empty(Q) //@ensures is stackqueue (Q); if (stack_empty(Q->outstack)) { while stack empty(Q->instack)) push (0->outstack, pop(Q->instack)); return pop Q->outstack); 2.1 Given a queue with k elements in it, exactly how many different ways can this queue be represented using two stacks, as a function of k? way(s). 2.2 We now determine the runtime complexity of the enq and deq operations. Let k be the total number of elements in the queue. What is the worst-case runtime complexity of each of the following queue opera- tions based on the description of the data structure implementation given above? Write ONE sentence that explains each answer. enq: O because deq: O because 2.3 Using amortized analysis, we can show that the worst-case complexity of a valid sequence of n enqueue/ dequeue operations starting from an empty queue is O(n). This means that the amortized cost per operation is case cost of an individual operation may not be constant. Here, a valid sequence of queue operations must start with the empty queue, each operation must be either an enq or a deq, and you must have enough tokens. Assume that push and pop each consume one token (and emptiness tests are free). How many tokens should be charged to enqueue an e dequeue an element? Your answers should be constant integers - recall that the amortized cost is to be . Justify each answer by briefly stating for what purpose of each token is used (you may not need all lines). (1), even though the worst- lement? How many to Cost of enq: token(s), to be used as follows: 1 token to 1 token to 1 token to 1 token to Cost of deq: token(s), to be used as follows: 1 token to 1 token to 1 token to 1 token to
