(a) For a stack that currently contains N elements, (and assuming a sensible stack impementation) which answer below best represents the time needed to push a new element on the stack?
Sample solution A reasonable stack implementation needs only a constant number of steps to push a new element, hence O(1) |
(b) Suppose we have typical stack and queue classes that includes the following methods (amongst others):
Stack Queue
---------------- --------------------
void push(int i) void enqueue(int i)
void pop(int &i) void dequeue(int &i)
bool isempty() bool isempty()
If a stack contains values 1,2,3,4,5 (in that order),
and we pass it as a parameter to the function F below,
what values will it contain (and in what order) afterwards?
void F(Stack &S)
{
int i;
Queue Q;
while (!S.isempty()) {
S.pop(i);
Q.enqueue(i);
}
while (!Q.isempty()) {
Q.dequeue(i);
S.push(i);
}
}
Sample solution Assuming 1 is the top of the stack, then the items are enqueued in order 1, 2, 3, 4, 5 Then the dequeued items are pushed in order 1, 2, 3, 4, 5 which means the resulting stack contents are 5, 4, 3, 2, 1 i.e. the stack contents are reversed by function F |