y !

n l
y o
d a
T o
Learn to program in Java in
(less than) one hour!

l!
e a
l d
c ia
p e
S
 y !
n l
y o
d a
T o

is open
CS2040S
Data Structures and Algorithms

Welcome!

is open
Reminders

1. Tutorials / Recitations were announced

last night.
– Timeslot was fixed.
– Section may change. (Balancing will finish today.)

2. DO NOT use ModReg to adjust or swap

tutorial or recitation.
– Not your allocated slot. Not any slot.
– It will only cause trouble!
Reminders

3. Help! I don’t have a slot!

– Please fill out the appeal on Coursemology.
– Deadline: Thursday (tomorrow), noon.

4. Help! My assigned slot conflicts!

– Please fill out the appeal on Coursemology.
– Deadline: Thursday (tomorrow), noon.
Reminders

5. Help! I don’t like my slot!

– Please find someone else to swap with.
– See Coursemology forum.
– Please fill out the appeal on Coursemology.
– Deadline: Thursday (tomorrow), noon.
Reminders

DO NOT use ModReg to adjust or swap

tutorial or recitation.
– We have the master list.
– We will revert back changes you make directly.
– The only way to change is via Coursemology
appeal survey.
Reminders

Do read Coursemology Announcements.

– We will keep you updated on the status.
Reminders
Problem Set 1:
– Available on Coursemology
– Full description in pdf file (with FAQ at end).
– Due Sunday night.
– Discussion on Coursemology if you have questions
• Java setup issues (JDK, etc.)
• Why is my image blank?
• Why is my image wrong?
• I don’t recognize the person in that picture?
Reminders
Beware:
Finalize Submission means…
You have finalized your submission.
– No more changes after it is finalized.
– Only click finalize when you are done with all the
parts of the problem set or lecture review.
 On CS2040S Problem Sets:

Do not use libraries that simplify the

problem.

Do not use libraries unless the problem set

specifically says you can.

In t h e
f
the fo uture, you
ru m a can as
your t n d /or ch k on
utor, i e ck
f u n su w ith If the goal of the problem set is to write
re.
a sorting routine, then calling the Java
library sort defeats the purpose…
Reminders
Archipelago: (if you didn’t receive, check your spam for the link)

– A little room for interaction…

– Some distraction from just staring at a screen…
– Some motivation for in person attendance…
– “Random Question” is always open for feedback.
– I try to answer unanswered questions after class
on Coursemology Forum.
– EXP for everyone that uses Archipelago during
lecture (starting next week).

If you joined the class late, you may not yet be properly in Archipelago. Apologies, will fix.
 y !
n l
y o
d a
T o
the basics of OOP and Java
the basics of OOP and Java

For more advanced topics:

• See CS2030S.
• Google.
• See suggested (optional) textbook.
Java “advanced” features:
Examples:

Lambda expressions:
Java “advanced” features:
Examples:

Type inference:

vs.
Java “advanced” features:
Examples:

Default, static private methods in an interface:

Many different use cases, restrictions, rules, best practices, …

Advice:

Do not use the advanced features:

• Typically, just makes code shorter.
• Very little extra functionality.
• Often hide what is really happening.
• Can make code easier to read, but can make code
harder to read.

* Especially if you are new to Java.

Goals in writing code:
1. Correct / bug-free.
2. Easy to read / understand.
3. Efficient.
4. Submitted by the deadline.
5. ..
6. ..
7. ..
8. ..
100. Short.
Advice:

Make your code intentional.

(Do not rely on default / non-explicit behavior.)

* Especially if you are new to Java.

More advice: use the IntelliJ debugger

Click “debug”

Set a breakpoint…
is open
More advice: use the IntelliJ debugger

Step through your code

Warning:

Today’s goal:
To make you aware of key aspects of Java

After class:
Go look things up!
the basics of OOP and Java
Programming Paradigms

Programming paradigms:
– Procedural (imperative) languages
– Functional languages
– Declarative languages
– Object-oriented languages

How to organize information?

How to think about a solution?
Programming Paradigms

Object-oriented Languages
– Examples: Java, C++, …

– Advantages:
• Near-ubiquitous in industry
• Modular
• Code re-use
• Easier to iterate / develop new versions
– Information hiding
– Pluggable
Object-oriented Paradigm
Separate interface (”what it is
Abstraction supposed to do”) from implementation
(“how it does it”).

Encapsulation Hide implementation. Only make

interface publically visible.

Build new classes by extending

Inheritance existing classes. (Share functionality.)

Same interface, but different behavior

Polymorphism based on context.
([Link]()meows if animal
is a cat, and barks if animal is a dog..)
Object-oriented Paradigm

Abstraction
Very relevant
to CS2040S

Encapsulation

Inheritance
Less relevant
to CS2040S
(but very important overall).
Polymorphism
 Problem: Naruto the new
Naruto the new hirehire
Description of Naruto:
­ “Nice guy!”
­ “Really likes bananas!”
­ “Not the smartest fellow... but
friendly!”
­ “I’m afraid he’s going to $^%&
up our code, man!”
 what should we do?
What should we do?
Give him some pointless work!
Send him back to the forest!

But we want Naruto to help with

our project!
But we don’t want him to wreck
our software.
 Abstraction

Remove all unnecessary elements:

• What Naruto needs-to-know? Expose!
• What Naruto doesn’t need-to-know? Hide!

Keep things simple!

 Encapsulation and information hiding

User
Implementer Object

Public Interface

Private Data
Naruto
[XKCD: Black Hat]
Private Methods
Claim: We are all Naruto!
 Software is getting very complex

[[Link]
 Software is getting very complex

[[Link]
 Software is getting very complex

Also look at : [Link]

37
 Encapsulation and information hiding

User
Implementer Object

Public Interface

Private Data
Naruto
[XKCD: Black Hat]
Private Methods

Abstract away unnecessary details

Better understand complex software
Save us from ourselves
Abstraction
Software engineering
– Divide problem into components.
– Define interface between components.
– Assign a team to build each component.
– (Recurse.)

– Top down design: get the big idea first, then

figure out how to implement it.
Abstraction
Algorithm design
– Divide problem into components.
– Define interface between components.
– Solve each problem separately.
– (Recurse.)
– Combine solutions.
Object-oriented Programming

Object has:
– State (i.e., data)
– Behavior (i.e., methods for modifying the state)

Classroom
enter(student)
list_of_students
leave(student)
number of chairs
temperature
count()
 How to implement a File System?

1. file management object + file contents object

2. file object
3. folder hierarchy + folder contents
4. file object + folder object

is open
 How to implement a File System?

1. file management object + file contents object

2. file object
3. folder hierarchy + folder contents
Objects represent state (“nouns”)
4. file object + folder object
not actions (”verbs”).
 How to implement a File System?

1. file management object + file contents object

2. file object
3. folder hierarchy + folder contents
4. file object + folder object

What after folders?

 How to implement a File System?

1. file management object + file contents object

2. file object
3. folder hierarchy + folder contents
4. file object + folder object

Objects should be unitary, without

dividing functionality.
 How to implement a File System?

1. file management object + file contents object

2. file object
3. folder hierarchy + folder contents
4. file object + folder object
How to implement a File System?

Files: Folders:
– Contain data – Contain files
– Edited – Contain folders
– Rename – Rename
– Moved – Moved
 First principle of Java

« Everything is an object »
 First principle of Java

« Everything is an object »

“But I was told Java 8+ was functional!” To Java, these are

“What about the lambda expressions?” just disguised objects.
“Java supports anonymous functions now!”
 First principle of Java

« Everything is an object »

A class is a template for producing an object.

Defining a class in Java
class File
{
String name = “”;
FileData contents = null;

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
Defining a class in Java
class File
{
String name = “”;
FileData contents = null;

void rename(String newName){...}

Not Java syntax.
FileData getData(){...} Abbrv. for slides.

void setData(FileData newdata){...}

}
Defining a class in Java
class File
{
String name = “”;
FileData contents = null;

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
Defining a class in Java
class File
Name of class MUST
{ be name of file.
String name = “”; è
FileData contents = null;
[Link]

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
Defining a class in Java
class File
Variables initialized
{ when defined first.
String name = “”;
Advice: don’t rely on
FileData contents = null; defaults: be explicit.

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
 Second principle of Java

« Everything has a type »

 Second principle of Java

« Everything has a type »

“But I can declare a local To Java, there is still

variable with just var as an a type. It just sometimes
unspecified type!” guesses it for you.
 Second principle of Java

« Everything has a type »

int j = 7; var j = 7;
j = “7”; ERROR j = “7”;
 Second principle of Java

« Everything has a type »

int j = 7; var j = 7;
j = “7”; ERROR j = “7”;

Advice: always specify the type.

(Don’t rely on type inference.)
Types
class File
{
String name = “”;
FileData contents = null;

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
Java library class: String

Creating strings:
String str = “Some text.”;
String altStr = new String(“some text”);

Accessing a string:
– charAt(int index)
– substring(int begin, int end)
– toCharArray()
[Link]
– length() /api/[Link]/java/lang/[Link]
Java library class: String

Comparing strings:
– compareTo(String otherString)
– compareToIgnoreCase(String otherString)
– equals(Object anObject)

Using strings:
– Flexible and easy: str = str + ‘c’;
– Use with care…
[Link]
/api/[Link]/java/lang/[Link]
Java library class: String

Comparing strings:
– compareTo(String otherString)
– compareToIgnoreCase(String otherString)
– equals(Object anObject)

Common bug:
Using strings:
– Flexible and easy: str = str + ‘c’;
– Use with care…
Types
class File
{
String name = “”;
FileData contents = null;

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
Member (Instance) Variables
class File
{
String name = “”;
FileData contents = null;

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
Methods (Functions)
class File
{
String name = “”;
FileData contents = null;

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
Defining a class in Java
class File
{
String name = “”;
FileData contents = null;

void rename(String newName){...}

FileData getData(){...}
void setData(FileData newdata){...}
}
Another class
class Folder
{ Note array notation

String name;
Folder[] children;
File[] files;
Note “recursive” folder

int getNumFiles(){...}
File getFile(int i){...}

}
 Class vs. Object

What’s the difference?

is open
 Class vs. Object

What’s the difference?

Class is a template for how to make an object.

An object is an instance of the class.

Creating a new object

Folder createFolder(String name)

{
Folder redFolder = new Folder(name);
return redFolder;
}
Creating a new object

Folder createFolder(String name)

{
Folder redFolder = new Folder(name);
return redFolder;
}

Calls “constructor” with parameter: name

Constructors
class File
{
String name = “”;
FileData contents = null;

File(String fileName)
{
name = fileName;
contents = null; Constructor:
} • Same name as class.
• Takes 0 or more parameters.
} • Called on object creation.
• Used to initialize class.
• Runs after variables initialized
on declaration.
Constructors Many rules involving constructors.
class File
E.g., when exactly are they executed
{ during object construction? In what
String name = “”;order? Etc.
FileData contents = null;
Especially complicated with inheritance.
File(String fileName)
{
name = fileName;
contents = null;
}
}
Object-oriented Paradigm
Separate interface (”what it is
Abstraction supposed to do”) from implementation
(“how it does it”).

Encapsulation Hide implementation. Only make

interface publically visible.

Build new classes by extending

Inheritance existing classes. (Share functionality.)

Same interface, but different behavior

Polymorphism based on context.
([Link]()meows if animal
is a cat, and barks if animal is a dog..)
Object-oriented Programming

Object has:
– State (i.e., data)
– Behavior (i.e., methods for modifying the state)

Classroom
enter(student)
list_of_students
leave(student)
number of chairs
temperature
count()
Abstraction

Interface: how you manipulate the object

Implementation: details hidden inside the object

Classroom
enter(student)
list_of_students
leave(student)
number of chairs
temperature
count()
Defining an interface
// Explain with a comment
// what your interface is for.
interface IFile
{
// Comments explain how to use interface
void rename(String newName);

FileData getData();

void setData(FileData newdata);

} Note no functionality!
Only method names.
Except for the
“advanced features.”
Implementing an interface
class File implements IFile
{
String name = “”; “I promise to implement
all the functionality in IFile.”
FileData contents = null;

void rename(String newName){...}

FileData getData(){...}

void setData(FileData newdata){...}

}
Implementing an interface
class OtherFile implements IFile
{
char[] nom;

char[] meteo;

FileData getData(){...}

void setData(FileData nouveau){...}

}
Implementing an interface
class OtherFile implements IFile
{
char[] nom; Is this good?

char[] meteo;

FileData getData(){...}

void setData(FileData nouveau){...}

}

is open
Implementing an interface
class OtherFile implements IFile
{
char[] nom;

char[] meteo;
Error!
FileData getData(){...}

void setData(FileData nouveau){...}

}
Implementing an interface
class OtherFile implements IFile
{
char[] nom;

char[] meteo;

void rename() {...}

FileData getData(){...}

void setData(FileData nouveau){...}

}
Using an interface
IFile copyFile(IFile oldFile) {

File newFile = new File();

FileData data = [Link]();

[Link](data);

return newFile; It does not matter how the object

is implemented. The oldFile can
} be a File or an OtherFile.
Problem Set 1
Quick summary…
So far: Object-Oriented Programming
– Defining classes and interfaces
– Implementing interfaces
– Using interfaces

Next: Some Java Details

– Access control
– Static variables / methods
– Initializing an object / Constructors
 Access Control

« Behavior is public, data is private »

Defining a class in Java
public class OtherFile implements IFile
{
private char[] name;

private char[] contents;

public void rename() {...}

public FileData getData(){...}

public void setData(FileData newdata){...}

private void compressDataStorage()

}
Access Control

• (none specified)
– within the same package

• public
– everywhere

• private:
– only in the same class

• protected:
– within the same package, and by subclasses
Access Control
public class A
{
private int secretFunction();

public class B
{
public int stealSecrets(A example){

int readMe = [Link]();

Error: cannot access secretFunction().

Access Control
public class A
{
private int secretVariable;

public class B
{
public int stealSecrets(A example){

int readMe = [Link];

Error: cannot access secretVariable.

Access Control
public class A
{
public int secretVariable;

public class B
{
public int stealSecrets(A example){

int readMe = [Link];

Ok, can access secretVariable.

Access Control
public class A Bad idea!
{
public int secretVariable; Breaks encapsulation.
}

public class B
{
public int stealSecrets(A example){

int readMe = [Link];

Ok, can access secretVariable.

Access Control
public class B
{

public B(int data){

// Initialize class B using data.
}
public int stealSecrets(A example){

int readMe = [Link];

}
A constructor should (almost) always be public.

Why?
Access Control
public interface ISee
{

public int ReadSomething(int data);

public int WriteSomething(int data);

An interface should (almost) always be public.

Interface methods should (almost) always be public.

Why?
Access Control

• (none specified)
– within the same package

• public
– everywhere

• private:
– only in the same class

• protected:
– within the same package, and by subclasses
Access Control

• (none specified)
– within the same package

• public Advice:
– everywhere Always specify the access you intend
(even if the default behavior is okay).
• private:
– only in the same class

• protected:
– within the same package, and by subclasses
Packages
package [Link];

public class B
{
public int stealSecrets(A example){

int readMe = [Link]();

}
}
For CS2040S:

We will not use packages.

Importing library code
import CleverCode.*;

public class B
{
public int stealSecrets(A example){

int readMe = [Link]();

}
}
Import everything from CleverCode.
Importing library code
import [Link];

public class B
{
public int stealSecrets(A example){

ShiftRegister reg = [Link]();

}
}

Import just ShiftRegister from package.

Good practice: only import what you need.

Importing library code
import [Link];

public class B
{
public int stealSecrets(A example){

ShiftRegister reg = [Link]();

}
}

Import HashMap from java libraries.

On problem sets: see instructions to see what you can use.

 On CS2040S Problem Sets:

Do not use libraries if they make the problem

set easier.

Do not use libraries unless the problem set

specifically says you can.

If the goal of the problem set is to write

a sorting routine, then calling the Java
library sort defeats the purpose…
 Class vs. Object

What’s the difference?

Class is a template for how to make an object.

An object is an instance of the class.

 Class vs. Object

What’s the difference?

Class is a template for how to make an object.

An object is an instance of the class.

regular variables/functions are PER OBJECT

static variables/functions are PER CLASS
static methods
class File
{
private String fileName = “”;

private FileData contents = null;

public static String addExt(String name){

return (name + “.pdf”);

}
}
static methods
class File
{
private String fileName = “”;

private FileData contents = null;

public static String addExt(String name){

fileName = name;

return (name + “.pdf”);

}
static methods
class File
{
private String fileName = “”;

private FileData contents = null;

public static String addExt(String name){

fileName = name;

return (name + “.pdf”);

Error!
}
Cannot access member variable.
}
static methods
class File
{
private String m_name = “”;

private static int s_count = 0;

public void increment(){

s_count++;

} Every File object shares s_count.

}
Initializing an object
Initializing an object
class File
{
private String name = “”;

private FileData contents = null;

public File(String fileName){

name = fileName;

contents = null;

}
}
Initializing an object
class File
{
private String name = “”;

private FileData contents = null;

// Constructor
public File(String fileName){

name = fileName;

contents = null;

}
}
Initializing an object
class File
{
public File(String fileName){

name = fileName;

contents = null;

}
Multiple constructors with
public File(){ different signatures.

name = null;

contents = null:
}
Initializing an object with an array
class File
{
private int[] pageNumbers = new int[100];

If the array size is fixed, then initialization is simple.

What if the array size is not known in advance?

Initializing an object with an array
class File
{
private int[] pageNumbers = null;

public File(int NumPages){

pageNumbers = new int[numPages];

}
}
You might use a constructor to initialize the array.
The main method
class FileSystem

public static void main(String[] args){

Folder root = new Folder();

File homework = new File(“[Link]”);

[Link](homework);

}
Creating an object
class FileSystem

public static void main(String[] args){

Folder root = new Folder();

File homework = new File(“[Link]”);

[Link](homework);

}
Using a constructor
class FileSystem

public static void main(String[] args){

Folder root = new Folder();

File homework = new File(“[Link]”);

[Link](homework);

}
Invoking a method
class FileSystem

public static void main(String[] args){

Folder root = new Folder();

File homework = new File(“[Link]”);

[Link](homework);

}
Java Operators
Operator Functionality
assignment
=
plus, minus, multiplication, division
+, –, *, /
remainder
%
increment, decrement
++, – –
test equality
==, !=
less than, greater than
<, >
less-than-or-equal, greater-than-or-equal
<=, >=
left shift, right shift
<<, >>
logical and, logical or
&&, ||
bitwise operations: complement, and, xor, or
~, &, ^, |
Primitive Data Types
Name Size Min Max

byte 8 bit -128 127

short 16 bit -32,768 32,767

int 32 bit -2,147,483,648 2,147,483,647

-9,223,372,036,854,775,808 9,223,372,036,854,775,808
long 64 bit
float 32 bit
double 64 bit
boolean 1 bit false true

char 16 bit \u0000 (0) \uffff (65535)

(unicode)
Problem Set 1
A few common problems

Library setup

See forum for discussion of making sure IntelliJ is

setup correctly (with access to JUnit library, etc.).
A few common problems

The file does not run properly

You need a “main” method.

Make sure IntelliJ is running the right “main” method.

Make sure the filename is the same as the class.

A few common problems

The file does not compile

Check all the red squiggles. (Hover over them.)

Check all the files in the project.

A few common problems

The image file comes up empty.

Check your ShiftRegister.

Check if the image file is in the right place.

Check if the image is being opened correctly (or if

there is an exception being thrown).
A few common problems
Other problems?

See discussion in forum.

Google weird error messages.

Ask questions in forum.

Find out more:

Java basics:
[Link]

Java object-oriented programming:

[Link]
 y !
n l
y o
d a
T o
Puzzle of the Week

Non-transitive Dice: A > B > C > A

– A has six sides: 2, 2, 4, 4, 9, 9
– B has six sides: 1, 1, 6, 6, 8, 8
– C has six sides: 3, 3, 5, 5, 7, 7

Game: Questions:
– Alice chooses a die. – Which die should Alice
– Bob chooses a die. choose?

– Alice and Bob both roll. – Which die should Bob

choose?
– The higher value wins.
– Who is more likely to win?
More Dice Puzzles

Sicherman Dice
– Two six-sided dice
– Same distribution for the SUM
Wikipedia:
 Next Week

How to search for stuff…

Puzzle of the Week

Imagine three dice:

– A has six sides: 2, 2, 4, 4, 9, 9
– B has six sides: 1, 1, 6, 6, 8, 8
– C has six sides: 3, 3, 5, 5, 7, 7

Non-transitive dice:
– A beats B.
– B beats C.
– C beats A
– Choosing second is the best strategy!
Puzzle of the Week

Imagine three dice:

– A has six sides: 2, 2, 4, 4, 9, 9
– B has six sides: 1, 1, 6, 6, 8, 8
– C has six sides: 3, 3, 5, 5, 7, 7

Questions:
– Algorithm for deciding if dice are non-transitive?
– Can you design a set of 10 non-transitive dice?
– Can you design a set of 20-sided non-transitive dice?
A little quiz, just for fun…
 Which of the following is NOT a
fundamental OOP principle?

1. Inheritance
2. Behavioralism
3. Encapsulation
4. Polymorphism
 Encapsulation suggests that you should:

A. Keep each class in its own file.

B. Keep all of a class’s behaviors private.
C. Keep all of a class’s data private.
D. Prefer to use static variables
E. Write you code in a Japanese capsule hotel.
 “Behavior is public, implementation is private.”
Thus all methods should be public.

1. True
2. False
3. Sort of
 Which statement is NOT true?

1. All methods in an interface should be

public.
2. You may not declare an instance variable
in an interface.
3. An interface should be well commented.
4. An interface may include some methods
that are completely implemented.
A constructor is the first place a variable is
initialized?

1. Yes
2. No
 You do not need to specify the size of an
array when you declare it.

1. True
2. False
 Consider the following:
A. Static methods can never access
non-static variables.
B. Non-static methods can never access
static variables.

1. Only A.
2. Only B.
3. Both A and B.
4. Neither A nor B.
Which of the following is NOT a benefit of
encapsulation?

1. Modularity
2. Bug reduction
3. Information (data)
hiding
4. Implementation hiding
5. Logical code
organization
6. None of the above.
 Interfaces are primarily useful as a
conceptual method of separation, and have
little practical impact on my program.
1. True
2. False
3. Sort of
Abstract Data Types (Not Java specific.)

Specification:
– Interface
– Behavior

Implementation:
– Algorithm
– State
Abstract Data Types
Bag (of integers)
Interface:
void add(int x)
int remove()
boolean isEmpty()

Behavior:
– add(x) : adds an item to the bag
– remove() : removes an arbitrary item from the bag
Abstract Data Types
List
Interface:
Abstract Data Types
List
Interface:
void append(int x)
void prepend(int x)
void put(int x, int slot)
void remove(int x) first last
int getFirst()
int getLast()
int get(int slot)
45 57 23 21 17
boolean isEmpty()
0 1 2 3 4
Abstract Data Types
interface [Link]
Interface:
void add(int x)
void addAll(Collection c)
void clear()
void contains(int x) first last
void isEmpty()
int remove()
int set()
45 57 23 21 17

0 1 2 3 4
Abstract Data Types
interface [Link]
Java implementations:
[Link]
[Link]
[Link]

first last

45 57 23 21 17

0 1 2 3 4
Abstract Data Types
Stack
Interface:
– void push(element x)
– element pop()

Behavior: (LIFO: last-in, first-out)

– push(x) : adds element x to the stack
– pop() : removes the mostly recently added
element and returns it
Abstract Data Types
Stack
Interface:
– void push(element x)
– element pop()
– empty()
top 45
of stack
57
23
100
Abstract Data Types
Stack
Execution:
– push(77)

top 45
of stack
57
23
100
Abstract Data Types
Stack
Execution:
– push(77)

top 77
of stack
45
57
23
100
Abstract Data Types
Stack
Execution:
– push(77)
– push(33) top 33
of stack
77
45
57
23
100
Abstract Data Types
Stack
Execution:
– push(77)
– push(33) 33
– pop() ® ?? top 77
of stack
45
57
23
100
Abstract Data Types
Stack
Execution:
– push(77)
– push(33)
– pop() ® 33 top 77
of stack
45
57
23
100
Abstract Data Types
Stack
Execution:
– push(77)
– push(33)
– pop() ® 33
– pop() ® 77
– pop() ® 45
– pop() ® 57 top 23
of stack
100
Abstract Data Types
Stack
Execution:
– pop() ® 23
– pop() ® 100

top
of stack
Abstract Data Types
Stack
Execution:
– pop() ® 23
– pop() ® 100
– pop() ® ??

top
of stack
Abstract Data Types
Stack
Execution:
– pop() ® 23
– pop() ® 100
– pop() ® ??

• Error!
– Option 1: throw exception (postponed)
– Option 2: modify specification
top
of stack
Abstract Data Types
Stack
Execution:
– pop() ® 23
– pop() ® 100
– empty() ® true

top
of stack
Abstract Data Types
Queue
Interface:
– void enqueue(element x)
– element dequeue()

Behavior: (FIFO: first-in, first-out)

– enqueue(x) : adds element x to the front of the
queue
– dequeue() : removes and returns element at the
end of the queue
Abstract Data Types
Queue
Execution:

back front

45 57 23
Abstract Data Types
Queue
Execution:
– enqueue(7)

back front

45 57 23
Abstract Data Types
Queue
Execution:
– enqueue(7)

back front

7 45 57 23
Abstract Data Types
Queue
Execution:
– enqueue(7)
– dequeue() ® 23

back front

7 45 57 23
Sorting with Stacks
Is it always possible to insert “pop”
commands to make the output sorted?
Example:
654321 è 654321 −−−−−−
Sorting with Stacks
Is it always possible to insert “pop”
commands to make the output sorted?
Example:
654321 è 654321 −−−−−−

123456 è 1−2− 3− 4− 5− 6
Sorting with Stacks
Is it always possible to insert “pop”
commands to make the output sorted?
Example:
654321 è 654321 −−−−−−

123456 è 1−2− 3− 4− 5− 6 −

4 1 3 2 6 5 è 4 1 −3 2 − − −6 5 − −
Sorting with Stacks
(Easy) Challenge:
Devise an algorithm that can determine how to
sort a sequence with a stack, if it is possible
(and fails if it is impossible).