Java代写 | ITEC 2620-A Summer 2020 Assignment Two

本次Java代写是完成数据结构中的栈和队列

ITEC 2620-A Summer 2020 Assignment Two
Due: 2nd-July, 2020
1 Introduction: Stack and Queue
Procedures for array-implemented Stacks from the lecture notes are presented below.
StackEmpty(S)
1: if top[S] == 0
2: then return TRUE
3: else return FALSE
Push(S, x)
1: top[S] <- top[S] + 1
2: S[top[S]] <- x
Pop(S)
1: if StackEmpty(S)
2: then error “underflow”
3: else top[S] <- top[S] – 1
4: return S[top[S]+1]
Procedures for array-implemented Queues from the lecture notes are presented below.
Enqueue(Q, x)
1: Q[tail[Q]] <- x
2: if tail[Q] == length[Q]
3: then tail[Q] <- 1
4: else tail[Q] <- tail[Q] + 1
Dequeue(Q)
1: x <- Q[head[Q]]
2: if head[Q] == length[Q]
3: then head[Q] <- 1
4: else head[Q] <- head[Q] + 1
5: return x
2 What to do
• Write pseudocodes for the procedure StackFull;
• Update the Push procedure to consider the exceptional situation where the stack is full;
• Write pseudocodes for the procedures QueueFull and QueueEmpty; In particular, how would
you revise the queue-full condition “head[Q]==tail[Q]+1”, when “head[Q]==1” thus you
need to wrap around the array index?
• Update the Enqueue procedure to consider the exceptional situations where the queue is full;
• Update the Dequeue procedure to consider the exceptional situations where the queue is empty;
• Implement the pseudocodes in Java. That is,
– Use an array S[1…n] and the attribute top[S] to implement a Stack of n Elements,
where top[S]==0 means the stack is empty.
– Use an array Q[1…(n+1)] and the attributes head[Q] and tail[Q], for a Queue of
n Elements. Again, implementation of head[Q] and tail[Q] should strictly follow the
pseudocodes.
1
– Add to the Java Starter (available on Moodle) two Java classes ArrayStack.java and
ArrayQueue.java. Specifically, these two classes MUST implement respectively the interfaces Stack.java and Queue.java.
– You should NOT make any change to the three files: Element.java, Stack.java and
Queue.java.
• Write a driver class Driver.java.
– the driver class creates a stack of size n. It also creates n elements whose key values
are randomly selected from 0 inclusive to n-1 inclusive. All the n elements are initially
pushed into the stack.
– a queue of size n is also created, and the queue is initial empty.
– With the help of the empty queue, your program reorders all elements in the stack, from
top to bottom with non-increasing key values.
– Note that, in your program, change on content in the stack can only be achieved by
push/pop; Change on content in the queue can only be achieved by Enqueue/Dequeue;
– Also note that, the key value of an element can be accessed by the program, ONLY when
it is not contained in either the stack or the queue.
– How it works (illustrated with an example of size 4 stack/queue):
Initially, stack: 13,18,11,17(top); queue: empty
Goal: stack:11,13,18,19(top); queue: empty
step One: move the minimal element (key value 11) to the bottom of the stack.
step One.a: move and check all elements from the stack to the queue so you
know which element is the minimal one, resulting
stack: empty; queue: (head)17,11,18,13(tail) min. is 11
step One.b: remove Element 11 from the queue, resulting
stack: 17(top) queue: (head)18,13(tail), Element 11 is put aside
step One.c: move Element 17 from the stack to the queue, resulting
stack: empty; queue: (head)18,13,17(tail), Element 11 is still out
step One.d: push Element 11 into the stack, resulting
stack: 11(top) queue: (head)18,13,17(tail)
Note that Element 11 is now at its goal position!
step One.e: move all the remaining three elements back to the stack, resulting
stack: 11,18,13,17(top) queue: empty
We move on to step Two, on the same problem, but with problem size reduced by 1.
Continue with all the steps until all the elements are rearranged in sorted
order in the stack.
Run your Driver.java on the same example, you should generate the following output,
where
∗ pp stands for pop,
∗ ph(k) stands for pushing an element whose key value is k into the stack,
∗ dQ stands for deQueue,
∗ eQ(k) stands for enqueueing an element whose key value is k into the queue.
The example needs three steps to finish. Right before the last step, your program should
print out YourName and your ID, and a message notifying that there is just one more
step left to finish.
ph(13) ph(18) ph(11) ph(17)
Step 1
Step 1.A: pp eQ(17) pp eQ(11) pp eQ(18) pp eQ(13) Min. pos. is: 3; Min. key value is: 11.
Step 1.B: dQ ph(17) dQ
Step 1.C: pp eQ(17)
Step 1.D: ph(11)
Step 1.E: dQ ph(18) dQ ph(13) dQ ph(17)
2
Step 2
Step 2.A: pp eQ(17) pp eQ(13) pp eQ(18) Min. pos. is: 3; Min. key value is: 13.
Step 2.B: dQ ph(17) dQ
Step 2.C: pp eQ(17)
Step 2.D: ph(13)
Step 2.E: dQ ph(18) dQ ph(17)
Program written by Your Name/012345678.
One more step needed to finish!
Step 3
Step 3.A: pp eQ(17) pp eQ(18) Min. pos. is: 4; Min. key value is: 17.
Step 3.B: dQ
Step 3.C:
Step 3.D: ph(17)
Step 3.E: dQ ph(18)
3 What to submit
• A PDF file of Thirteen + pages. Exactly in the following order,
– (Page One) A cover page with print-out of
∗ Your Name/ID, and
∗ The statement: I have read and understood the Academic Honesty Statement specified
in the course outline, and I have adhered fully at all time to the academic honesty
rules and policies laid by the instructor, the School of Information Technology and
York University Senate’s Academic Integrity Policy.
– (Page Two) Updated pseudocodes for Stack.
– (Page Three) Updated pseudocodes for Queue.
– (Page Four-Five) Print-out of the source code ArrayStack.java. Provide comments
in your code to highlight locations where each one of the lines in the pseudocodes are
implemented.
– (Page Six-Seven) Print-out of the source code ArrayQueue.java. Provide comments
in your code to highlight locations where each one of the lines in the pseudocodes are
implemented.
– (Page Eight) Output from input of ph(13) ph(18) ph(11) ph(17) for Driver.java.
– (Page Nine) Output from input of ph(10) ph(20) ph(30) ph(40) for Driver.java.
– (Page Ten) Output from input of ph(40) ph(30) ph(20) ph(10) for Driver.java.
– (Page Eleven) Input stack contains 83 elements whose key values are integers drawn
uniformly from 0 to 82 inclusive (duplicates of keys possible and allowed). Output the
last FIVE steps.
– (Page Twelve) What is time complexity (in Big O notation) with respect to problem
size n of this sorting operation in terms of T(n), the total number of Pop/Push and
enQueue/deQueue operations? Provide justification of your answer.
– (Page Thirteen Plus) Source code Driver.java.
• A zipped file containing the source codes. Your program will be evaluated on correctness,
conciseness, and neatness (readability).
3


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: [email protected]  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

发表评论