Introduction to Stacks

• What is a Stack?

• Stack implementation using array.

• Stack implementation using linked list.

• Applications of Stacks.

1
 What is a Stack?
• A stack is a data structure in which data is added and
removed at only one end called the top.

• To add (push) an item to the stack, it must be placed on

the top of the stack.

• To remove (pop) an item from the stack, it must be

removed from the top of the stack too.

• Thus, the last element that is pushed into the stack, is

the first element to be popped out of the stack.
i.e., A stack is a Last In First Out (LIFO) data structure

2
 An Example of a Stack

top 2
top 8 8
top 1 1 1
Push(8) Push(2)
7 7 7
2 2 2

pop
()

top 8
top 1
1
top 7 7 pop()
pop() 7
2 2
2

3
 Stack Implementations
• In our implementations, a stack is a container that extends the
AbstractContainer class and implements the Stack interface:

public interface Stack extends Container {

public abstract Object getTop();
public abstract void push(Object obj);
public abstract Object pop();
}

• We shall study two stack implementations:

– StackAsArray
• The underlying data structure is an array of Object
– StackAsLinkedList
• The underlying data structure is an object of MyLinkedList

4
 StackAsArray – Constructor
• In the StackAsArray implementation that follows, the top of the stack is
array[count – 1] and the bottom is array[0]:

• The constructor’s single parameter, size, specifies the maximum

number of items that can be stored in the stack.

• The variable array is initialized to be an array of length size.

public class StackAsArray extends AbstractContainer

implements Stack {

protected Object[] array;

public StackAsArray(int size){

array = new Object[size];
}

// …
5
 StackAsArray – purge() Method

• The purpose of the purge method is to remove all the

contents of a container.

• To empty the stack, the purge method simply assigns

the value null to the first count positions of the array.

public void purge(){

while(count > 0)
array[--count] = null;
}
)…(Complexity is O

6
 StackAsArray – push() Method
• push() method adds an element at the top the stack.

• It takes as argument an Object to be pushed.

• It first checks if there is room left in the stack. If no room

is left, it throws a ContainerFullException exception.
Otherwise, it puts the object into the array, and then
increments count variable by one.

public void push(Object object){

if (count == [Link])
throw new ContainerFullException();
else
array[count++] = object;
}
)…(Complexity is O
7
 StackAsArray – pop() Method
• The pop method removes an item from the stack and
returns that item.

• The pop method first checks if the stack is empty. If the

stack is empty, it throws a ContainerEmptyException.
Otherwise, it simply decreases count by one and returns
the item found at the top of the stack.
public Object pop(){
if(count == 0)
throw new ContainerEmptyException();
else {
Object result = array[--count];
array[count] = null;
return result;
}
} )…(Complexity is O
8
 StackAsArray – getTop() Method

• getTop() method is a stack accessor which returns the top

item in the stack without removing that item. If the stack is
empty, it throws a ContainerEmptyException. Otherwise,
it returns the top item found at index count-1.

public Object getTop(){

if(count == 0)
throw new ContainerEmptyException();
else
return array[count – 1];
}
)…(Complexity is O

9
 StackAsArray – iterator() Method

public Iterator iterator() {

return new Iterator() {
private int index = count-1;
public boolean hasNext() {
return index >=0;
}
public Object next () {
if(index < 0)
throw new NoSuchElementException();
else
return array[index--];
}
};
}

10
 StackAsLinkedList Implementation
In the singly-linked list implementation, the top of the stack is the first node in
the list.

public class StackAsLinkedList

extends AbstractContainer
implements Stack {

protected MyLinkedList list;

public StackAsLinkedList(){
list = new MyLinkedList();
}

public void purge(){

[Link]();
count = 0; )…(Complexity is O
}

// …
11
StackAsLinkedList Implementation (Cont’d)
public void push(Object obj){
[Link](obj); )…(Complexity is O
count++;
}

public Object pop(){

if(count == 0)
throw new ContainerEmptyException();
else{
Object obj = [Link]();
[Link]();
count--; )…(Complexity is O
return obj;
}
}
public Object getTop(){
if(count == 0)
throw new ContainerEmptyException();
else
return [Link](); )…(Complexity is O
} 12
StackAsLinkedList Implementation (Cont’d)
public Iterator iterator() {
return new Iterator() {
private [Link] position =
[Link]();

public boolean hasNext() {

return position != null;
}

public Object next() {

if(position == null)
throw new NoSuchElementException();
else {
Object obj = [Link]();
position = [Link]();
return obj;
}
}
};
}
13
 Applications of Stacks
• Some direct applications:
– Conversion of tail-recursive algorithms to iterative ones. [Note:
Tail recursion will be covered in a later lesson]
– Keeping track of method calls: Method activation records are
saved on the run-time stack
– Evaluation of arithmetic expressions by compilers [infix to
postfix conversion, infix to prefix conversion, evaluation of postfix
expressions]

• Some indirect applications

– Auxiliary data structure for some algorithms
• Example: Converting a decimal number to another base
– Component of other data structures
• Example: In this course we will use a stack to implement a
Tree iterator

14
 Application of Stacks - Evaluating Postfix Expressions

(5+9)*2+6*5
• An ordinary arithmetical expression like the above is called infix-
expression -- binary operators appear in between their operands.

• The order of operations evaluation is determined by the

precedence rules and parentheses.

• When an evaluation order is desired that is different from that

provided by the precedence, parentheses are used to override
precedence rules.

15
 Application of Stacks - Evaluating Postfix Expressions (Cont’d)

• Expressions can also be represented using postfix notation - where

an operator comes after its two operands or prefix notation – where
an operator comes before its two operands.

• The advantage of postfix and prefix notations is that the order of

operation evaluation is unique without the need for precedence rules
or parentheses.

Prefix (Polish) Notation Postfix (Reverse Polish) Notation Infix Notation

/ 16 2 16 2 / 16 / 2
* + 2 14 5 2 14 + 5 * (2 + 14)* 5
+ * 2 14 5 2 14 5 * + 2 + 14 * 5
* - 6 2 + 5 4 6 2 - 5 4 +* (6 – 2) * (5 + 4)

16
 Infix to Postfix conversion (manual)
• An Infix to Postfix manual conversion algorithm is:
1. Completely parenthesize the infix expression according to order
of priority you want.
2. Move each operator to its corresponding right parenthesis.
3. Remove all parentheses.

• Examples:
3+4*5 (3 + (4 * 5) ) 345*+

a/b^c–d*e–a*c^3^4 abc^/de*ac34^^*-
-

((a / (b ^ c)) – ((d * e) – (a * (c ^ (3 ^ 4) ) ) ) )

17
 Infix to Prefix conversion (manual)
• An Infix to Prefix manual conversion algorithm is:
1. Completely parenthesize the infix expression according to
order of priority you want.
2. Move each operator to its corresponding left parenthesis.
3. Remove all parentheses.

• Examples:
3+4*5 (3 + (4 * 5) ) +3*4 5

a/b^c–d*e–a*c^3^4 -/a^b c-* d e*a^c^

3 4

( (a / (b ^ c)) – ( (d * e) – (a * (c ^ (3 ^ 4) ) ) ) )

18
 Application of Stacks - Evaluating Postfix Expression (Cont’d)

• The following algorithm uses a stack to evaluate a postfix expressions.

Start with an empty stack

for (each item in the expression) {
if (the item is an operand)
Push the operand onto the stack
else if (the item is an operator operatorX){
Pop operand1 from the stack
Pop operand2 from the stack
result = operand2 operatorX operand1
Push the result onto the stack
}
}

Pop the only operand from the stack: this is the result of the evaluation

19
 Application of Stacks - Evaluating Postfix Expression (Cont’d)
• Example: Consider the postfix expression, 2 10 + 9 6 - /, which is (2 + 10) / (9 - 6)
in infix, the result of which is 12 / 3 = 4.

• The following is a trace of the postfix evaluation algorithm for the postfix expression:

20
 Application of Stacks – Infix to Postfix Conversion
postfixString = “”;
while(infixString has tokens){
Get next token x;
if(x is operand)
Append x to postfixString;
else if(x is ‘(’ )
[Link](x);
else if(x is ‘)’ ){
y = [Link]();
while(y is not ‘(’ ){
Append y to postfixString;
y = [Link]();
}
discard both ‘(‘ and ‘)’;
}
else if(x is operator){
while(stack is not empty){
y = [Link](); // top value is not removed from stack
if(y is ‘(‘ ) break;
if(y has low precedence than x) break;
if(y is right associative with equal precedence to x) break;
y = [Link]();
Append y to postfixString;
}
push x;
}

21
 Application of Stacks – Infix to Postfix Conversion (cont’d)
while(stack is not empty){
y = [Link]( );
Append y to postfixString;
}
:step1 :step2

:step3 :step4

22
 Application of Stacks – Infix to Postfix Conversion (cont’d)

:step5 :step6

:step7 :step8

23
 Application of Stacks – Infix to Postfix Conversion (cont’d)

:step9 :step10

:step11 :step12

24
 Application of Stacks – Infix to Postfix Conversion (cont’d)

:step13 :step14

:step15 :step16

25
 Application of Stacks – Infix to Postfix Conversion (cont’d)

:step17 :step18

26
 Application of Stacks – Infix to Prefix Conversion

An infix to prefix conversion algorithm:

1. Reverse the infix string
2. Perform the infix to postfix algorithm on the reversed string
3. Reverse the output postfix string

Example: (A + B) * (B – C)

reverse

(C – B) * (B + A)

Infix to postfix algorithm

C B - B A + *

reverse

* + A B - B C
27