Question

1)Given a Stack implemented with a Linked List, and an O(1) implementation of push and pop,show the Linked List after the following commands are executed:

Stack myStack = new Stack();

myStack.push(20);

myStack.push(40);

myStack.pop();

myStack.push(60);

myStack.push(80);

2)If the same commands were used but the Stack was implemented with an Array with maximum size of 10, show what the array would look like after all these commands are executed. Assume O(1) implementation of push and pop here as well.

3)Given a Queue implemented with a Double Ended Linked List (this is a linked list with a head and tail node), and an O(1) implementation of insert and remove, show the Double Ended Linked List after the following commands are executed:

Queue myQueue = new Queue();

myQueue.insert(20);

myQueue.insert(40);

myQueue.remove();

myQueue.insert(60);

myQueue.insert(80);

4)If the same commands were used but the Queue was implemented with an Array with a maximum size of 3, show what the array would look like after all these commands are executed. Assume O(1) implementation of push and pop here as well.

Answer 1

Stack using
Linked List:
myStack.push(20); H->20
myStack.push(40); H->40 -> 20
myStack.pop();     H->20
myStack.push(60); H->60->20
myStack.push(80); H->80->60->20

Array:
myStack.push(20); |20| | | | | | | | | |
myStack.push(40); |20|40| | | | | | | | |
myStack.pop();     |20| | | | | | | | | |
myStack.push(60); |20|60| | | | | | | | |
myStack.push(80); |20|60|80| | | | | | | |

Queue using
DE Linked List:
myQueue.insert(20); H->20<-T
myQueue.insert(40); H->20->40<-T
myQueue.remove();   H->40<-T
myQueue.insert(60); H->40->60<-T
myQueue.insert(80); H->40->60->80<-T

Array:
myQueue.insert(20); |20| | |
myQueue.insert(40); |20|40| |
myQueue.remove();   | |40| |
myQueue.insert(60); | |40|60|
myQueue.insert(80); |80|40|60|

Key:

Array elements are represented by values between two '|'
Bold parts are the outputs in final state