Basic stack operations
Stacks are Abstract Data Structures (ADTs) which exhibit Last In First Out (LIFO) behaviour. They can be static (fixed size) or dynamic (changeable size) just as lists can be. In common with most other ADTs, they are implemented using lists / arrays.
Implementation of a stack involves five operations ...
- PUSH - an item is added to the top of the stack and the '
topOfStack' pointer is moved up
- POP - the item at the top of the stack is copied and the '
topOfStack' pointer moves down
- PEEK - the value at the top of the stack is copied but the '
topOfStack' pointer remains the same
- EMPTY - returns
True if the stack is empty (private normally)
- FULL - returns
True if the stack is full (private normally)
- SIZE - returns the number of items on the stack
Static implementations of stacks can overflow if you try to push on an item when the stack is already full. In practice, you would always check whether the stack was full before attempting this. All stack implementations can underflow if you try to remove an item from an empty stack. Again, in practice, we would check for this first before trying to execute a POP operation and this error should never occur.
Task 1.1 Class based stack implementation
 - First, download the Python script, staticStack.py, open it in IDLE and run it.
- Create a blank word processed document with a suitable header and footer and use screenshots and written explanation to document what you have done and what you have learnt. Make sure that the screenshots are clear.
- Inspect the script - you should find all the operations stated above implemented. Print the script out for your notebooks. Use Notepad++ for this because it will print it in colour and it looks nice!
- Firstly, create a new stack object with 10 empty positions by typing the following command at the prompt, then pressing the ENTER key afterwards.
>>> myStack = stack(10)
- Investigate your stack using the following commands. Try to break it and see how robust it is (well designed interface, see?) To inspect the contents of the stack, issue the
print(myStack) command which will invoke the __str__ magic method to print out the stack object.
myStack.push(item)
myStack.pop()
myStack.peek()
- For each of the
.push(), .pop() and .peek() methods of the stack class, write a pseudocode algorithm and create a flowchart using flowcharting software like yEd. Copy your flowchart onto your word processed document.
- Print out your word processed document for your notes.
OUTCOME : A word processed document with lots of stuff about stacks on it. |
Stacks find use in all manner of computational and real life situations.
- Reverse Polish Notation calculations (see Witaj!)
- Storing return addresses in subroutine calls / recursion / nested loops
- Most recently used commands (command history)
- Reversing the order of a list
Stack Frames and the Call Stack
Stacks are used to store information about running programs. When program execution encounters a subroutine call, the program leaves the currently executing instruction and begins execution at another part in the program. To keep track of ...
- The parameters that are passed to the subroutine
- The state of execution of the program prior to the subroutine call
- The return address to come back to after subroutine execution is complete
... a stack (or rather a combination of stacks) is used.
Task 1.2 Stack frame
Copy the following diagram into your notebooks.
Click to enlarge
Now visit this website and write some brief notes about the call stack from sections 1.4.2 to 1.4.5.
OUTCOME : Notes on the call stack and stack frames
|
Command history
If you are used to using the CMD prompt or Linux Bash, you will be familiar with the use of the up arrow (↑) and down arrow (↓) to scroll through the 'command history'. Command history stores all recently used commands using a stack. Using suitable key-bindings, you can peek at the previous command on the stack, recalling it ready for editing and execution.
If you are using IDLE, however, the key combinations for command history are slightly different to normal ...
- ALT + P : Previous command
- ALT + N : Next command
Let's fix that, shall we?
Task 1.3 Changing the IDLE keybindings
It might be quicker for you to change the keybindings in Python to enable up and down arrow movement through the command history so that it works like most other shell environments.
- If it is not already open, open up IDLE
- Choose 'Options > Configure IDLE'
- Choose the 'Keys' tab
- Scroll down the 'Custom Key Bindings' section until you see 'history-next', select it and click 'Get New Keys for Selection'
- Scroll down the list of keys until you find 'Down Arrow'. Select and press 'OK'
- Give your custom key bindings a suitable name (like 'IDLE Custom Keys') and click 'OK'
- Repeat for 'history-previous' but this time choose 'Up Arrow' from the keys list.
- Click 'OK' on the Settings window
- Enjoy your new, standard key bindings!
OUTCOME : Better mapped key-bindings for Python IDLE. Demonstrate what you have done to your teacher.
|
Reversing the order of a list
One kind of funky use for a stack is to reverse the order of a list of values. Consider the following diagram which shows two different views of the same railway siding.
Task 1.4 Reverse those trains
First, download the script staticStack.py, save this to your user space. Create a new Python script and import this library. Create a single stack object and use it to implement your solution.
OUTCOME : Python script plus screenshot evidence of the script to reverse the order of a list using a stack.
|
Basic queue operations
A queue is another Abstract Data Structure that is related to stacks except that a queue is a First In First Out (FIFO) data structure. The implementations of queues here are static / fixed size.
All queues have similar operations ...
- ENQUEUE - Add an item to the back of the queue
- DEQUEUE - Remove an element from the front of the queue
- PEEK - Returns the first element in the queue without removing it
There are three main implementations of queues which we will look at in this section ...
- Linear queue or shuffle queue
- Circular queue
- Priority queue
Linear queue or Shuffle queue
In a linear, fixed length queue, items are enqueued at the back and dequeued from the front. In order to maintain efficient use of space in the queue, after any dequeue operation, all elements will need to be 'shuffled' up to the front of the queue (there is little point discussing a situation where this does not happen). In this case, there is no need for a FRONT pointer as the first element will always be at the front (after a suitable shuffle, of course).
To monitor the size of the queue however, a REAR pointer is always needed.
Animation showing structure of a shuffle queue
Task 2.1 Linear queue / shuffle queue implementation
linearQueue.py
- Download the Python file, linearQueue.py from the lesson resources and save it in your user area.
- Create a blank word processed document with a suitable header
and footer and use screenshots and written explanation to document what
you have done and what you have learnt. Make sure that the screenshots
are clear.
- Inspect the script - you should find all the operations stated above implemented. Print the script out for your notebooks. Use Notepad++ for this because it will print it in colour and it looks nice! Annotate it to describe what each part of the script does.
- Running the script which will create a class in memory called
linearQueue(max) with which you can create a queue object. Try investigating the behaviour of this queue object by typing the following instructions at the prompt, pressing the ENTER key after each one.
>>> myQueue = linearQueue(10)
>>> print(myQueue)
>>> myQueue.enqueue('Mark')
>>> myQueue.enqueue('Alan')
>>> myQueue.enqueue('Beatrice')
>>> myQueue.enqueue('Leanne')
>>> print(myQueue)
>>> myQueue.dequeue()
>>> print(myQueue)
- Most of the queue operations are trivial - the only one which is a little more complicated is the
linearQueue.shuffle() method. Use suitable flowcharting software to draw a flowchart representation for the algorithm which is implemented in this method.
- Now print out your word processed document for your notes.
OUTCOME : Evidence that you have investigated and analysed a linear queue implementation.
|
Circular queue
To overcome the need to continually shuffle the contents of a linear list up to the front of the queue, a circular queue links the back of the available space in the queue to the front, so enqueued items may eventually enter the queue at the lower range of the array indices.
Animation showing structure of a circular queue
Clearly, this behaviour necessitates the use of both a
FRONT and a
REAR pointer. In practice of course, arrays are
not circular - this is merely a logical structure for the queue. The algorithm maintains this structure by rolling round the pointers as necessary during enqueue and dequeue operations using modulus (%) arithmetic. However, it is not possible to use the relationship between the
FRONT and the
REAR pointers to determine whether the list is full or empty (
can you think why?) therefore, we need another variable called
SIZE which keeps track of the size of the queue so we can tell if it's empty or full.
Task 2.2 Circular queue implementation
Python IDLE
Circular Queue Hints.docx
e
I think I've worked hard enough - now it's your turn. Using the existing linearQueue class definition to help you, create your own class for a circularQueue. Download Circular Queue Hints to help you! Print out both your attempt at a script and evidence that you have tested it.
When you have successfully attempted this (or tried your hardest but failed) I will provide you with a solution. Then, use a highlighter pen to identify the changes you have made to the linear queue script. Nice.
OUTCOME : Your own Python implementation (hopefully) for a circular queue.
|
Priority Queue
In a priority queue, the data items have a predefined
priority and must be dequeued in priority order. There are
various ways of accomplishing this but by far the simplest way is to search through the queue for the first highest priority item and dequeue that. Maintaining the queue structure then requires that the head of the queue is swapped with this dequeued item (as long as the queue is at least two items in length).
Animation showing structure of a priority queue
Task 2.3 Priority queue implementation
Python IDLE
Guess what? That's right - I'd like you to have a go at the implementing a priority queue as well. The solution to this is not a million miles from a standard circular queue. However, the dequeue operation requires a quick priority search and a swap (as long as there is more than 1 item in your queue).
You will require a little more information in each node than is provided by a simple array of values and therefore you will need to implement a 'node' class with 'data' and 'priority' fields.
Just to annoy you, there is no help document for this one, you are on your own!
Again, when you have successfully implemented this (or tried your hardest and failed), I will provide you with a solution. Seriously, if you can get this working (and prove it works), you are a legend!
OUTCOME : Your own Python implementation (hopefully) of a priority queue and legendary status.
|
Technically, *some* would say that this implementation of a priority queue is fatally flawed, since, through the swapping aspect, the
original in priority FIFO ordering is likely to be altered. However, a famous wiki says ...
... and therefore, since this is the simplest way of implementing a priority queue, I'm going to stick with this one. However,
as we have seen, there are actually many other ways of doing this, including ...
- After the dequeue operation, shuffle the front portion of the queue up one position (if necessary, which will still require a circular queue);
- After the dequeue operation, shuffle the back portion of the queue down one position (if necessary, which will not require a circular queue);
- Maintaining a priority sorted queue by inserting any enqueued nodes at the back of the existing similar priority items which are already in the queue;
- Creating a separate circular queue within the data structure for *each* priority level and maintain each individual queue separately.
- Use of balanced binary trees and heaps.
If you fancy implementing any of these methods (or just chatting about them for two or three hours), feel free :)
If you want more, download the worksheet
Characteristics of Stacks and Queues from the lesson resources and have a go. Remember that you do not deserve an outstanding attitude to learning if you don't do some of the extension activities - you have been warned!
What's next?
Before you hand your book in for checking, make sure you have completed all the work required and that your book is tidy and organised. Your book will be checked to make sure it is complete and you will be given a spicy grade for effort.
|
END OF TOPIC ASSESSMENT
