Problem Specification

You must write a program which takes a hard-coded array of unordered integers and sort them in two ways as they are being read from the unordered array. The first technique applies a method which uses two stacks to sort integers one-at-a-time, while the second applies a method which uses two queues to do so. The methods must return a sorted list of integers. The goals of the assignment are as follows:

1. Create several hard-coded unordered arrays of integers.
2. Implement two methods to sort the numbers one-at-a-time from the arrays and return them in lists: One using two stacks and the other using two queues.
3. Print each resulting list for each of the hard-coded cases.

Instead of using arrays for the underlying structures of stacks, you must use linked list representations that do not use built-in list classes. The program may be implemented in either Python or Java. The programs to be implemented in either language MUST be well-commented, i.e. use block comments for describing each method in a class and give some lines of comments to explain statements. Programs with very few comments (as in just commenting on one of two methods only) or no comments at all will be given a small grade penalty. For those implementing in Python, you must write a class Stack, a class Node, a class LinkedList, a class QueueSorter, and a class StackSorter. Note: when adding to its own module, the module containing the Queue class should be called something different from queue.py, since there is already a module with this name. You may call your module something else, such as my_queue.py.

class Stack(object):

# constructor for stack class

def __init__(self):

# initialize __linkedList attribute here

# push item onto stack

def push(self, x):

# code goes here

# pops item from top of stack

def pop(self):

# code goes here (should return item from top of stack or None if stack is empty)

# returns Boolean of whether stack is currently empty

def isEmpty(self):

# code goes here

# returns Boolean of whether stack is currently full

def isFull(self):

# code goes here

# clears the stack

def clear(self):

# code goes here

# looks at the top item of the stack and returns it, without removing it

def peek(self):

# code goes here

class Queue(object):

# constructor for Queue class

def __init__(self):

# initialize __linkedList attribute here

# adds item to rear of queue

def enqueue(self, x):

# code goes here

# removes item from front of queue

def dequeue(self):

# code goes here (should return item from end of queue or None if queue is empty)

# returns Boolean of whether queue is currently empty

def isEmpty(self):

# code goes here

# returns Boolean of whether queue is currently full

def isFull(self):

# code goes here

# clears the queue

def clear(self):

# code goes here

# looks at the item at the end of the queue without removing it

def poll(self):

# code goes here

class LinkedList(object):

# constructor for LinkedList class

def __init__(self):

# initialize the following 4 class attributes: __head, __tail, __capacity, and __size

# add item x to list at index i

def add(self, i, x):

# code goes here

# remove item at index i from the list

def remove(self, i):

# code goes here (should return item from list or None if item is not in the list)

class Node(object):

# constructor for Node class

def __init__(self):

# Initialize attributes __next, __prev, and __data here

class StackSorter(object):

# constructor for StackSorter class

def __init__(self):

# initialize attributes __sortedlist

# Sort a list of numbers using stacks

def sortArray(self, nums):

# code goes here

class QueueSorter(object):

# constructor for QueueSorter class

def __init__(self):

# initialize attributes __sortedlist

# Sort a list of numbers using queues

def sortArray(self, nums):

# code goes here