程序代写代做 data structure ADT Review and Stacks

ADT Review and Stacks
Daniel Archambault
CS-115: ADT Review and Stacks
1

Previously in CS-115
tail
next element
next element
next element
null
head
Obj.
Linked Lists: Know the Ends. Know how to get to the middle.
Obj.
Obj.
CS-115: ADT Review and Stacks
2

Previously in CS-115
What are the two attributes of Link in a linked list?
CS-115: ADT Review and Stacks
3

Previously in CS-115
What are the two attributes of Link in a linked list? What are the two attributes of a linked list?
CS-115: ADT Review and Stacks
3

Previously in CS-115
What are the two attributes of Link in a linked list? What are the two attributes of a linked list?
Name an advantage of a linked list?
CS-115: ADT Review and Stacks
3

Previously in CS-115
What are the two attributes of Link in a linked list? What are the two attributes of a linked list?
Name an advantage of a linked list?
Name a disadvantage of a linked list?
How do you get to an item that is not the ends? Can queues be implemented using arrays?
CS-115: ADT Review and Stacks
3

Previously in CS-115
We now look at an ADT and a possible implementation.
Stacks
CS-115: ADT Review and Stacks
4

More about ADTs
Implementation not specified!
ADT specifies the behaviour of the software construct The data structure implements those behaviours
􏰀 Which data structures do we have to implement a Queue? For ADTs, think about state and operations on the state
􏰀 don’t think about main or the rest of the program
CS-115: ADT Review and Stacks
5

A Stack Interface
Last in First Out
public interface Stack {
public boolean isEmpty ();
public void push (Object newItem); public void pop ();
public Object peek ();
}
CS-115: ADT Review and Stacks
6

isEmpty behaviour
Returns true if there are zero elements in the stack
Otherwise, returns false
12
51
17
(a) true (b) false
CS-115: ADT Review and Stacks
7

push behaviour
Adds an item to the top of the stack
8
12
12
51
51
17
17
(c) before (d) after push push of 8
CS-115: ADT Review and Stacks
8

pop behaviour
Removes an item from the top of the stack
12
51
51
17
17
(e) before pop (f) after pop 12
CS-115: ADT Review and Stacks
9

peek behaviour
Returns the top element of the stack
12
51
17
(g) returns 12
CS-115: ADT Review and Stacks
10

Implementation of Stack
To turn a ADT Stack into a Stack data structure we can choose either an array/ArrayList, or linked list
􏰀 both linked list and array/ArrayList are about same difficulty I’ll explain this implementation with a linked list first
Then an ArrayList second
CS-115: ADT Review and Stacks
11

Attributes of Stack Implemented with Linked List
public class Stack { private Link head; private Link tail;
public Stack () { head = null; tail = null;
} }
CS-115: ADT Review and Stacks
12

isEmpty implementation
Returns true if there are zero elements in the stack Otherwise, returns false
Really, could just check head, but this prevents bugs
…
return ((this.head == null) && (this.tail == null)); …
CS-115: ADT Review and Stacks
13

push implementation
Adds an item to the top of the stack
It is the end of the linked list
If tail is null, you need to set head and tail…
…
Link newNode = new Link (element, head); this.head = newNode;
…
CS-115: ADT Review and Stacks
14

pop implementation
Removes an item from the top of the stack
Simply remove the link from the back
…
if this.isEmpty () {
throw new NoSuchElementException (); }
this.head = this.head.next; …
Check if tail is null. If so, set head null. (stack empty)
CS-115: ADT Review and Stacks
15

peek behaviour
Returns the top element of the stack
…
if this.isEmpty () {
throw new NoSuchElementException (); }
return this.head.element; …
CS-115: ADT Review and Stacks
16

Implementation of Stack: ArrayList
ADT says nothing about how implemented
It only specifies what is implemented.
We can also implement a stack with an ArrayList
􏰀 Why is this easier than using an array?
CS-115: ADT Review and Stacks
17

Attributes of Stack Implemented with ArrayList
I’m using generics because it is convenient
Object can also be used. public class Stack {
private ArrayList stack;
public Stack () {
this.stack = new ArrayList ();
} }
CS-115: ADT Review and Stacks
18

isEmpty implementation
Returns true if there are zero elements in the stack Otherwise, returns false
Just check the size of the array list
public boolean isEmpty () { return this.stack.size () == 0;
}
could also use isEmpty () of ArrayList.
CS-115: ADT Review and Stacks
19

push implementation
Adds an item to the top of the stack
Just use the add operation provided
public void push (T e) { this.stack.add (e);
}
CS-115: ADT Review and Stacks
20

pop implementation
Removes an item from the top of the stack
Use the remove method to delete last element
public void pop () {
if (this.stack.isEmpty ()) {
throw new NoSuchElementException (); }
this.stack.remove (this.stack.size () – 1);
}
CS-115: ADT Review and Stacks
21

peek behaviour
Returns the top element of the stack
public T peek () {
if (this.stack.isEmpty ()) {
throw new NoSuchElementException (); }
return this.stack.get (this.stack.size() – 1);
}
CS-115: ADT Review and Stacks
22

Related Posts