Stacks

Abstract Data Type (ADT):

What is an Abstract Data Type?

To answer this, let us ask the negative of this:

What is NOT an Abstract Data Type (in C++)?
◦Int
◦int is a built-in type in the C++ language
◦Double
◦double is a built-in type in the JAVA language
◦There are certainly many others we can list
These data types are already built into the language
Abstract Data Type (ADT):

So again, what is an Abstract Data Type?

◦It is a data type that is NOT built into the language
◦It is a data type that we will “build”
◦We will specify what it is, how it is used, etc.
◦It is often defined in terms of its behaviour rather than its implemented
representation

another definition from Wikipedia:

An abstract data type is defined indirectly, only by the operations
that may be performed on it (i.e. behaviour)
Stacks – An Overview

Stacks:

Stacks are an Abstract Data Type

◦They are NOT built into C++
We must define them and their behaviours

So what is a stack?
◦A data structure that stores information in the form of a stack.
◦Consists of a variable number of homogeneous elements
◦i.e. elements of the same type
Stacks
Access Policy:

The access policy for a stack is simple: the first element to be

removed from the stack is the last element that was placed onto
the stack
◦The main idea is that the last item placed on to the stack is the first
item removed from the stack

Known as the “Last in, First out” access policy

◦LIFO for short
Stacks
Basic Operations:
◦PUSH:
◦This Pushes an item on top of the stack
◦POP:
◦This POPs off the top item in the stack and returns it
Other important aspects:

The end of the stack,

◦where Pushes and POPs occur,
is usually referred to as the TOP of the stack
Building Stack Step-by-Step
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
stacks
Other useful operations:
◦isEmpty:
◦Typically implemented as a Boolean function
◦Returns TRUE if no items are in the stack
◦isFull:
◦Returns TRUE if no more items can be added to the stack
◦In theory, a stack should NEVER become full
◦Actual implementations do have limits on the number of elements a stack can store
◦top:
◦Simply returns the value at the top of the stack without actually popping the stack.
stacks
Other useful operations:
◦Note:
◦Each of those operations ACCESS the stack
◦But they do NOT modify the stack
◦A PUSH can only be done if the stack isn’t full
◦A POP can only be done on a non empty stack
Implementation of a stack:
◦Can be done using both static and dynamic memory
◦Array or a linked list
◦Implemented as an array, the stack could possibly become full
◦As a linked list, this is MUCH LESS LIKELY to occur
We will cover detailed implementations NEXT TIME.
Stack Errors
Stack Overflow
 An attempt to add a new element in an already full stack is an error

 A common mistake often made in stack implementation

 Stack Underflow
 An attempt to remove an element from the empty stack is also an
error

 Again, a common mistake often made in stack implementation

 Example : The following table shows a series of stack operations
and their effects on an initially empty stack S of integers.
Operation Output Stack Contents

push(5) - (5)
push(3) - (5, 3)
pop() 3 (5)
push(7) - (5, 7)
pop() 7 (5)
top() 5 (5)
pop() 5 ()
pop() "error“ ()
isEmpty() ()
push(9) true
push(7) - (9)
push(3) - (9, 7)
push(5) - (9, 7, 3)
size() - (9, 7, 3, 5)
pop() 4 (9, 7, 3, 5)
push(8) 5 (9, 7, 3)
pop() - (9, 7, 3, 8)
pop() 8 (9, 7, 3)
3 (9, 7)
Using stacks
So when is stack useful?
◦When data needs to be stored and then retrieved in reverse order
Applications:
◦Page-visited history in a Web browsers.
◦Undo sequence in a text editor.
Stacks: Implementation in
C++
Array Implementation of Stacks:
◦What components will we need to store?
◦The array storing the elements
◦ The actual stack
◦An index to the top of the stack
◦We assume the bottom of the stack is index 0
◦ Meaning, the 1st element will be stored in index 0
◦and we move up from there
◦The max size of the stack
Array Implementation of
Stacks:

Here is our class, intStack:

maxSize clearly represents the max number of items in the stack

If the stack becomes full, at that point, the top item will be stored at index
‘maxSize-1’
Array Implementation of
Stacks:

Here is the constructor:

So we set maxSize from the parameter sizeOfStack

We then make the new array, stackArray
Finally, we set top equal to -1
◦So when top is zero, that means we have ONE element
◦To show that the stack is empty, we set Top equal to -1
Array Implementation of
Stacks:

Here are the methods we will need to control our stack behavior:

Public Boolean isEmpty()

Public Boolean isFull()
public void push(int j)

Public int pop()

Public int peak()
Array Implementation of
Stacks:

isEmpty:
◦The isEmpty function simply checks if the stack has no elements
◦Based on what you know so far, how would you determine if the stack
is empty?
◦If the top currently equals -1!
Here’s the code:
Array Implementation of
Stacks:
isFull():
◦The isFull function checks to see if the stack is full
◦How would we do this?
◦Remember, maxSize is the max # of items in the stack
◦Item 1 goes at index 0
◦If the stack is full, the top item will be at index ‘maxSize-1’
Here’s the code:
Array Implementation of
Stacks:
push:
◦Remember, we can only push if the stack is not full
◦Meaning, if there is room to push
◦So if the stack is full
◦We throw an Exception, showing the push could not be done
◦If there is room
◦We increment top to point to the next space in the stack
◦Then we simply copy the value into this new top position
Array Implementation of
Stacks:
push:

To push an element, increment top to point to the next space in

the stack
Then we simply copy the value into this new top position
Here’s the code:
Array Implementation of
Stacks:
pop:

Remember, we can only pop if the stack is not empty

◦Meaning, there is at least one element to pop
So if the stack is empty
◦We throw an exception showing that we cannot pop
If the stack has at least one element:
◦We return the value at position top
◦At the same time, we decrement top
◦This makes the top “pointer” refer to the next item down in the stack
Array Implementation of
Stacks:
pop:

To pop an element, we simply return the top item in the stack and
then decrement top
Here’s the code:
Array Implementation of
Stacks:
Peek (or top):

The peek method is very similar to pop

Remember, we can only check for the top of the stack if the stack is not empty
◦Meaning, there is at least one element in the stack
So if the stack is empty
◦We throw an exception
If the stack has at least one element:
◦We simply return the topmost element
◦It returns the value of the top ("front") of the collection without removing the
element from the collection.
◦NO decrement
Array Implementation of
Stacks:
top:
◦Simply returns the top item in the stack
Here’s the code:
Linked Lists Implementation of
Stacks
Linked Lists Implementation of Stacks:
◦We essentially use a standard linked list
◦But we limit the functionality of a linked list
◦Thus creating the behavior required of a stack
◦A push is simply designated as inserting into the front of the linked list
◦A pop would be deleting the front node
Linked Lists Implementation
of Stacks:
So each node will be an element of the stack

Each node has a data value

Each node also has a next

We simply push (insert at front)

And pop (delete the front node)

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)
Linked Lists Implementation
of Stacks: