Data Structures and Abstract Data Types
This content delves into the concepts of data structures, covering topics such as stacks, queues, linked lists, binary search trees, hash tables, and more. It discusses the challenges with static arrays, the benefits of dynamic arrays, and operations on stacks. Additionally, it explores abstract data types and the distinction between ADTs and data structures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Data Structures Stacks Dr. Wedad Hussein Information Systems Department wedad.hussein@cis.asu.edu.eg Dr. Asmaa Kassem Computer Science Department Asmaa.bahai@cis.asu.edu.eg Dr. Wedad Hussein Information Systems Department wedad.hussein@cis.asu.edu.eg Dr. Asmaa Kassem Computer Science Department Asmaa.bahai@cis.asu.edu.eg
Course Contents 1. Revision on classes & Pointers. Stacks Queues Array Lists Linked Lists Binary Search Trees Hash Tables STL Graphs 10. Priority Queues 2. 3. 4. 5. 6. 7. 8. 9.
Problems with Static Arrays Exceeding maximum: Choosing impossible. Declaring extremely wasteful of memory. No expansion. a real maximum is often very large arrays can be
Creating Dynamic Arrays Create a pointer to the array: int* arr = new int[5]; It points at the first element in the array. Elements are stored in consecutive positions. Use the delete operator: delete[] arr;
The Stack ADT A stack is a list with the restriction that insertions and deletions can be performed in only one position, the end of the list (LIFO).
Stack Operations Length: Returns the number of elements. Push: adds an element to the top of the stack. Pop: removes the top element. Top: returns the top element. Empty: returns whether the stack is empty.
Abstract Data Types An abstract data type (ADT) is a set of objects together with a set of operations. An ADT is fully described by a domain of values together with a set of operations to manipulate these values. E.g. set: a collection of distinct objects, Operations: add, remove, size, and contains. There is no mention on how the set of operations are implemented. ADT vs. Data Structure
Stack ADT Implementations Using Linked Lists: Top 9 8 7 Using Dynamic Arrays: Top 9 8 7 6 5
Stack Operations Length: Returns the number of elements. Push: adds an element to the top of the stack. Pop: removes the top element. Top: returns the top element. Empty: returns whether the stack is empty.
STL Standard Template Library. It is a C++ library of container classes and algorithms. It provides many of the basic algorithms and data structures of computer science.
Stack STL stack<T> Operations: empty pop push size top
2. Balancing Symbols Compilers should check whether everything is balanced. Thus, every right brace, correspond to its left counterpart. Steps: Read characters until end of file. If the character is an opening symbol, push it onto the stack. If it is a closing symbol and the stack is empty, report an error. Otherwise, pop the stack. If the symbol popped doesn t match, report an error. At end of file, if the stack is not empty, report an error. bracket, and parenthesis must
3. Call Stack On calling a function, it is important to save the address of next instruction that needs to be executed in the program. For saving a return address, it needs to be put somewhere in the memory. The conventional method is to push in to the stack. Also, a function needs to save the parameters before executing its instructions, which will also be pushed in the stack. This forms the call stack. https://www.youtube.com/watch?v=Q2sFmqvpBe0
Infix, Prefix and Postfix Expressions Infix A+B A+B*C (A+B)*C Prefix +AB +A*BC *+ABC Postfix AB+ ABC*+ AB+C*
4. Evaluating Postfix Expressions Infix Expression 6*(5+(2+3)*8+3) Equivalent to Postfix: 6 5 2 3 + 8 * + 3 + * Easier to be evaluated. Could be evaluated using a stack. Also called Reverse Polish Notation . Steps: Operands are pushed into the stack. When an operator is encountered the last 2 operands are popped and replaced with the result.
4. Evaluating Postfix Expressions cont. 6 5 2 3 + 8 * + 3 + * 3 2 5 6
4. Evaluating Postfix Expressions cont. 6 5 2 3 + 8 * + 3 + * 3 2 5 6 5 5 6
4. Evaluating Postfix Expressions cont. 6 5 2 3 + 8 * + 3 + * 8 5 5 6
4. Evaluating Postfix Expressions cont. 6 5 2 3 + 8 * + 3 + * 8 5 5 6 40 5 6
4. Evaluating Postfix Expressions cont. 6 5 2 3 + 8 * + 3 + * 40 5 6 45 6
4. Evaluating Postfix Expressions cont. 6 5 2 3 + 8 * + 3 + * 3 45 6
4. Evaluating Postfix Expressions cont. 6 5 2 3 + 8 * + 3 + * 3 48 6 45 6
4. Evaluating Postfix Expressions cont. 6 5 2 3 + 8 * + 3 + * 48 6 288
5. Infix to Postfix Conversion We can also use a stack to convert an expression in standard form into postfix. E.g. a + b * c + ( d * e + f ) * g Postfix: a b c * + d e * f + g * +
5. Infix to Postfix Conversion When an operand is read, output it When an operator is read Pop until the top of the stack has an element of lower precedence Then push it When ) is found, pop until we find the matching (. ( has the lowest precedence when in the stack but has the highest precedence when in the input. When we reach the end of input, pop until the stack is empty
Try this at home A player is playing a cards game where he draws cards from a pile. He can draw one card each round and the card is one of four options: W: gives the player 5 points, D: the double win card which gives the player 10 points, C: cancels the wins of the last round, S: the player wins the sum of the points in the last two valid rounds (that has not been cancelled). Given a sequence of cards, write a C++ function to calculate the player's final points. Use the appropriate data structure. You can use STL containers. The input is the number of rounds and a sequence of characters representing the cards.
Try this at home cont. if the input is 5 and the following sequence of values: W D W C S, the output should be 30 , this is calculated as follows: Round 1: W: the user wins 5 points, the total points become 5. Round 2: D: the user wins 10 points, the total points become 15. Round 3: W: the user wins 5 points, the total points become 20. Round 4: C: cancels the wins of round 3 which was 5 points so the points become 15. Round 5: S: wins the sum of the last two valid rounds which are round 1 and round 2 so we add 15 point to the wins and the final points are 30.
Lecture Resources Lecture Notes. Lecture Code. Text Book: Chapter 3: 3.6.
