Linear Data Structures & Algorithms - ASSIGNMENT 1 - DATA STRUCTURES - ADT MyStack  - Solved

The stack is a fundamental data-structure used extensively in algorithm design and program implementation. At an abstract level it can be described very simply, as it only allows for the addition (pushing) of new elements and removal (popping) of existing elements from the top of the stack. This description can be abbreviated to LIFO, which stands for Last-In-First-Out.

 

 

   

 

Problem Specification:

In this assignment we are going to specify the ADT MyStack with the following operations:  

▪     createEmpty(): It creates a new MyStack with no elements and initialises each of the attributes. 

         ▪     isEmpty(): It returns whether the stack is empty or not.  

▪ push(int element): It places an integer item onto the top of the stack (if there is space for it). If there is no space, it prints on the screen an error message informing that the stack is full.  

▪ pop(): It removes the top integer from the stack (if the stack is non-empty) and returns that item. If the stack is empty, it prints on the screen an error message informing that the stack is empty and returns -1. 

▪ print(): It prints the items that are in the stack in a single line (the item on the top of the stack should appear in the left-most position). For the example of the figure above, the printed value on the screen would be: 6 9 9 7 1 12. If the stack is empty, it prints an error message to the screen confirming that the stack is empty.  (Week 4)

A MyStack of int elements: Static Implementation.                                                                

 

BACKGROUND. 

The unit on Canvas contains the following files:

-          MyMain.java:  This class tests the functionality of the stack’s static implementation. -       MyStack.java: This interface specifies the ADT MyStack containing int elements. 

-          MyStaticStack.java: This class implements all operations of MyStack, using a static based implementation based on the following attributes: 

                        ▪     private int items[];  

                        ▪     private int numItems; 

                        ▪     private int maxItems;   

 

EXERCISE. 

Implement the class MyStaticStack.java. IMPORTANT: only modify this .java file. Look for the comments: //TO-COMPLETE  

                 


(Week 5)

A MyStack of int elements: Dynamic Implementation. Here there is no limit on the size of the stack.       

 

BACKGROUND. 

The unit on Canvas contains the following files:

-          MyMain.java: This class tests the functionality of the stack’s dynamic implementation. 

-          MyNode.java: This class models the concept of a single linked node containing an int info and a pointer to its next node next.   

-          MyStack.java: This interface specifies the ADT MyStack containing int elements. (Same file used last week in part 1) 

-          MyDynamicStack.java: This class implements all operations of MyStack, using a dynamic based implementation based on the following attributes: 

                        ▪    private MyNode head;    

 

EXERCISE. 

Implement the class MyDynamicStack.java. IMPORTANT: only modify this .java file. Look for the comments: //TO-COMPLETE

                 


(Week 6)

A MyStack of generic type <T> elements: Dynamic Double-Linked Implementation.

             

 

BACKGROUND. 

In this last hint, we extend the ADT MyStack with the capability of adding and removing elements from both front and back. That is why, we do not refer to the top in this hint, but to the head and tail. The head represents the element that is on top of the stack and the tail the element that is on the bottom of the stack. In the following figure, we can see the image where the red color represents the head and the blue color represents the tail. The new extended ADT MyStack contains the following operations:  

 

         ▪     createEmpty(): It creates a new MyStack with no elements.  

         ▪     isEmpty(): It returns whether the stack is empty or not.  

▪ first(): If the stack is non-empty, then it returns its first element (coloured in red in Figure 1). Otherwise, it returns an error message.   

▪ addByFirst(): Given a new item (coloured in red above in Figure 1), it adds it to the front/head of the stack.  

▪ removeByFirst(): If the stack is non-empty, then it removes its first element (coloured in red above in Figure 1). Otherwise, it returns an error message.   

▪ last(): If the stack is non-empty, then it returns its last element (coloured in blue in Figure 1). Otherwise, it returns an error message.   

▪ addByLast(): Given a new item (coloured in blue above in Figure 1), it adds it to the back/tail of the stack.  

▪     removeByLast(): If the stack is non-empty, then it removes its last element (coloured in blue below in Figure 1). Otherwise, it returns an error message. 

 

 

 

4 
 
 
 
 

8 
 
 
  4 
  5
  2
  1
  7
  8
 
 

4 
 
 
 
 

8 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
                                                                           Figure 1 - Double Linked List Example 

                 

The folder /src contains the following files:

-          MyMain.java: This class tests the functionality of the stack’s dynamic implementation. 

-          MyDoubleLinkedNode.java: This class models the concept of a double linked node containing an element of type <T> info, a pointer to its next node left and a pointer to its previous node right.    

-          MyStack.java: This interface specifies the ADT MyStack containing elements of type <T>. 

-          MyDoubleDynamicStack.java: This class implements all operations of MyStack, using a dynamic based implementation based on the following attributes: 

                        ▪    private MyDoubleLinkedNode<T> head;  

                                                     head                                                                      tail 

▪ private MyDoubleLinkedNode<T> tail;    

 

 

 

 

EXERCISE. 

Implement the class MyDoubleDynamicStack.java. IMPORTANT: only modify this .java file. Look for the comments: //TO-COMPLETE