Unformatted text preview:

StacksWhat 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: ObjectExample•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 operationsStack Interfaceint 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–topExercises•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


View Full Document

USF CS 112 - Stacks

Documents in this Course
Structs

Structs

4 pages

Trees

Trees

25 pages

Strings

Strings

27 pages

Queues

Queues

3 pages

Trees

Trees

24 pages

Arrays

Arrays

5 pages

ArrayList

ArrayList

24 pages

Stacks

Stacks

2 pages

Trees

Trees

24 pages

Stacks

Stacks

8 pages

Queues

Queues

16 pages

Queues

Queues

17 pages

Queues

Queues

17 pages

Load more
Download Stacks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Stacks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Stacks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?