### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Data Structures CSCI 3230

GSU

GPA 3.52

### View Full Document

## 48

## 0

## Popular in Course

## Popular in ComputerScienence

This 45 page Class Notes was uploaded by Leonor Kulas on Monday October 12, 2015. The Class Notes belongs to CSCI 3230 at Georgia Southern University taught by Debopam Acharya in Fall. Since its upload, it has received 48 views. For similar materials see /class/221982/csci-3230-georgia-southern-university in ComputerScienence at Georgia Southern University.

## Similar to CSCI 3230 at GSU

## Popular in ComputerScienence

## Reviews for Data Structures

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/12/15

Stacks and Queues LJ Stacks M4 Lecture Notes Stacks and Queues Stack l A Stack is a data structure in which new elements or nodes as they are often called can be added to a stack and removed from a stack only from one end I For this reason a stack is referred to as a LIFO structure LastIn FirstOut M4 Lecture Notes Stacks and Queues 3 Stack I A stack Lastin firstout LIFO property I The last item placed on the stack will be the first item removed 11 Analogy A stack of dishes in a cafeteria Stack of cafeteria dishes M4 Lecture Notes Stacks and Queues Operations in Stack I The main primitives of a stack are known as I Push 9 adds a new node I Pop 9 removes a node I Additional primitives can be defined It IsEmpty 9 reports Whether the stack is empty I IsFull 9 reports Whether the stack is full I Initialize 9 createsinitializes the stack Destroy 9 deletes the contents of the stack may be implemented by reinitializing the stack M4 Lecture Notes Stacks and Queues 5 Operations in Stack lnitialise Creates the structure ie ensures that the structure exists but contains no elements eg InitialiseS creates a new empty stack named S M4 Lecture Notes Stacks and Queues U Operations in Stack Push eg PushXS adds the value X to the TOP of stack 8 M4 Lecture Notes Stacks and Queues Operations in Stack Pop eg P0p removes the TOP node and returns its value M4 Lecture Notes Stacks and Queues Operations in Stack Example B A spush A spush B spush C spop nah lth fquot A 5PUSh F 3POP SPOPO 5P0P0 returns F returns B returns A Stack Implementation lThe Java Collections Framework includes a set of ready made data structure classes including a Stack class I However we will create our own stack class order to learn how a stack is implemented l Our class will be a bit simpler than the Collections Framework M4 Lecture Notes Stacks and Queues 10 Stack Implementation l A stack can be stored in U a static data structure OR u u a dynamic data structure I Static data structures u it These de ne collections of data which are xed in size when the program is compiled An array is a static data structure I Dynamic data structures l l These de ne collections of data which are variable in size and structure They are created as the program executes and grow and shrink to accommodate the data being stored M4 Lecture Notes Stacks and Queues 1 1 Stack Implementation I This Stack class stores data in an array static structure The array reference type Stack is Object which means that it can contain stack Object 11 any kind of Java object This is because of total int polymorphism every Java class is a subclass of Object Slimming pustbJect boolean I The constructor creates a new array w1th 1tS pom O inject size speci ed as a parameter The constructor does the job of the Initialize primitive described before isE m purl boolea n isFulll boolean getllte m lint Object getTotalU int I An instance variable total keeps track of how many items are stored in the stack This changes when items are added or removed The stack is full when total is the same as the size of the array M4 Lecture Notes Stacks and Queues 12 L l D Stack Implementation public class Stack private Object stack private int total to track number of items public Stackint Size stack new Objectsize create array total U set number of items to zere fir k add an item to the array public boolean push0bjeat obj if iSFull false Checks if space in stack stacktotal Obj add item total increment item counter return true to indicate success else return false to indicate failure I Stack Implementation MT VX39 remove an item by obeying LlFO rule public Object pop if isEmpty false check stack is not empty I reduce counter by one Object obj stackltotal l get last item stacktotal l null remove item from array total update total return obj return item else return null to indicate failure M4 Lecture Notes Stacks and Queues 14 Stack Implementation 7 7 checks if array is empty public boolean isEmpty if total D return true else return false xx Checks if array is full public boolean isFull if total stacklength return true return false v M4LedmeNobs SmdeandQumms 15 rilii Stack Implementation l k r returns the item at index i public Object getItemiint i return stacki 1 ith item at position i l k k return the number of items in the array public int getTotal return total M4 Lecture Notes Stacks and Queues 1 6 39 Simple Applications of Stack Checking for Balanced Braces I A stack can be used to verify whether a program contains balanced braces l An example of balanced braces abcdefgijklmnopqr l An example of unbalanced braces abcdefghijklm M4 Lecture Notes Stacks and Queues 17 Checking for Balanced Braces I Requirements for balanced braces Each time you encounter a it matches an already encountered When you reach the end of the string you have matched each M4 Lecture Notes Stacks and Queues 18 Checking for Balanced Braces Input string Stack as algorithm executes l 2 3 4 abC abC ablc 1 push quotquot 2 push quotquot 3 pop 4 pop Stack empty 2 balanced 1 push quotquot 2 push quotquot 3 pop Stack not empty 2 not balanced 1 push 2 pop Stack empty when last quot quot encountered gtnot balanced Traces of the algorithm that checks for balanced braces M4 Lecture Notes Stacks and Queues 19 U L Implementations of Stack ta l Hm Array lb 30 4 top l NJ 10 Z Linked list Implementation of the stack that use a an array b a linked list M4 Lecture Notes Stacks and Queues 20 Comparing Implementations I All of the implementations are ultimately array based or reference based I Fixed size versus dynamic size 1 An arraybased implementation I Uses xedsized arrays l l Prevents the push operation from adding an item to the stack if the stacks size limit has been reached H A referencebased implementation I Does not put a limit on the size of the stack M4 Lecture Notes Stacks and Queues 21 The Java Collections Framework Class Stack I J CF contains an implementation of a stack class called Stack generic I Derived from Vector llncludesmethods peek pop push and search M4 Lecture Notes Stacks and Queues 22 39 Application Algebraic Expressions I An algebraic expression ABC can be written in til lnfix form A B C it Postfix form A B C l l Prefix form A B C I To evaluate an infix expressions ill Convert the infix expression to postfix form U Evaluate the postfix expression M4 Lecture Notes Stacks and Queues 23 Evaluating Postfix Expressions I A postfix calculator Requires you to enter postfix expressions Example 2 3 4 When an operand is entered the calculator Pushes it onto a stack When an operator is entered the calculator Applies it to the top two operands of the stack Pops the operands from the stack The second operand will be the first element that is popped Pushes the result of the operation on the stack M4 Lecture Notes Stacks and Queues 24 Evaluatino Postfix Exoressions Key entered 2 3 4 Calculator action push 2 push 3 push 4 operand2 pop stack 4 operandl pop stack 8 result operandl operand2 U push result operand2 pop stack D operandl pop stack Q result operandl operand2 U4 push result Stack bottom to top 2 2 3 2 3 4 14 The action of a postfix calculator when evaluating the expression 2 3 4 M4 Lecture Notes Stacks and Queues 25 Converting Infix Expressions to Equivalent Postfix Expressions I An infix expression can be evaluated by first being converted into an equivalent postfix expression I Facts about converting from infix to postfix i Operands always stay in the same order with respect to one another An operator will move only to the right with respect to the operands i All parentheses are removed M4 Lecture Notes Stacks and Queues 26 b Converting Infix Expressions to Equivalent Postfix Expressions ch stack bottom to top postfixExp a a a a b ab ab c abc abc d abcd abcd Move operators abcd from stack to abcdgt postfixExp until quot quot abcd e abcde Copy operators from abcde stack to postfixExp Atrace of the algorithm that converts the infix expression a b c de to postfix form M4 Lecture Notes Stacks and Queues 27 LJ Queues M4 Lecture Notes Stacks and Queues 28 Queue I A queue W New items enter at the back or rear of the queue Items leave from the front of the queue Firstin firstout FIFO property The first item inserted into a queue is the first item toleave M4 Lecture Notes Stacks and Queues 29 Queue I queue operations i i Create an empty queue i i Determine whether a queue is empty i Add a new item to the queue i x Remove item from the queue the item that was added earliest i x Remove all the items from the queue i i Retrieve item from the queue the item that was added earliest M4 Lecture Notes Stacks and Queues 30 Queue I Queues lAre appropriate for many realworld situations Example A line to buy a movie ticket l l Have applications in computer science Example A request to print a document I A simulation l A study to see how to reduce the wait involved in an application M4 Lecture Notes Stacks and Queues 31 Queue I Another form of restricted list i 7 Insertion is done at one end whereas deletion is performed at the other end I Basic operations quotenqueue insert an element at the rear of the list dequeue delete the element at the front of the list dequeue enqueue M4 Lecture Notes Stacks and Queues 32 Enqueue and Dequeue Primary queue operations Enqueue and Dequeue Like checkout lines in a store a queue has a front and a rear Enqueue u Insert an element at the rear of the queue Dequeue u Remove an element from the front of the queue M4 Lecture Notes Stacks and Queues 33 Enqueue and Dequeue Ogeration queuecreateQueue queueenqueue5 queueenqueue2 queueenqueue7 queueFront queuepeek queueFront queuedequeue queueFront queuedequeue Some queue operations M4 Lecture Notes Stacks and Queues Queue after ogeration W Front queueFrontisS queueFrontisZ NU IU IU IUWUW 2 27 2 7queueFronti55 27 7 34 quot Queue Implementation of Array I There are several different algorithms to implement Enqueue and Dequeue I Naive way ll When enqueuing the front index is always fixed and the rear index moves fonNard in the array rear 1 rear front front front Enqueue3 M4 LectuEryh gg l ggksgand Queues Enqueue9 35 I Queue Implementation of Array I Naive way llWhen dequeuing the element at the front the queue is removed Move all the elements after it by one position Inefficient rear rear rear 1 l front front front Dequeue Dequeue Dequeue M4 Lecture Notes Stacks and Queues 36 Circular Queue Representation I An efficient queue representation can be obtained by taking an array qO n1 and treating it as if it were circular I Elements are inserted by increasing the variable rear to the next free position When rear n1 the next element is entered at qO in case the spot is free I The variable front always points one position counterclockwise from the first element in the queue I The variable front rear if and only if the queue is empty and we initially set front rear 0 NJ 14 l l iii M l l 1 plugquot I quot3 2i 3J gil tying lllx lug in mi l0 iill i mnITKJ mat4 rum 4 man 0 M4 Lecture Notes Stacks and Queues 37 Circular Queue Representation I An elegant way to insert or delete is to use the builtin modulo operator which computes reminders I Before doing an insert we increase the rear pointer by saying rear rear 1 mod n I Similarly it is necessary to move front one position clockwise each time a deletion is made I The first element in the queue is not at qfront but is one position clockwise from this point othenvise we wont be able to distinguish between the cases full and empty I This means we are allowing only n1 elements in a queue of size n M4 Lecture Notes Stacks and Queues 38 39 Enqueue and Dequeue Implementation I Algorithm Enqueueitem insert item in the circular queue stored in qOn1 rear points to the last item and front is one position counterclockwise from the first item in q rear rear 1 n Advance rear clockwise if frontrear print Queue is full if front 0 rear n1 else rearrear 1 return false else qrearitem return true M4 Lecture Notes Stacks and Queues 39 39 Enqueue and Dequeue Implementation I Algorithm Dequeueitem Removes and returns the front element of queue qOn1 if frontrear print Queue is empty return false else frontfront1 n item qfront return true M4 Lecture Notes Stacks and Queues 40 Application of Queues Recognizing Palindromes I A palindrome A string of characters that reads the same from left to right as its does from right to left I To recognize a palindrome a queue can be used in conjunction with a stack 1 A stack can be used to reverse the order of occurrences A queue can be used to preserve the order of occurrences M4 Lecture Notes Stacks and Queues 41 Recognizing Palindromes String abcbd I A nonrecursive recognition algorithm for Queue palindromes l or As you traverse the Front Back character string from left to right insert each character into both a queue and a Stad stack Compare the characters at the front of the queue and the top Of the stack The results of inserting a string into both a queue and a stack M4 Lecture Notes Stacks and Queues 42 A ReferenceBased Implementation of Queue I Possible implementations of a queue A linear linked list with two external references I A reference to the front I A reference to the back lta2gt4 V 0 V l firstNode lastNode A referencebased implementation of a queue a a linear linked list with two external references M4 Lecture Notes Stacks and Queues 43 The Java Collections Framework Interface Queue I JCF has a queue interface called Queue I Derived from interface Collection I Adds methods i element retrieves but does not remove head i of fer inserts element into queue i pee k retrieves but does not remove head i poll retrieves and removes head i remove retrieves and removes head M4 Lecture Notes Stacks and Queues 44 Comparing Implementations I All of the implementations of queue are ultimately either rArray based l Reference based I Fixed size versus dynamic size n A statically allocated array Prevents the enqueue operation from adding an item to the queue if the array is full I l A resizable array or a referencebased implementation Does not impose this restriction on the enqueue operation M4 Lecture Notes Stacks and Queues 45

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.