CTEC2901 Data Structures and Algorithms: Queue & Sorting Analysis

This assignment solution focuses on data structures and algorithms, specifically queue operations, stack implementation, and sorting algorithms. It includes the implementation of queue and stack methods like `printLocations`, `queueToStack`, and `stackToQueue`, along with an analysis of their worst-case time complexity. The assignment further explores a queue reversal method using a stack. Additionally, the solution provides a step-by-step walkthrough of Bubble Sort and Selection Sort algorithms applied to given sequences, illustrating each iteration. Desklib provides a platform for students to access a wide range of solved assignments and past papers.

Running head: COMPUTER SCIENCE
Computer Science
Name of the Student:
Name of the University:
Author note:

1
COMPUTER SCIENCE
Question 1
Answer A
public void printLocations(Queue locations){
String str;
while(locations.isEmpty()==false){
str = locations.dequeue();
System.out.println(str);
}
}
Worst Case complexity: O(n)
Answer B
public void queueToStack(Queue queue, Stack stack){
String str;
while(queue.isEmpty()==false){
str = queue.dequeue();
stack.push(str);
}
}
Worst Case complexity: O(n)
Answer C
public void stackToQueue (Queue queue, Stack stack){
String str;
while(stack.isEmpty()==false){
str = stack.pop();
queue.enqueue(str);
}
}
Worst Case complexity: O(n)

2
COMPUTER SCIENCE
Answer E
public void reverse(Queue locations){
Stack stack = new Stack();
String str;
while(queue.isEmpty()==false){
str = queue.dequeue();
stack.push(str);
}
while(stack.isEmpty()==false){
str = stack.pop();
queue.enqueue(str);
}
}
Considering that the queue consists of the following data :
Original Queue:
jungle trail
waterfall
beach
cave
Creating the stack from the queue with FIFO technique…
Stack:
jungle trail
waterfall
beach
cave

3
COMPUTER SCIENCE
The queue is emptied from the front that is “cave” and then this value is inserted into the stack.
Then “beach” is taken out from the queue and put into stack. Similarly, the queue is dequeued
from the front and the stack is filled. In this situation, the stack looks exactly like the queue was
at the beginning.
Filling the queue by removing elements from the stack following LIFO technique…
Queue:
cave
beach
waterfall
jungle trail
Once the stack has been filled, the stack is now emptied one from the top and the values are
enqueued into the queue. The new formed queue is reversed as the stack follows a LIFO
technique and it gives out elements from its top instead of its front and these elements are put in
as the queue’s front. This finally creates the final queue as shown above, which is reversed from
the original.
Worst Case complexity: O(n)
Question 2
Bubble Sort
Sequence 1
Iteration 1: 21 19 6 40

4
COMPUTER SCIENCE
Iteration 2: 19 6 21 40
Iteration 3: 6 19 21 40
Sequence 2
Iteration 1: 40 28 16 45
Iteration 2: 28 16 40 45
Iteration 3: 16 28 40 45
Sequence 3
Iteration 1: 16 28 40 45
Iteration 2: 16 28 40 45
Iteration 3: 16 28 40 45
Selection Sort
Sequence 1
Iteration 1: 6 40 19 21
Iteration 2: 6 19 40 21
Iteration 3: 6 19 21 40
Sequence 2
Iteration 1: 16 40 28 45
Iteration 2: 16 28 40 45
Iteration 3: 16 28 40 45
Sequence 3

5
COMPUTER SCIENCE
Iteration 1: 16 28 40 45
Iteration 2: 16 28 40 45
Iteration 3: 16 28 40 45