Data Structures - I

“No Bonus” marks for this course anymore

CP
CS
20
4

O my Lord! Expand for me my chest [with

assurance] and ease for me my task and untie
the knot from my tongue that they may
understand my speech. (Quran 20 : 25-28)

1 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP
CS
20
4
STACKS
Implementation

2 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Implementation - Introduction
CS • Implementation
20 o Arrays
4 o Linked List
• Accessibility
o Top, LIFO
• Operations
o Push
o Pop
o isEmpty
o isFull
o top
3 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP
CS
20
4 Stack
Implementation
Arrays

4 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Array Implementation
CS
• Array • Array as STACK
20 o Push
o Insertion
4 • first, last, Anywhere • Only at Top
o Deletion o Pop
• Only from Top
• first, last, Anywhere
o isEmpty
o Traversal
• Top == -1
o Searching o isFull
o Sorting • Top == maxSize-1
o Merging o top or peek
• Return the value at Top
5 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Array - Class

CS public class StackArray { StackArray S;

20 private int[] stack; S = new StackArray (5);

private int top;

4 private int maxSize;
S

4
public StackArray(int size) { maxSize

maxSize = size; 3 5

stack = new int[maxSize]; stack 2

Top
top = -1;
1
} -1
0
}

6 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Array - Methods

CS • public boolean isEmpty()
20
4 • public boolean isFull()

• public void push(int j)

• public int pop()

• public int top()

7 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - isEmpty()

CS
20 public boolean isEmpty() {
if (top == -1)
4 public class StackArray {
private int[] stack; return true;
private int top; else
private int maxSize;
return false;
public StackArray(int size) { }
maxSize = size;
stack = new int[maxSize];
top = -1; public boolean isEmpty() {
}
return (top == -1);
} }

8 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - isEmpty()

CS
20 public boolean isEmpty() { S
return (top == -1);
4 } 4
maxSize

S 3 5

stack 2
4 Top
maxSize 1
-1
3 5 0
stack 2 6
Top
1 9
2
0 4 True

9 Dr. Jonathan (Yahya) Cazalas False Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - isFull()

CS
20 public boolean isFull() {
if (top == maxSize-1)
4 public class StackArray {
private int[] stack; return true;
private int top; else
private int maxSize;
return false;
public StackArray(int size) { }
maxSize = size;
stack = new int[maxSize];
top = -1; public boolean isFull() {
}
return (top == maxSize-1);
} }

10 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - isFull()

CS
20 public boolean isFull() { S

4 }
return (top == maxSize-1);
4 1
maxSize

S 3 0 5

stack 2 6
4 Top
maxSize 1 9
4
3 5 0 4
stack 2 6
Top
1 9
2
0 4 True

11 Dr. Jonathan (Yahya) Cazalas False Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - push(value)

CS
• Remember, we can only push if the stack is not full
20 o Meaning, if there is room to push
4 • So if the stack is full
o We print an error message.
• Or throw an Exception, showing the push could not be done
• If there is room
o We increment top to point to the next space in the stack
o Then we simply copy the value into this new top
position

12 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - push(value)

CS public void push(int value) {
20 if (isFull())
System.out.println(“Cannot PUSH; stack is full.”);
4 else{
top++;
stack[top] = value;
}
}

public void push(int value) {

if (isFull())
System.out.println(“Cannot PUSH; stack is full.”);
else
stack[++top] = value;
}
13 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - push(value)

CS public void push(int value) {
20 if (isFull())
System.out.println(“Cannot PUSH; stack is full.”);
4 else
stack[++top] = value;
}
S Value =8 S
4 4
maxSize maxSize
3 5 38 5
stack 2 6 stack 2 6
Top Top
1 9 1 9
2 3
0 4 0 4

14 Dr. Jonathan (Yahya) Cazalas False Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - pop()

CS
• Remember, we can only pop if the stack is not empty
20 o Meaning, there is at least one element to pop
4 • So if the stack is empty
o We print an error message
• Or throw an exception showing that we cannot pop
• If the stack has at least one element:
o We return the value at position top
o At the same time, we decrement top
o This makes the top “pointer” refer to the next item
down in the stack

15 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - pop()

CS public int pop() {
int value;
20 if (isEmpty())
4 else{
System.out.println(“Cannot POP; stack is empty.”);

value = stack[top];
top--;
return value;
}
}
public int pop() {
if (isEmpty())
System.out.println(“Cannot POP; stack is empty.”);
else
return stack[top--];
16 } Jonathan (Yahya) Cazalas
Dr. Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - pop()

CS public int pop() {
20 if (isEmpty())
System.out.println(“Cannot POP; stack is empty.”);
4 else
return stack[top--];
}
S Value =6 S
4 4
maxSize maxSize
3 5 3 5
stack 2 6 stack 26
Top Top
1 9 1 9
2 1
0 4 0 4

17 Dr. Jonathan (Yahya) Cazalas False Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - top()or peek()

CS
• The top method is very similar to pop
20
• Remember, we can only check for the top of the
4 stack if the stack is not empty
o Meaning, there is at least one element in the stack
• So if the stack is empty
o We print an error message
• If the stack has at least one element:
o We simply return the topmost element
o But we do NOT decrement
18 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - top()

CS public int pop() {
20 if (isEmpty())
System.out.println(“Cannot POP; stack is empty.”);
4 else
return stack[top--];
}

public int top() {

if (isEmpty())
System.out.println(“Cannot TOP; stack is empty.”);
else
return stack[top];
}

19 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - top()

CS public int top() {
20 if (isEmpty())
System.out.println(“Cannot TOP; stack is empty.”);
4 else
return stack[top];
}
S Value =6 S
4 4
maxSize maxSize
3 5 3 5
stack 2 6 stack 2 6
Top Top
1 9 1 9
2 2
0 4 0 4

20 Dr. Jonathan (Yahya) Cazalas False Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP
CS
20
4 Stack
Implementation
Linked List

21 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Linked List Implementation

CS
• Linked List • Linked List as STACK
20
o Insertion o Push
4 • first, last, Anywhere • Only at Top
o Deletion o Pop
• first, last, Anywhere • Only from Top
o Traversal o isEmpty
o Searching • Top == -1
o Merging o top or peek
• Return the value at
Top
22 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Linked List Implementation

CS
• Linked List as STACK
20 o We essentially use a standard linked list
4 o But we limit the functionality of a linked list
• Thus creating the behavior required of a stack
o Step 1:
• Choose the location of top!
• Where should we choose top to be? What is best?
o Top could be the “front” of the list OR the “end” of the list
o Which is better?
• If we choose top to be the end, we must traverse to the end
for every PUSH and every POP…a lot of traversing!
• BEST choice: we let top be the front of our list.
23 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Linked List Implementation

CS
• Linked List as STACK
20 o So we will create two classes (like Linked-Lists)
4 • StackNode.java (this is like the LLnode class)
• StackLL.java (this is like the LinkedList class)
o We use most of the SAME methods as used for the
Linked List class
o However, we RESTRICT the functionality
• Now, we cannot insert anywhere in the list
• We can only insert at the top (head)
• Now, we cannot delete from anywhere in the list
• We can only delete from the top (head)
24 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Linked List – Node Class

CS
public class StackNode {
20 private int data;
4 private StackNode next;

public StackNode(int i) {
data = i;
next = null;
}
public StackNode(int i, StackNode n) {
data = i;
next = n;
}
}
25 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan
 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Linked List – Stack LL Class

CS public class StackLL {
20 private StackNode Top;
4 public StackLL() {
Top = null;
}

// POP, PUSH, TOP and more...

}

26 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Linked List - Methods

CS • public boolean isEmpty()
20
4 • public void push(int j)

• public int pop()

• public int top()

27 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - isEmpty()

CS
20
4
public boolean isEmpty() {
return Top == null;
}

null
Top

28 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - push(value)

CS
public void push(int data) {
20
4 Top = new StackNode(data, Top);

}
Top
Value = 13 null
Top

10 null

13 50 8 10 null

29 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - pop()

CS public int pop( ) {
20 if (!isEmpty()) {
int temp = Top . data;
4 Top = Top . next;
return temp;
}
}

Top
Temp = 13

13 50 10 null

30 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP Stack Methods - top()

CS
20 public int top( ) {
if (!isEmpty()) {
4 return Top.data;
}
}

Top
Temp = 13

13 50 10 null

31 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan

 Data Structures - I
“No Bonus” marks for this course anymore

CP
CS
20
4

Allah (Alone) is Sufficient for us, and He is

the Best Disposer of affairs (for us).(Quran 3 :
173)

32 Dr. Jonathan (Yahya) Cazalas Dr. Muhammad Umair Ramzan