CS42 : Stacks and queues, very British (apart from the stacks) ...

 
Stacks and queues exist in all walks of life. We see them everywhere. They are also very useful in computer science as we are all about to learn.

We are learning ...
  • About stacks
  • About queues
So that we can ...
  • Understand the structure and representation of stacks and queues
  • Perform operations on stacks
    - Push
    - Pop
    - Peek or top
    - Test for empty stack
    - Test for full stack
  • Understand how the stack frame is used to store return addresses, parameters and local variable values
  • Perform operations on queues (shuffle, circular, priority)
    - Add an item
    - Remove an item
    - Test for an empty queue
    - Test for a full queue
    - Peek at the next item

Activity 1 Stacks (220)

Basic stack operations

Stacks are Abstract Data Structures (ADTs) which exhibit Last IFirst 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.

https://drive.google.com/file/d/0B83yXMOilskad0sxUU1QeGFvdTg/view?usp=drive_web
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.
  1. If it is not already open, open up IDLE
  2. Choose 'Options > Configure IDLE'
  3. Choose the 'Keys' tab
  4. Scroll down the 'Custom Key Bindings' section until you see 'history-next', select it and click 'Get New Keys for Selection'
  5. Scroll down the list of keys until you find 'Down Arrow'. Select and press 'OK'
  6. Give your custom key bindings a suitable name (like 'IDLE Custom Keys') and click 'OK'
  7. Repeat for 'history-previous' but this time choose 'Up Arrow' from the keys list.
  8. Click 'OK' on the Settings window
  9. 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.


Activity 2 Queues (170)

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 :)



Extension Activities 

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