Stacks What is a stack Last in first out data structure LIFO New objects are placed on top Removal restricted to top object Examples Stack ADT Operations push o Insert o at top of stack Input Object Output None pop Remove top object error if empty Input None Output Object removed size Return number of objects in stack Input None Output Integer isEmpty Return a boolean indicating stack empty Input None Output Boolean top Return top object without removing error if empty Input None Output Object Example push 5 push 3 pop push 7 pop top pop pop isEmpty push 9 push 7 push 3 push 5 size pop push 8 pop pop Implementing a Stack Implementation involves writing one or more classes which provide functions to accomplish stack operations Stack Interface int size boolean isEmpty Object top throws StackEmptyException void push Object obj Object pop throws StackEmptyException Underlying Representation Array versus Linked List Pros and cons Running time size isEmpty push pop top Exercises Implement a text editor Your editor will display a string of characters and a cursor Your program will allow the user to move the cursor and modify the text using the following five operations left move the cursor to the left one character or do nothing if at the end of the line right move the cursor to the right one character or do nothing if at the end of the line rdelete n delete n characters to the right of the cursor ldelete n delete n characters to the left of the cursor insert c insert the character c just before the cursor Use 2 stacks to store the characters one to store the chars to the left of the cursor and one to store the chars to the right of the cursor
View Full Document
Unlocking...