Data structure

data/stacks.docx

JUBAIL UNIVERSITY COLLEGE

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

SEMESTER 382

GROUP ASSIGNMENT (8%)

TO BE FILLED BY THE CONCERNED DEPARTMENT

Introduction

PROJECT DESCRIPTION

The students need to form groups consisting of 3 members. Each group has to develop TWO (2) Java applications by applying any suitable Data Structures (Linked List, Stack and Queue) studied in this course. The applications can be developed for handling the student list, employee list, shopping list, book list, seminar reservation, hall reservation, air-ticket reservation, hotel reservation, stock inventory, sales invoice or any other. The nodes of each data structure should include at least FOUR (4) fields/attributes appropriate to the applications. Each application should include at least FOUR (4) basic operations performed on the data structures (such as insert, update, delete, search or print). And, include at least ONE (1) new operation/method in each application. (For example, sorting the elements (in ascending/descending order) in the linked list, retrieving/modifying the set of nodes in the list that satisfies the given condition, deleting the set of nodes from the list that satisfies the given condition, adding/removing the elements as per priority in the queue, swapping the elements in the Stack etc.)

Application of stacks and queues.

 The data structures most are used to such as Arrays, linked lists, trees, etc. are best for data that represents real objects. Stacks and Queues are instead used to complete a task and are soon after discarded.

A major difference is that stacks and queues allow only a single item to be added or removed at a time. Stacks then provide access to the last item in, while queues provide access to the first item in. The video and code below will cover everything.

Program listing

Main Class- The Stacks

// Arrays, linked lists, trees, etc. are best for

// data that represents real objects.

// Stacks & Queues are instead used to complete a

// task and are soon after discarded.

// Stacks & Queues

// 1. Allow only a single item to be added or removed at a time

// 2. Stacks allow access to the last item inserted (LIFO)

// 3. Queues allow access to the first item inserted (FIFO)

import java.util.Arrays;

public class TheStack {

private String[] stackArray;

private int stackSize;

// Sets stack as empty

private int topOfStack = -1;

TheStack(int size){

stackSize = size;

stackArray = new String[size];

// Assigns the value of -1 to every value in the array

// so I control what gets printed to screen

Arrays.fill(stackArray, "-1");

}

public void push(String input){

if(topOfStack+1 < stackSize){

topOfStack++;

stackArray[topOfStack] = input;

} else System.out.println("Sorry But the Stack is Full");

displayTheStack();

System.out.println("PUSH " + input + " Was Added to the Stack\n");

}

public String pop(){

if(topOfStack >= 0){

displayTheStack();

System.out.println("POP " + stackArray[topOfStack] + " Was Removed From the Stack\n");

// Just like in memory an item isn't deleted, but instead is just not available

stackArray[topOfStack] = "-1"; // Assigns -1 so the value won't appear

return stackArray[topOfStack--];

} else {

displayTheStack();

System.out.println("Sorry But the Stack is Empty");

return "-1";

}

}

public String peek(){

displayTheStack();

System.out.println("PEEK " + stackArray[topOfStack] + " Is at the Top of the Stack\n");

return stackArray[topOfStack];

}

public void pushMany(String multipleValues){

String[] tempString = multipleValues.split(" ");

for(int i = 0; i < tempString.length; i++){

push(tempString[i]);

}

}

public void popAll(){

for(int i = topOfStack; i >= 0; i--){

pop();

}

}

public void popDisplayAll(){

String theReverse = "";

for(int i = topOfStack; i >= 0; i--){

theReverse += stackArray[i];

}

System.out.println("The Reverse: " + theReverse);

popAll();

}

public void displayTheStack(){

for(int n = 0; n < 61; n++)System.out.print("-");

System.out.println();

for(int n = 0; n < stackSize; n++){

System.out.format("| %2s "+ " ", n);

}

System.out.println("|");

for(int n = 0; n < 61; n++)System.out.print("-");

System.out.println();

for(int n = 0; n < stackSize; n++){

if(stackArray[n].equals("-1")) System.out.print("| ");

else System.out.print(String.format("| %2s "+ " ", stackArray[n]));

}

System.out.println("|");

for(int n = 0; n < 61; n++)System.out.print("-");

System.out.println();

}

public static void main(String[] args){

TheStack theStack = new TheStack(10);

theStack.push("10");

theStack.push("17");

theStack.push("13");

// Look at the top value on the stack

theStack.peek();

// Remove values from the stack (LIFO)

theStack.pop();

theStack.pop();

theStack.pop();

// Add many to the stack

theStack.pushMany("R E D R U M");

// Remove all from the stack

// theStack.popAll();

// Remove all from the stack and print them

theStack.popDisplayAll();

theStack.displayTheStack();

}

}

The Queue

import java.util.Arrays;

public class TheQueue {

private String[] queueArray;

private int queueSize;

// Sets stack as empty

private int front, numberOfItems, rear = 0;

TheQueue(int size){

queueSize = size;

queueArray = new String[size];

// Assigns the value of -1 to every value in the array

// so I control what gets printed to screen

Arrays.fill(queueArray, "-1");

}

public void insert(String input){

if(numberOfItems + 1 <= queueSize){

queueArray[rear] = input;

rear++;

numberOfItems++;

System.out.println("INSERT " + input + " Was Added to the Stack\n");

} else {

System.out.println("Sorry But the Queue is Full");

}

}

// This priority insert will add items in order from high to low

public void priorityInsert(String input){

int i;

if(numberOfItems == 0){

insert(input);

} else {

for(i = numberOfItems-1; i >= 0; i--){

if(Integer.parseInt(input) > Integer.parseInt(queueArray[i])){

queueArray[i+1] = queueArray[i];

} else break; // Done shifting items in queue

}

queueArray[i+1] = input;

rear++;

numberOfItems++;

}

}

public void remove(){

if(numberOfItems > 0){

System.out.println("REMOVE " + queueArray[front] + " Was Removed From the Queue\n");

// Just like in memory an item isn't deleted, but instead is just not available

queueArray[front] = "-1";

front++;

numberOfItems--;

} else {

System.out.println("Sorry But the Queue is Empty");

}

}

public void peek(){

System.out.println("The First Element is " + queueArray[front]);

}

public void displayTheQueue(){

for(int n = 0; n < 61; n++)System.out.print("-");

System.out.println();

for(int n = 0; n < queueSize; n++){

System.out.format("| %2s "+ " ", n);

}

System.out.println("|");

for(int n = 0; n < 61; n++)System.out.print("-");

System.out.println();

for(int n = 0; n < queueSize; n++){

if(queueArray[n].equals("-1")) System.out.print("| ");

else System.out.print(String.format("| %2s "+ " ", queueArray[n]));

}

System.out.println("|");

for(int n = 0; n < 61; n++)System.out.print("-");

System.out.println();

// Number of spaces to put before the F

int spacesBeforeFront = 3*(2*(front+1)-1);

for(int k = 1; k < spacesBeforeFront; k++)System.out.print(" ");

System.out.print("F");

// Number of spaces to put before the R

int spacesBeforeRear = (2*(3*rear)-1) - (spacesBeforeFront);

for(int l = 0; l < spacesBeforeRear; l++)System.out.print(" ");

System.out.print("R");

System.out.println("\n");

}

public static void main(String[] args){

TheQueue theQueue = new TheQueue(10);

theQueue.priorityInsert("16");

theQueue.priorityInsert("25");

theQueue.priorityInsert("10");

/*

theQueue.insert("10");

theQueue.displayTheQueue();

theQueue.insert("15");

theQueue.displayTheQueue();

theQueue.insert("25");

theQueue.displayTheQueue();

theQueue.insert("25");

theQueue.displayTheQueue();

theQueue.insert("25");

*/

theQueue.displayTheQueue();

theQueue.remove();

theQueue.displayTheQueue();

theQueue.remove();

theQueue.displayTheQueue();

theQueue.peek();

}

}

Sample Output

References

Treehouse.com

Eclipseide.org

www.quora.com

1

1

1

public synchronized class Link {
    public String bookName;
    public int booksSold;
    public Link next;
    public void Link(String, int);
    public void display();
    public String toString();
    public static void main(String[]);
}

synchronized class LinkList {
    public Link firstLink;
    void LinkList();
    public boolean isEmpty();
    public void insertFirstLink(String, int);
    public Link removeFirst();
    public void display();
    public Link find(String);
    public Link removeLink(String);
}

public synchronized class TheStack {
    private String[] stackArray;
    private int stackSize;
    private int topOfStack;
    void TheStack(int);
    public void push(String);
    public String pop();
    public String peek();
    public void pushMany(String);
    public void popAll();
    public void popDisplayAll();
    public void displayTheStack();
    public static void main(String[]);
}

package Stacks;
abstract interface package-info {
}

package Stacks;
public synchronized class TheQueue {
    private String[] queueArray;
    private int queueSize;
    private int front;
    private int numberOfItems;
    private int rear;
    void TheQueue(int);
    public void insert(String);
    public void priorityInsert(String);
    public void remove();
    public void peek();
    public void displayTheQueue();
    public static void main(String[]);
}

public synchronized class Link {
    public String bookName;
    public int millionsSold;
    public Link next;
    public void Link(String, int);
    public void display();
    public String toString();
    public static void main(String[]);
}

synchronized class LinkList {
    public Link firstLink;
    void LinkList();
    public boolean isEmpty();
    public void insertFirstLink(String, int);
    public Link removeFirst();
    public void display();
    public Link find(String);
    public Link removeLink(String);
}