Data structures and algorithms lab3

67 %
33 %
Information about Data structures and algorithms lab3

Published on March 1, 2014

Author: Bii03



OBJECTIVES Template functions  Template classes  Stack  Applications of stack 

TEMPLATES ‼Short reminder: why do we need templates? Study ex1.cpp: KeyStorage class from the previous lab  Pay attention to the way of defining the class methods 

TEMPLATES ‼Template functions: we can also use templates when we work in a procedural fashion.  Study ex2.cpp and ex2_swap.cpp

STACK  instance of an abstract data type (ADT) that formalizes the concept of restricted collection (LIFO = last in first out)  ADT vs. Data Structures: ADT is in the logical level and data structure is in the implementation level: ADT: the stack itself  Data Structure: the stack implemented with an array 

STACK: ACCESS TO ELEMENTS ‼ In a stack, all the operations take place at the top of the top of the stack. Consequently, we can have access to stack elements only through the top of the stack.

STACK: BASIC OPERATIONS  push(x)   Adds the element x at the top of the stack pop() Removes the element from the top of the stack and returns it  Returns an error if the stack is empty 

STACK: BASIC OPERATIONS  peek()  Returns (but does not remove) the element at the top of the stack  isEmpty()  Returns 1 if the stack is empty and 0 otherwise

STACK: ARRAY-BASED IMPLEMENTATION  Study stack_basic.cpp  Test the basic operations for a stack of char elements  Implement the following functionalities:  display all the elements of a stack  sort the elements of the stack Test the new methods!

STACK: APPLICATIONS ‼Exercise: Implement a class named LargeStack which can stock two arbitrary values of type T (use class templates). The class can have just two members: Stack<T> Smain, Saux; Smain is the main stack which allows stocking the values added to LargeStack.  Saux is the auxiliary stack which has to be empty before and after the call to a function of LargeStack class.  LargeStack class has the following main functions:  void push(T x): add an element x to the top of the Smain stack  T pop() : delete and return the element of the top of Smain stack  void swap(int i): exchange the values from level i and j of Smain stack. The levels are numbered starting with 0. If an error occurs, the stack won’t be modified. You can use Saux stack for temporary stocking of any values you want.

HOMEWORK  Finish all the lab exercises.  Using a stack, implement an algorithm for converting a number from a base to another base. For instance, 510 = 1012 .  Using a stack, check whether a given string is palindrome or not.

Add a comment

Related presentations

Related pages

3. Algorithms and data structures - KTH

2D1257: Visualization 3. Algorithms and data structures April 2, 2007 Introduction Methods and algorithms that we will familiarize ourselves with in this ...
Read more

Data Structures And Algorithms Lab Manual

Data Structures And Algorithms Lab Manual ... resources, you can find data structures. algorithms and applications in c++ 2nd edition. Review: ...
Read more

Data structures and Algorithms | Comp 15 - Data Structures

Data-structures Data structures and Algorithms. ... Data structure: ... Programs = Algorithms + Data structures -Niklaus Wirth
Read more

Data Structures, Algorithms | LinkedIn

View 645 Data Structures, Algorithms posts, presentations, experts, and more. Get the professional knowledge you need on LinkedIn. LinkedIn Home
Read more

Assignments — Problem Solving with Algorithms and Data ...

Problem Solving with Algorithms and Data Structures using Python by Bradley N. Miller, ...
Read more

Data Structures And Algorithms Lab Manual For Me Cse

Data Structures And Algorithms Lab Manual For Me Cse ME NOTES CP7102, Advanced Data Structures and Algorithms, Click Here CP7111, Advanced Data Structures ...
Read more

Algorithms and Data Structures

Algorithms and Data Structures Fall 2007 Robert Sedgewick and Kevin Wayne Department of Computer Science Princeton University Princeton, NJ 08544
Read more

Lab3 - DePaul University

CSC 300 Data Structures in Java I: Lab 3 (11/7 Thu) In this lab session, you do an empirical test of performance comparison of various sorting algorithms.
Read more