ECS 32C

Introduction to Data Structures

Winter 2024 - Instructor Siena Saltzen
 Administrative
https://canvas.ucdavis.edu/courses/877554/assignments/syllabus
● No need to email me if missing class, make your best scheduling decisions
● Homework 1 Due Wed!
● SLAC NIGHT - 36C and 32B
○ Weds of Programming Hws
○ Kemper Lobby 5-7
○ 2 TAs and Various Tutors
○ I will be in and out
● I think that’s it
How to be an expert in Programing and Data Structures
What’s a data structure again?
● Data structure: how to organize your data to get the results you want, along with
the supporting algorithms

● Any storage structure for data objects may also have some operations that are
specific to the data structure

● There’s a commonly used computing name for a combination of data structure

and associated operations…

Abstract data type

Abstract data type

An abstract data type or ADT is a combination of

● a collection of data items
● a set of operations on those items

It’s abstract because it lets us ignore the implementation details of how the data
is organized or how the operations really work.
abstraction: treating something complex as if it were simpler, giving that simple
thing a name, and throwing away (or postponing) the details
"The most important concept in all of computer science is abstraction.
Computer science deals with information and complexity. We make
complexity manageable by judiciously reducing it when and where
possible."

-Guy Steele

- A guy who has played an important role in designing and documenting

several computer programming languages and technical standards.
Abstraction
 Abstraction
Abstraction is essential to managing complex software development.
Managing complexity through abstraction is kind of the whole point of object-oriented
programming
An abstract data type or ADT is a combination of
• a collection of data items
• a set of operations on those items
Formally, an ADT is a mathematical description of an object and the set of operations on
the object.
In practice, an ADT is the interface of a data structure, without any information about
the implementation
 Creating classes and objects
Think of a class definition as a blueprint…
 Encapsulation

One of the principles of good programming, and one of the principles that
object-oriented programming languages support, is that of encapsulation

-- the notion that all interaction with an object occurs through a well-defined interface.

That interface consists of methods associated with the object which operate on the data
associated with that object (the “instance data”). With rare exceptions, only the
methods associated with an object should modify the instance data of that object.
Why can't you count on the other programmers to be sure to put in the necessary
protections to prevent bad things like negative account balances? Why don't they
look out for everyone's best interest and only do the right thing?

Have you ever met other programmers?

Encapsulation

In short, the methods associated with a class do two things for

you:
1) They let you manipulate objects of that class without having to know
how those objects actually work "behind the scenes"
2) They constrain what you can do to an object so that you can’t
&$*#%@ up that object
Accessors and mutators

In support of this encapsulation idea, we provide methods in a class to

retrieve and modify variable values.
A method that retrieves data is called an accessor method because it
gives read-only access to a particular value.
A method that changes a particular value is called a mutator method
because it mutates that value.
Accessor and mutator methods are often called getters and setters,
respectively, and their names often begin with get... and set... (but not
always).
 Linear data structures

Collections of data whose items are ordered depending on how they are added
to or removed from the data structure.

• stacks

• queues

• deques

• lists

They have two ends that can be called "top" and "bottom", "front" and "back"
or "rear", "left" and "right"...all depending on how you visualize them.
 Another Way to Think

Data collections whose items are ordered depending on how they are added or
removed.

Once an item is added, it stays in that position relative to the other elements that
came before and came after it.

Common Description include FIFO & LIFO

Stack

The stack is a container for a sequential collection of data.

The stack ADT permits data to be added or deleted only at one end of
the sequence. It’s easily implemented, and is great for storing
“postponed obligations” or “postponed computations”.
Real world analogies:
Spring-loaded dish dispenser in a cafeteria
Pez candy dispenser
Dishes in your sink
Stack

Only the “top” of a stack is accessible, so the stack ADT requires very
few operations:
push(item) add to item top of stack
pop() remove item from top of stack and return it
peek() return item at top without removing it
isEmpty() return True if stack empty else False
size() return number of items on stack
Stack() create a new stack object that is empty return that new stack
1) isEmpty() Stack Behavior
○ True
2) push(A)
3) push(B)
4) peek()
○ B
5) push(C)
6) peek()
○ C C
7) pop()
○ C B
8) peek() A
○ B
9) pop()

Stack
 Stack
A stack reverses the order of arrival.
This is called last-in-first-out or LIFO behavior.
Stacks have been widely used in computing.
A compiler or interpreter may use a stack to parse expressions.
During program execution, a stack is used to keep track of procedure calls
and parameters.
It’s how recursion is handled (coming soon).
A web browser’s ‘back’ button.
Undo...
 History with Homework Relevance
Around 1972, Hewlett Packard introduced the HP-35 scientific
calculator (“the electronic slide rule”).
It used a stack to evaluate arithmetic expressions, which in turn
relied on the user to enter the expression in Reverse Polish
Notation (RPN).
RPN puts the operator after the operands, and through the
correct ordering of operators the order of operands is preserved
while the need for parentheses is eliminated. RPN is also known
as Polish postfix notation or just postfix notation.
Introduced in 1972, for $395 (equivalent of $2,503 in 2021!).
 RPN - Stack

4 * (7 + 2) becomes -> 4 7 2 + *

4 7 2 + *

What is ( ( 7 * 4 ) + 2 ) / ( 4 + 1 ) in RPN?

There are still RPN calculators and people who 2

use them. 9
7
36
4

Stack
 RPN Revisited
• Postfix form of expression
• Example
• Infix: a + (b – c) * (d + e)
• Postfix (RPN): abc-de+*+
a bc - de+ * +
• Notice how operator precedence is preserved
• Notice how order of operands is preserved
• Notice how order of operators is NOT preserved
• RPN does not require parentheses
 RPN
RPN leads to faster calculations for a couple of reasons.

One is that there is less information to store.

Therefore, instead of needing to store nine characters for the infix expression ((5–3) * 2),
computers using RPN only need to store five characters with the expression 5 3–2 *.

And because there are fewer characters to process, execution becomes faster.

So in a computer using RPN, the evaluation of the expression 5 1–3 * is as follows:

So in a computer using RPN, the evaluation of the expression 5 1–3 * is as follows:

1. Push 5 into the stack. This is the first value.

2. Push 1 into the stack. This is the second value and is on the position above the 5.

3. Apply the subtraction operation by taking two operands from the stack (1 and 5).
The top value (1) is subtracted from the value below it (5), and the result (4) is
stored back to the stack. 4 is now the only value in the stack and is in the bottom.

4. Push 3 into the stack. This value is in the position above 4 in the stack.

5. Apply the multiplication operation by taking the last two numbers off the stack and
multiplying them. The result is then placed back into the stack. After this operation,
the stack now only contains the number 12.
The infix expression ((15 ÷ (7 − (1 + 1))) × 3) − (2 + (1 + 1)) can be written like this in reverse Polish notation:

15 7 1 1 + − ÷ 3 × 2 1 1 + + −
 Homework?

Things to think about:

How do I break up the input?

What type is the input?
Which ones do I add to the stack?
How to use the stack operators?
When can I tell when the operation is completed?
 Stack implementation

A stack can be implemented as a list. We add to one end to push, and we remove from
that end to pop. Does the choice of which end matter? (Bonus Point)
What was the first thing pushed on the stack? What was the last thing? What will be the
first thing popped off the stack? (Bonus Point)
What are the details involved in pushing something on the stack? In popping something
off the stack? Are the list indexes useful here? (Bonus Point)
Array Operations
Stack operators revisited

Only the “top” of a stack is accessible, so the stack ADT requires very
few operations:
push(item) add to item top of stack
pop() remove item from top of stack don't return anything
peek() return item at top without removing it
isEmpty() return True if stack empty else False
size() return number of items on stack
Stack() create a new stack object that is empty return that new stack
Stack Operations
Stack implementation
Stack implementation

What happens if we pop from an empty stack? Can we make that

result more graceful? Should we?

Will we ever run out of stack? What will happen if we do?

Stack implementation

Here's another way to implement a stack with array.

We create a list of fixed size, then keep track of a pointer to the item at
the top of the stack.
We push by incrementing the pointer, and we pop by decrementing the
pointer. Is this better? Worse? (Bonus Point)
Reminder
 Queue

The queue is another container for a sequential collection of data. Like the stack,
it’s great for storing “postponed obligations” or “postponed computations”.
Unlike the stack, the queue ADT permits data to be added only at one end of the
sequence (the "back" or "rear") and removed from the other end (the "front").
FIFO
Real world analogies:
The waitlist to enroll in a course
The line up for a bus, or tickets at the movies, or ...
Queue

... the cars at In-n-Out Burger.

Queue

Queue operations:
enqueue(item) add to back of queue
dequeue() remove from front of queue and return it
isEmpty() return True if queue empty else False
size() return number of items in queue
Queue() create a new queue object that is empty and return that new
stack
Queue Operations
Queue implementation

Let’s Look at the book

 Queue implementation

Just like the stack, we could use a list to implement a queue. Here’s an example of
some serious queue action. First, the constructor creates an empty queue.

What is the cost

of enqueue()?
Of dequeue()?
How might you
reduce the cost
of enqueue()?
 Deque

One more linear sequential ADT.

A deque (pronounced “deck”) is a double-ended queue.
It acts like a queue, but we can add at either end and remove at either end.
A deque can also be implemented using a list or a linked list.
It is an abstraction of the queue and stack.
And now you know.
There are at least two common ways to efficiently implement a deque:
with a modified dynamic array or with a doubly linked list.
?????

Dequestions?