CSC 1061 Week 14 Stacks, Queues & Graphs PDF

CSC 1061 STACKS, QUEUES, GRAPHS OBJECTIVES AGENDA: WEEK 14 Follow and explain stack-based algorithms 1. Stack: LIFO using the traditional computer science terminology of push, pop, top, and peek...

CSC 1061 STACKS, QUEUES, GRAPHS OBJECTIVES AGENDA: WEEK 14 Follow and explain stack-based algorithms 1. Stack: LIFO using the traditional computer science terminology of push, pop, top, and peek Functionality Implementation & Efficiency Analyze the implementation of a stack class using an array or a linked list data structure Examples Follow and explain queue-based algorithms 2. Queue: FIFO using the traditional computer science Priority Queue terminology of enqueue and de-queue Functionality Analyze the implementation of a queue class Implementation & Efficiency using an array or a linked list data structure Examples Follow and explain graph based algorithms 3. Graphs Design and implement classes Graph Overview & Terminology for labeles and unlabeled graphs Graph Implementation Traverse through a graph using Graph Traversals & Algorithms both breadth-first and depth-first algorithms Simulate the steps of simple path algorithms STACK: LIFO (LAST IN, FIRST OUT) A stack is a sequence of items that can only be inserted or removed from one end (the top or front). It is like a stack of books The bottom one is only used if all the rest have been taken. Items are pushed onto or popped off of the stack  STACK FUNCTIONALITY: LIFO A stack typically has the following operations: push - add an item to the top of the stack. pop - get an item off the top of the stack. top - return a copy of the first item on the stack (but it remains on the stack). This lets you peek at what's on top. size - specify how many items are on the stack. isEmpty – returns boolean if the stack is empty or not. A stack typically has the following error conditions: stack overflow occurs when you try to push something onto the stack, and the stack is full. stack underflow occurs when you try to pop something off of an empty stack. STACK IMPLEMENTATION: LIFO A stack is typically implemented using an array in which elements are added (pushed on to the stack) starting at the beginning of the array. Arrays are used to implement a stack when memory is fixed and will NOT need grow beyond the initial size of the array. You can also implement a stack with a linked list, where an element is added to the front of the list (first) and then removed from the front (LIFO). Stacks that grow and shrink, should be implemented as LinkLists that can dynamically allocate and deallocate memory. STACK IMPLEMENTATION BIG(0) Array implementation is simple What is the Method Big(0) and efficient value on the top size() (1) assume a fixed capacity for of the stack? array, but if MAX is too large, isEmpty() (1) memory is wasted stack m; pop() (1) m.push(5); LinkList implementation has NO push() (1) m.push(12); size limitation m.pop(); top() (1) dynamic memory management m.push(27); Both implementations result in constant time efficiency STACK IMPLEMENTATION – ARRAY Stack data members: MAX = 6 used = 0 top = 0 used (for the number of items) 0 1 2 3 4 5 MAX (fixed-size of the stack) top (top is the index of the top element in the stack, or last element in the array, and is the same as used - 1). Start adding at index 0, then increment used and if top == max, the stack is full. myStack.push(10); MAX = 6 used = 4 top = 3 myStack.push(12); 0 1 2 3 4 5 myStack.push(15); 10 12 15 22 myStack.push(22); You do NOT move the elements around in the array when you push or pop values onto or, off of, the stack. MAX = 6 used = 2 top = 1 myStack.pop(); // remove 22 0 1 2 3 4 5 myStack.pop(); // remove 15 10 12 STACK IMPLEMENTATION: LINKLIST You can also implement a stack with a linked list, where an element is added to the front of the list (first) and then removed from the front (LIFO). 0x4b 0x72 0xe9 0x62 head myStack.push(10); data = 22 data = 15 data = 12 data = 10 0x4b myStack.push(12); next = 0x72 next = 0xe9 next = 0x62 next = 0x0 myStack.push(15); tail myStack.push(22); 0x62 head 0xe9 0x62 myStack.pop(); // remove 22 0xe9 data = 12 data = 10 myStack.pop(); // remove 15 tail next = 0x62 next = 0x0 0x62  STACK EXAMPLES A stack is used to implement undo and redo for editors. Web browser page addresses are stored on a stack. A stack can be used by a compiler to implement function calls - (call stack). Another common use for a stack would be to try to solve a problem that requires back-tracking (like a maze). A traditional use of a stack is for a calculator using RPN (Reverse Polish Notation), which is used in scientific calculators (http://www.alcula.com/calculators/rpn/)  QUEUE: FIFO (FIRST IN, FIRST OUT) A queue is a sequence of items where items are added to the end, but removed from the beginning. If you are first in line, you should be helped first. When you are helped, you are no longer in line, and removed from the queue. A queue is like standing in a line. PRIORITY QUEUES A priority queue is a queue where some entries have higher priorities and are serviced first. (Like the lines at an airline ticket counter.) A common way to implement a priority queue is with a list of queues, either an array of queues or a linked-list of queues. 0 1 2 0x91 0x62 0x4b 0x4b 0x72 0xe9 0x91 0xaa 0x54 0x88 data = X data = Y data = Z data = A data = B data = C data = D 0x62 0xc5 next = 0x72 next = 0xe9 next = 0x0 next = 0xaa next = 0x54 next = 0x88 next = 0x0 data = L data = M next = 0xc5 next = 0x0 QUEUE FUNCTIONALITY: FIFO A queue typically has the following operations: enqueue - add an item to the end of the queue. dequeue- remove the first item from the queue. first - return a copy of the first item in the queue (but it remains in the queue). i.e. "Who's first?" last - return a copy of the last item in the queue. i.e. "Who's last?" size - specify how many items are in the queue. isEmpty - returns boolean if the stack is empty or not. QUEUE IMPLEMENTATION: FIFO A queue is typically implemented using a linked-list. Elements are added to the end (the tail pointer) and removed from the beginning (the header pointer). The linked-list is unsorted in that the order is determined by the order in which elements are inserted. You can also use an array to implement a linked list, but it must be a circular array. This means that the first and last element in the array are not necessarily at index 0 and max - 1. (The concept is a little hard because you must keep track of the first and last element separately from 0 and max.) QUEUE IMPLEMENTATION BIG(0) Circular Array implementation is What are the Method Big(0) simple and efficient values left in size() (1) assume a fixed capacity for the queue? array, but if MAX is too large, isEmpty() (1) memory is wasted queue q; dequeue() (1) q.push(10); LinkList implementation has NO q.push(20); enqueue() (1) size limitation q.push(30); first() (1) dynamic memory management q.pop(); Both implementations result in last() (1) constant time efficiency QUEUE IMPLEMENTATION: CIRCULAR ARRAY Queue data members: MAX = 6 used = 6 first = 0 last = 5 used (for the number of items) 0 1 2 3 4 5 MAX (fixed-size of the stack) first (index of first item) 10 12 15 22 45 3 last (index of last item) = = Start adding after index last and removing from 3 10 index first. Increment used and keep track of first and last indexes at all times. myqueue.enqueue(10); // used:1 first:0 last:0 = = myqueue.enqueue(12); // used:2 first:0 last:1 45 12 myqueue.enqueue(15); // used:3 first:0 last:2 myqueue.enqueue(22); // used:4 first:0 last:3 myqueue.enqueue(45); // used:5 first:0 last:4 = = 22 15 myqueue.enqueue(3); // used:6 first:0 last:5 QUEUE IMPLEMENTATION: CIRCULAR ARRAY You do NOT move the elements MAX = 6 used = 4 first = 2 last = 5 around in the array when you enqueue 0 1 2 3 4 5 or dequeue values onto; or, off of, 15 22 45 3 the queue. Queue is full if used == max = = myqueue.dequeue(); // used:5 first:1 last:5 3 7 myqueue.dequeue(); // used: 4 first:2 last:5 myqueue.enqueue(7); = 45 MAX = 6 used = 5 first = 2 last = 0 0 1 2 3 4 5 = = 7 15 22 45 3 22 15 QUEUE IMPLEMENTATION: LINKLIST You can also implement a queue with a linked list, where an element is added to the end of the list (last) and then removed from the front (FIFO). 0x62 0xe9 0x72 0x4b head myqueue.enqueue(10); 0x62 data = 10 data = 12 data = 15 data = 22 myqueue.enqueue(12); next = 0xe9 next = 0x72 next = 0x4b next = 0x0 tail myqueue.enqueue(15); myqueue.enqueue(22); 0x4b head 0x72 0x4b myqueue.dequeue(); // remove 10 0x72 data = 15 data = 22 myqueue.dequeue(); // remove 12 tail next = 0x4b next = 0x0 0x4b  QUEUE EXAMPLES Queues are used whenever a program needs to behave like a line. The Unix operating system uses message queues for IPC (inter-Process Communication). Different processes add messages to the queue and typically one process reads a message from the queue, processes it, then reads the next message. File I/O uses buffering, which is kind of like a queue. Queues are often used to manage resources, like a shared printer. Queues are also extensively used (in conjunction with statistics) to model real-life situations, such as traffic flow, scheduling buses, network communication, customer service phone lines, or other staffing problems. Often you are interested in the arrival rate, average time in queue, longest time in queue, rate of service, abandon rate, … There is an entire field of study called "queueing theory"!  GRAPH DATA STRUCTURE (PROGRAMIZ) A graph data structure is a collection of nodes that have data and are connected to other nodes. Example: On Facebook, everything is a node. That includes User, Photo, Album, Event, Group, Page, Comment, Story, Video, Link, Note...anything that has data is a node. Every relationship is an edge from one node to another. Whether you post a photo, join a group, like a page, etc., a new edge is created for that relationship. All of Facebook is a collection of these nodes and edges. This is because Facebook uses a graph data structure to store its data. GRAPH TERMINOLOGY A graph is a non-linear data structure with nodes and links, however in a graph the nodes may be linked in any pattern (or even no pattern). A node is often labeled as a vertex and links are called edges. An un-directed graph is a graph where the important information being represented in the vertices and the edges that connect them is NOT important. A directed graph is a graph where the direction of the edges that connect the vertices are important. (draw arrows!) A loop is an edge that connects a vertex to itself. A path is a set of adjacent vertices that are connected with edges. In a directed graph, the path goes from a source to a target. A graph may have multiple edges or multiple links between the same two nodes. A simple graph is a graph with no loops and no multiple edges. A labeled graph is a graph that has information at the vertices. GRAPH IMPLEMENTATION A graph with no multiple edges can be implemented with an adjacency matrix. This is a table with true/false values or weighted values indicating if an edge exists. The indices of the matrix represent the vertices. A 2-dimensional array is a commonly used implementation. The video answers the question: How to determine a un-directed or directed graph based upon adjacency matrix? An adjacency list (array of linked lists) can also be used to implement a graph. Each vertex has a list of the other vertices that it is connected to. GRAPH TRAVERSALS To traverse a graph, you have to make sure all the nodes that can be reached from a given node are visited. A marked node is one that has already been visited. A depth-first traversal follows a path until it ends before backtracking and following a different path. It uses a stack to keep track of the nodes that need to be visited. Stack: LIFO (last in, first out) A breadth-first traversal visits all the nodes adjacent to a given node before moving on. It uses a queue to keep track of the nodes that need to be visited. Queue: FIFO (first in, first out) GRAPH ALGORITHMS Does a path exist? If you can traverse a graph, using either breadth-first or depth-first, starting at one node and visit the second node, then the answer is "yes". Find the shortest path. Often the edges are weighted and you will traverse a graph looking for the shortest path (based on the weights). The weight of a path is the sum of the weights of the edges. The shortest path is the one with the lowest weight. Dijkstra's algorithm is an efficient algorithm for determining the shortest path from a given vertex to every other vertex in a graph with weighted edges.