Get 2 days of unlimited access
Study Guides (350,000)
CA (140,000)
SFU (4,000)
CMPT (100)
Study Guide

CMPT 225 Study Guide - Summer 2019, Comprehensive Midterm Notes - Binary Tree, Total Order, Selection Sort


Department
Computing Science
Course Code
CMPT 225
Professor
David Mitchell
Study Guide
Midterm

This preview shows pages 1-3. to view the full 45 pages of the document.
CMPT 225

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

CMPT 225 Data Structures and Programming
The Stack ADT
Stores a collection of objects/values
Insertions and removals follow last in first out scheme
Basic Operations
Push inserts an element
Pop removes and returns last inserted element
Top returns but doesn‟t remove top
Size returns number of elements on stack
Empty returns true if size = 0
Array Based Stack Implementation
Constructor ( )
Capacity
Create new array
Set size to 0
Void Push (item)
A[size] = item
Size++
E.g. Parentheses Checking with a Stack
Input: a sequence of n tokens Output: true if parentheses correctly matched
S //a new empty stack
for I in 1 … R
if xi is „(„ ; opening character
push „(„ onto the stack
else if xI is „)‟ ;a closing character
if S is empty
return false //too few „(„
else pop a „(„ from S ;pop a token and compare to
closing just found, must match
if S is not empty //too many „(„
return false
else
return true
Essential
Non-essential
int Top ( )
Return [size -1]
T Pop ( )
Size -1
Return A[size]
Bool empty ( )
Return size == 0
-Stack based implementation is
overkill. Only need a for loop
with a counter. If ends on 0 they
are evenly matched.
-Implementation for many
symbols in highlighter
find more resources at oneclass.com
find more resources at oneclass.com

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

C++
Hello World Program
#include <iostream> - Inserts a Library of declarations and functions
Using namespace std; - avoid writing “std:: … “
main (){
cout << “ Hello World \n”; -print statement, left arrows for output, \n for new
} new line
C++ files
c.h - a header file
c.cpp - implementations of functions
To compile c++ files in command line:
g++ -c c.cpp compiles and generates c.o
g++ -c test.cpp compiles and generates test.o
g++ -o test c.o test.o creates file test for next step
./test runs program
Our Stack Class
Don‟t need a new operator to create an instance of a class in c++
x = s.pop( )
Within header file int* A; creates a pointer to an array
A = new int[capacity] //will evaluate to a pointer
ctrl click for Error! Reference source not found.
ctrl Error! Reference source not found.
#include “int_stack.h” inserts text of the header file when complied so
declarations are available, thus they only occur in one place
The ADT Queue
A queue is a collection of objects with insertions and removals satisfying first in
first out ordering, think of a pipe
removals from the front aka dequeue
insertions from the rear aka enqueue
Auxiliary operations are
front () ; size () ; empty ()
Uses „circular array‟ implementation
Must keep track of the front (where to dequeue) and rear (where to enqueue)
find more resources at oneclass.com
find more resources at oneclass.com
You're Reading a Preview

Unlock to view full version

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Que Implementation with Array
Error! Reference source not found.
Error! Reference source not found. link
Function Implementation for que:
Queue Functions
Constructor ( )
set capacity size
create array
set front, rear and size to 0
Dequeue ( )
item = A[front]
increment front %capacity
decrement size
return item
E.g. Recognizing Palindromes
push tokens onto a stack and a queue
pop off checking each popped pair for equivalence
don‟t need stack and queue if we have an array
HOWEVER, if we don‟t know the length when we start receiving tokens, need
dynamic data structure.
Big O Notation
Recall:
For 2 functions f: N N and g:N N
fi is O(g) means:
For some positive constant n0 and c
n > n0 f(n) < c*g(n)
i.e. for all but a finite set of „small‟ values (the n < n0) f(n) < c*g(n)
i.e. “f grows no faster than g as n infinity
Now:
Output not affected by input.
f(n) = O(1) if n0 , c > 0 such that n > n0 f(n) c*1 (c*1 = c)
ie f(n) < c except for some finite number of values of n, but we can choose c‟ so we don‟t
need n0
Need:
void enqueue( int item );
int dequeue();
int front();
bool empty();
int size();
Enqueue (item)
set the array at REAR to the item
increment rear counter %capacity
this accounts for circular array
increment size
Size(), empty(), front() all
return necessary values
find more resources at oneclass.com
find more resources at oneclass.com
You're Reading a Preview

Unlock to view full version