1 of 40

Lecture 3

Stack

2 of 40

Stack

3 of 40

The Stack ADT (Abstract Data Type)

A Stack is a collection of objects inserted and removed according to the Last In First Out (LIFO) principle. Think of a stack of dishes.

4 of 40

Stack operations

Push and Pop are the two main operations

5 of 40

6 of 40

A lot of applications

Think of the undo operation of an editor. The recent changes are pushed into a stack, and the undo operation pops it from the stack.
Reverse strings
The expression evaluation stacks are also used for parameter passing and local variable storage.

Think of ED diagrams and recursions!

Check if a given expression has correct “(“ , “)” order.

7 of 40

Classic Example: Parenthesis checker

(2 + 3) - (4 + 1)

Push “(“
Ignore 2,“+”, 3
If you see” )” then Pop “(”. Exists?
Ignore “-”
Push “(“
Ignore 4, “+”, 1
If you see” )” then Pop “(”. Exists?
Empty Stack, empty Input! Hooray!

8 of 40

Implementation. Arrays

Main update methods:

Push(e): add an element to the stack
Pop( ): remove an element from the stack

Additional useful methods

Peek(): Same as pop, but does not remove the element
Empty(): Boolean, True when the stack is empty
Size(): Returns the size of the stack

9 of 40

reminder

mic

10 of 40

11 of 40

Implementation design




X
X

12 of 40

Implementation design




X
X

top

13 of 40

Implementation design




X
X

top

push(2)

14 of 40

Implementation design



2
X
X

top

push(2)

15 of 40

Implementation design



2
X
X

top

push(2)

16 of 40

Implementation design



2
X
X

top

push(2)

push(5)

17 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

18 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

pop()

19 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

pop()

20 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

pop() //5 is returned

21 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

pop() //5 is returned

push(7)

22 of 40

Implementation design


7
2
X
X

top

push(2)

push(5)

pop() //5 is returned

push(7)

23 of 40

Implementation design


7
2
X
X

top

push(2)

push(5)

pop() //5 is returned

push(7)

push (int elem) {

stack[top]= elem;

top++;

}

stack

top = 0

top

24 of 40

Implementation design


7
2
X
X

top

push(2)

push(5)

pop() //5 is returned

push(7)

push (int elem) {

stack[top]= elem;

top++;

}

stack

top = 0

top

int pop() {

top --;

return stack[top];

}

25 of 40

Implementation design




X
X

26 of 40

Implementation design




X
X

top

27 of 40

Implementation design




X
X

top

push(2)

28 of 40

Implementation design




X
X

top

push(2)

29 of 40

Implementation design



2
X
X

top

push(2)

30 of 40

Implementation design



2
X
X

top

push(2)

push(5)

31 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

32 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

pop()

33 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

pop()

34 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

pop() //5 is returned

35 of 40

Implementation design


5
2
X
X

top

push(2)

push(5)

pop() //5 is returned

push(7)

36 of 40

Implementation design


7
2
X
X

top

push(2)

push(5)

pop() //5 is returned

push(7)

37 of 40

Implementation design


7
2
X
X

top

push(2)

push(5)

pop() //5 is returned

push(7)

push (int elem) {

top++;

stack[top]= elem;

}

stack

top = -1

top

38 of 40

Implementation design


7
2
X
X

top

push(2)

push(5)

pop() //5 is returned

push(7)

push (int elem) {

top++;

stack[top]= elem;

}

stack

top = 0

top

int pop() {

e = stack[top];

top --;

return e;

}

39 of 40

Complexity

Operation	Complexity
Push	O(1)
Pop	O(1)

40 of 40

Advantage and Limitation

Advantages of Array-based Implementation Fast:

all operations are completed in one step. No loops are needed: O(1)

Limitations of Array-based Implementation:

You have to know the upper bound of growth and allocate memory accordingly. If the array is full and there is another push operation then you encounter an exception (error).