2023年11月25日

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

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

ITEC 2620-A Summer 2020 Assignment Two
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)