用Python实现Stack和Queue结构，代写完成一个Banana的文字游戏。
Background
Let’s play a game… the banana game! This one doesn’t involve any coding at
all, we’re just working out manually. It should give you some practice with
the general ideas of stacks and queues.
The BANANA game
The object of the game is to transform a word (source word) into another word
(goal word) using only the container provided (the container must be left
empty at the end of the game). This means that we can’t add or delete any
letters, but we can re-arrange them by putting them into a container and
taking them out again. At each stage, we have three options:
- Add the next letter of source word onto the end of goal word (we’ll call this move)
- Put the next letter from source word into the container (we’ll call this put)
- Remove a letter from the container and add it to the end of goal word (we’ll call this get)
For example, if we wanted to change the word CAT into the word ACT, we could
do so with a simple container that only holds one letter (we’ll call this
container a Bucket): - put(C)
- move(A)
- get(C)
- move(T)
Try it out and make sure you understand how that works before you continue.
Using a Queue
With our simple container, we can’t do too much. For example, there’s no way
we could change NICK into
CNKI. (Try it… doesn’t work). But could we do it if we had a Queue as our
container? Let’s see:
| Operation | source word | goal word | Container |
|---|---|---|---|
| NICK | |||
| put(N) | ICK | N | |
| put(I) | CK | NI | |
| move(C) | K | C | NI |
| get(N) | K | CN | I |
| move(K) | CNK | I | |
| get(I) | CNKI | ||
| Try changing BANANA into AAABNN. Make sure you can do it before moving on. |
Stacks
What if we want to change BANANA into AAANNB? Well now we have a problem.
We’ve put the B into our container (a Queue), which means if we want to put
anything else in (the Ns), we’ll need to dequeue our B before we can get to
the Ns. So we’re stuck (convince yourself of this before moving on).
Maybe a new ADT will help us:
In lecture, we defined a Queue as: A container of objects accessed in FIFO
(First-In First-Out) order. What if we had a container that held objects in
LIFO (Last-In First-Out) order? You can think of this as putting each new item
on top of the previous items, so we can only access the most recently added
item at any given time. So we’ll call this new container a Stack.
Can we solve our problem using a Stack as our container? Let’s see:
| Operation | source word | goal word | Container |
|---|---|---|---|
| BABABA | |||
| put(B) | ANANA | B | |
| move(A) | NANA | A | B |
| put(N) | ANA | A | BN |
| move(A) | NA | AA | BN |
| put(N) | A | AA | BNN |
| move(A) | AAA | BNN | |
| get(N) | AAAN | BN | |
| get(N) | AAANN | B |
Your Task
Your task this week is to play the Banana Game (who says CS students can’t
have any fun?). Try to create the following permutations of BANANA using the
containers (bucket, stack and queue):
- AAABBN
- AAANNB
- BNAAAN
- NBNAAA
- NNAAAB
- NNBAAA
- ANANAB
- NABANA
- NANANANABATMAN
What to Hand in
On Markus, you must submit a file called ex1.txt Note the file extension, it’s
not a Python file. Where, for each of the above cases, you indicate which (if
any) of the three containers (Stack, Queue or Bucket) can be used to solve the
banana game, and for each container that can be used, the series of operations
that will turn BANANA into the given permutation (note that there may be more
than one solution). For any example that can’t be solved using any of the
containers, simply write impossible.
Your file should be formatted as follows: each section will start with the
word number on a line by itself. The next line will be just the word
impossible if it can’t be done with any container, or the list of containers
with which it is possible. For every container with which the game can be
solved, there will then be a line containing the container name, followed by a
move list separated by spaces
A properly formatted, but in no way correct example submission file is below:
impossible
bucket stack queue
bucket put(A) move(B) get(A)
stack put(A) move(B) get(A)
queue put(A) move(B) get(A)
queue
queue put(A) put(B) move(C) get(A) get(B)
