Stacks

Stacks khaled.nagi@alexu.edu.eg 1
Stacks

 Stacks
 Array-based implementations
 Linked list implementations

Stacks khaled.nagi@alexu.edu.eg 2
Stacks

 A stack is a container of objects that are inserted and removed

according to the last-in,first-out (LIFO) principle.
 Objects can be inserted at any time, but only the last (i.e., the most
recently inserted) object can be removed.
 Inserting an item is known as “pushing” on to the stack.

Stacks khaled.nagi@alexu.edu.eg 3
Stacks (ǁ)

 Popping” off the stack is synonymous with removing an item.

 The name "stack" is derived from a stack of plates in a spring-loaded,
cafeteria plate dispenser.
 When we need a new plate from the dispenser, we "pop" the top plate
off the stack, and
 When we add a plate, we "push" it down on the stack to become the
new top plate.

Stacks khaled.nagi@alexu.edu.eg 4
Stacks

 Stacks are a fundamental data structure used in many Applications:

 Internet Web browsers store the addresses of recently visited sites on a
stack.
 Each time a user visits a new site, that site's address is "pushed“ onto the stack
of addresses.
 The browser then allows the user to "pop" back to previously visited sites using
the "back" button.
 Text editors usually provide an "undo" mechanism that cancels recent
editing operation. This undo operation can be accomplished by keeping text
changes in a stack.

Stacks khaled.nagi@alexu.edu.eg 5
The Stack Abstract Data Type

 A stack is an abstract data type (ADT) that supports two main methods:
 Push(o): Inserts object o onto top of stack.
 Input: Object; Output: none
 Pop(): Removes the top object from the stack and returns it; if stack is empty
an error occurs.
 Input: none; Output: Object

Stacks khaled.nagi@alexu.edu.eg 6
The Stack Abstract Data Type

 The following support methods should also be defined:

Size(): Returns the number of objects in stack

Input: none; Output:integer
Is Empty(): Return a boolean indicating if stack is empty.
Input: none; Output: boolean
Top(): Return the top object of the stack, without
removing it. If the stack is empty, an error
occurs.
Input: none; Output: Object

Stacks khaled.nagi@alexu.edu.eg 7
Example Stack Operations

 Series of stack operations and their effects on an initially empty stack S

of integers
 Two types of errors are possible with stack structure :
 Stack underflow: a pop operation was applied to an empty stack
 Stack overflow: a push operation was applied to a "full" stack

Stacks khaled.nagi@alexu.edu.eg 8
Abstract Classes

 An abstract class is a class that cannot be instantiated.

 It generally corresponds to a generic entity with details that need to be
"filled in" by a subclass.
 An abstract method is a method that does not contain an implementation
(i.e., an empty method).
 An abstract class can intermix abstract and non abstract method
definitions.
 A class with abstract methods must be modified as abstract. Modifying
an abstract method as final or static would be a contradiction

Stacks khaled.nagi@alexu.edu.eg 9
Code

Stacks khaled.nagi@alexu.edu.eg 10
Interfaces

 Interfaces may contain only

 Constants
 Abstract methods
 Other interfaces
 Interfaces may extend other interfaces.
 As an expression of pure design, interfaces are useful constructs in the
design of ADTs.
 The interface specifies the methods which must be defined in a class
that implements the interface, but does not specify the implementation of
those methods.
 All methods in an interface are by default declared to be public and
abstract.
 Constants in an interface are by default public, static, and final

Stacks khaled.nagi@alexu.edu.eg 11
Code

Stacks khaled.nagi@alexu.edu.eg 12
 A formal parameter type that is an interface can accept as an actual
parameter any class or subclass that implements the interface.
 /** Some operations on Measurable's. */
public class MeasureUtil {
public static double maxArea(Measurable m1, Measurable m2) {
return(Math.max(m1.getArea(), m2.getArea()));
}
public static double totalArea(Measurable[] mArray) {
double total = 0;
for(int i=0; i<mArray.length; i++)
total = total + mArray[i].getArea();
return total;
}
}

Stacks khaled.nagi@alexu.edu.eg 13
(ǀ)

/** Test of MeasureUtil. Note that we could change the actual classes of
elements in the measurable array (as long as they implemented
Measurable) without changing
The rest of the code.
*/
public class MeasureTest {
public static void main(String[] args) {
Measurable[] measurables = {
new Rectangle(0, 0, 5.0, 10.0), //also implements measurable
new Rectangle(0, 0, 4.0, 9.0),
new Circle(0, 0, 4.0),
new Circle(0, 0, 5.0)
};

Stacks khaled.nagi@alexu.edu.eg 14
(ǁ)

System.out.print("Areas:");
for(int i=0; i<measurable.length; i++)
System.out.print(" " + measurable[i].getArea());
System.out.println();
System.out.println
("Larger of 1st, 3rd: " +
MeasureUtil.maxArea(measurables[0], measurable[2]) + "\nTotal area: " +
MeasureUtil.totalArea(measurables));
}
}

Stacks khaled.nagi@alexu.edu.eg 15
A Stack Interface in Java

public interface Stack {

// accessor methods
public int size(); // return the number of elements stored in the stack
public boolean isEmpty(); // test whether the stack is empty
public Object top() // return the top element
Throws StackEmptyException; // thrown if called on an empty stack
// update methods
public void push (Object element); // insert an element onto the stack
Throws StackFullException; // thrown if overflow
public Object pop() // return and remove the top element of the stack
Throws StackEmptyException; // thrown if called on an empty stack
}

Stacks khaled.nagi@alexu.edu.eg 16
A Stack Interface in Java

 While the stack data structure is a “built-in” class of the JDK java.util
package,
 It is possible and sometimes preferable to define your own interface
 It is instructive to learn how to design and implement a stack "from scratch."

Stacks khaled.nagi@alexu.edu.eg 17
An Array-Based Stack

 Create a stack using an array by specifying a maximum size N for our

stack, e.g., N = 1000.
 The stack consists of an
 N-element array S and
 An integer variable t, the index of the top element in array S.

 Array indices start at 0, so we initialize t to –1.

Stacks khaled.nagi@alexu.edu.eg 18
Pseudo Code

Stacks khaled.nagi@alexu.edu.eg 19
An Array-Based Stack

 Each of the above methods runs in constant time (O(1)).

 The array implementation is simple and efficient.
 There is an upper bound N on the size of the array-based stack.
 This arbitrary value N may be too small for a given application or
 It may be too large and a waste of memory

Stacks khaled.nagi@alexu.edu.eg 20
Array-Based Stack: a Java Implementation

 Public class ArrayStack implements Stack {

Stacks khaled.nagi@alexu.edu.eg 21
Array-Based Stack: a Java Implementation

Stacks khaled.nagi@alexu.edu.eg 22
Array-Based Stack: a Java Implementation

Public Object pop() // Pop off the stack element

Throws StackEmptyException {
Object elem;
if (isEmpty())
throw new StackEmptyException("Stack is
Empty.");
Elem = S[top];
S[top--] = null; //Dereference S[top] and
decrement top
Return elem;

Stacks khaled.nagi@alexu.edu.eg 23
Casting with a Generic Stack

 We can store generic objects in ArrayStack (and other datastructure

classes) because every Java class is a subclass of the Object class.
 When retrieving from an ADT, however, it is often necessary to cast the
object back to its original type.
 A Java code example:
 // reverse an array a into an array b
 Public static Integer[] reverse(Integer[] a)
{
ArrayStack S = new ArrayStack(a.length);
Integer[] b = new Integer[a.length];
for(int i = 0; i < a.length; i++)
S.push(a[i]);
for(int i = 0; i < a.length; i++)
b[i] = (Integer)(S.pop());
Return b;
}

Stacks khaled.nagi@alexu.edu.eg 24
Stacks in the Java Virtual Machine

 Each process running in a Java program has its own Java method stack.
 Each time a method is called, it is pushed onto the stack.
 A frame in the stack stores information relevant to running and
suspended methods (i.e., local variables, actual parameters, return
values, etc.)
 The choice of a stack for this operation allows Java to do several useful
things:
 Perform recursive method calls. Conceptually, as regards the Java method
stack, there is no difference between a recursive call and a “regular” call.
 Print stack traces so that users can locate an error.

Stacks khaled.nagi@alexu.edu.eg 25
Java Method Stack

Stacks khaled.nagi@alexu.edu.eg 26
A Linked List-based Stack

 The stack is represented by a collection of nodes, each node x, has two

fields:
 Data field
 Link field
 The link fields of a node points to the previous node in the stack
 The link field of last node points to null
 Stack pointer, a pointer Top that points to the top node of the stack.
 Top = null when stack is empty
 A flag underflow to indicate whether
 pop operations are successful.
 No overflow flag is necessary

Stacks khaled.nagi@alexu.edu.eg 27
Should the top of the stack be at the head or at
the tail of the list?
 Insert and delete elements at the head O(1)
 Thus, it is more efficient to have the top of the stack at the head of the
list.
 In order to perform operation size in constant time, we keep track of the
current number of elements in an instance variable.

Stacks khaled.nagi@alexu.edu.eg 28
…

Stacks khaled.nagi@alexu.edu.eg 29
A Stack Interface in Java

 public interface Stack {

// accessor methods
public int size(); // return the number of elements
stored in the stack
public boolean isEmpty(); // test whether the stack is empty
public Object top() // return the top element
throws StackEmptyException; // thrown if called on an empty
stack

 // update methods
public void push (Object element); // insert an element onto the stack
throws StackFullException; // thrown if overflow
public Object pop() // return and remove the top element of the stack
throws StackEmptyException; // thrown if called on an empty stack
}

Stacks khaled.nagi@alexu.edu.eg 30
Java Implementation of a Stack NodeStack Class

Stacks khaled.nagi@alexu.edu.eg 31
Java Implementation of a Stack NodeStack Class

public Object top() throws StackEmptyException {

If (isEmpty()) throw new StackEmptyException(" Stack is empty.");
return top.getElement();
}

public Object pop() throws StackEmptyException {

if (isEmpty()) throw new StackEmptyException("Stack is empty.");
Object temp = top.getElement();
top = top.getNext(); // link-out the former top node
size--;
return temp;
}
}

Stacks khaled.nagi@alexu.edu.eg 32
Java Implementation of a Stack NodeStack Class

 All the methods of the Stack are executed in constant time.

 This implementation has a space requirement that is O(n) where n is the
current number of elements in the stack.
 Does not require that a new exception be created to handle size
overflow problems (only if Heap is full).

Stacks khaled.nagi@alexu.edu.eg 33
Reversing an Array Using a Stack – Non
Recursive Algorithm
 The basic idea: push all the elements of the array in order into a stack
and then fill the array back up again by popping the elements off of the
stack.
Public static Integer[] reverse(Integer[] a)
{
ArrayStack s = new ArrayStack(a.length);
Integer[] b = new Integer[a.length];
for(int i = 0; i < a.length; i++)
s.push(a[i]);
for(int i = 0; i < a.length; i++)
b[i] = (Integer)(s.pop());
return b;
}

Stacks khaled.nagi@alexu.edu.eg 34
Reversing an Array Using a Stack – Recursive
Algorithm (ǀ)
 The reversal of an array can be achieved by swapping the first and last
elements
 Then recursively reversing the remaining elements in the array.

Algorithm ReverseArray(A,i,j):
Input: An array A and nonnegative integer indices i and j
Output: The reversal of the elements in A starting at index i and ending at j
if i < j then
Swap A[i] and A[j]
ReverseArray(A, i+1,j-1)
return

Stacks khaled.nagi@alexu.edu.eg 35
Reversing an Array Using a Stack – Recursive
Algorithm (ǁ)
 Two base cases, namely, when i = j and when i > j:
 if n is odd, we will reach the i = j case,
 if n is even, we will reach the i > j case.
 In either case, we terminate the algorithm, since a sequence with zero
elements or one element is trivially equal to its reversal

Stacks khaled.nagi@alexu.edu.eg 36
Java Method Stack

Stacks khaled.nagi@alexu.edu.eg 37
Applications Using Stacks

 Two related applications of stacks

 Matching parentheses and grouping symbols in Arithmetic expressions.
 Matching Tags in an HTML document

Stacks khaled.nagi@alexu.edu.eg 38
Matching Parentheses

 Arithmetic expressions can contain various pairs of grouping symbols,

such as
 Parentheses: "(" and ")“
 Braces: "{" and "}“
 Brackets: "[" and "]“
 Floor function symbols: "└" and "┘“
 Ceiling function symbols: "┌" and "┐"
 Each opening symbol must match with its corresponding closing symbol.
[(5+x)-(y + z)]

Stacks khaled.nagi@alexu.edu.eg 39
An Algorithm for Parentheses Matching

 Write an algorithm that

 Tests that left and right symbols match up and also
 That the left and right symbols are both of the same type.
 Basic idea: use the Stack to perform the matching in an arithmetic
expression with a single left-to-right scan.
 • Suppose we are given a sequence X =x0 x1 x2 … xn-1, where each xi is
a token that can be a grouping symbol, a variable name, an arithmetic
operator, or a number.
 Process the tokens in X in order.
 For each opening symbol, push that symbol onto S
 For each closing symbol, pop the top symbol from the stack S (assuming S
is not empty)
 Check that these two symbols are of the same type.
 If the stack is empty after we have processed the whole sequence, then the
symbols in X match.

Stacks khaled.nagi@alexu.edu.eg 40
(ǀ)

 Algorithm ParenMatch(X,n):
 Input: An array X of n tokens, each of which is either a grouping symbol,
a variable, an arithmetic operator, or a number
 Output: true if and only if all the grouping symbols in X match
 Let S be an empty stack
 for i ← 0 to n – 1 {
 if X[i] is an opening grouping symbol then
 s.push(X[i])
 else if X[i] is a closing grouping symbol then
 if s.isEmpty() then
 return false {nothing to match with}
 if s.pop() does not match the type of X[i] then
 return false {wrong type}
}

Stacks khaled.nagi@alexu.edu.eg 41
(ǁ)

 if s.isEmpty() then
 return true {every symbol matched}
 else
 return false {some symbols were never matched}
 Assuming that the push and pop operations are implemented to run in
constant time, this algorithm runs in O(n), that is linear time

Stacks khaled.nagi@alexu.edu.eg 42
Matching Tags in an HTML Document

 Application: validation of HTML documents.

 HTML is the standard format for hyperlinked documents on the Internet.
 In an HTML document, portions of text are delimited by HTML tags.
 A simple opening HTML tag has the form "<name>" and the
corresponding closing tag has the form "</name>“
 Commonly used HTML tags include
 Body: document body
 H1: section header
 Center: center justify
 P: paragraph
 Ol: numbered (ordered) list
 Li: list item.
 Ideally, an HTML document should have matching tags

Stacks khaled.nagi@alexu.edu.eg 43
Stacks khaled.nagi@alexu.edu.eg 44
 The same algorithm as for matching parentheses can be used to match
the tags in an HTML document.

Stacks khaled.nagi@alexu.edu.eg 45