Week 17
ACSL - Stacks / Queues
Announcement
Homework
Level 1
Allen Wu
Lewis Huh
Mattias Kim
Ryan Tang
Jonathan Marx
Nathan Regan
Level 3
Katelyn Phung
Andy Luo
Michael Fine
Andy Blaha
Havish Singavarapu
Level 2
Ryan Chen
Hayden Jiang
Aanya Mathur
Daniel Choi
Jerry Wang
Lucas Xue
Data Structures
Bad programmers worry about the code. Good programmers worry about data structures and their relationships.
Linus Torvalds
Examples of data structures
Stacks and Queues
Stack - LIFO (Last in - First Out)
Uses “PUSH” and “POP”
Push(element) will add element to
top of stack
Pop(X) will pop the top element from
the stack, and the element will be
stored as X in ACSL.
Commonly referred to as LIFO
Example Problem - Stack
Given an initially empty stack and the following sequence of operations, what would be the next POPPED element?
PUSH(O), PUSH(C), PUSH(E), POP(X), PUSH(A), PUSH(N), POP(X), POP(X), PUSH(S), PUSH(T), POP(X), PUSH(A), PUSH(T), PUSH(E), POP(X), POP( X)
Example Solution - Stack
Stack uses LIFO (Last in - First out), and is constructed as follows:
O, OC, OCE, OC, OCA, OCAN, OCA, OC, OCS, OCST, OCS, OCSA, OCSAT, OCSATE, OCSAT, OCSA. The next element popped is A.�
Queue - FIFO (First in - First out)
Also uses “PUSH” and “POP”
“Push” will add element to back of queue
“Pop” will pop the element at the front of
the queue, stored as X.
Referred to as FIFO, unlike stacks
Example Problem - Queue
Given an initially empty queue and the following sequence of operations, what would be the next POPPED element?
PUSH(O), PUSH(C), PUSH(E), POP(X), PUSH(A), PUSH(N), POP(X), POP(X), PUSH(H), PUSH(E), POP(X), PUSH(L), PUSH(L), PUSH(O), POP(X), POP(X)
Example Solution - Queue
Queue uses FIFO, and following FIFO rules, is constructed like this:
O, OC, OCE, CE, CEA, CEAN, EAN, AN, ANH, ANHE, NHE, NHEL, NHELL, NHELLO, HELLO, ELLO. The next item popped is E.
Kahoot
Tree
ACSL Study materials
YouTube playlist - Computer Science ACSL Review: https://www.youtube.com/watch?v=aW3qCcH6Dao&list=PLSLbUekviFje3KuOJoKdDrC6cWq0JO2sD
ACSL categories: https://www.categories.acsl.org/wiki/index.php?title=Main_Page
Before you go...