Transcript iki10100i.20080318.s..

IKI 10100I: Data Structures & Algorithms
Implementing Stacks & Queues
Ruli Manurung
(acknowledgments to Denny & Ade Azurat)
Fasilkom UI
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
1
Outline
ADT: Stacks
 Basic operations
 Examples of use
 Implementations
• Array-based and linked list-based
ADT: Queues
 Basic operations
 Examples of use
 Implementations
• Array-based and linked list-based
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
2
Linear Data Structures
A collection of components that are arranged
along one dimension, i.e in a straight line, or
linearly.
Stack: a linear data structure where access is
restricted to the most recently inserted item.
Queue: a linear data structure where access is
restricted to the least recently inserted item.
Both of these abstract data types can be
implemented at a lower level using a list:
either an array or a linked list.
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
3
Stack
The last item added is pushed (added) to
the stack.
The last item added can be popped
(removed) from the stack.
The last item added can be topped
(accessed) from the stack.
These operations all take constant time:
O(1).
A typical stack interface:
void push(Thing newThing);
void pop();
Thing top();
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
4
Stack Implementation: Array
A stack can be implemented as an array
A and an integer top that records the
index of the top of the stack.
For an empty stack, set top to -1.
When push(X) is called, increment top,
and write X to A[top].
When pop() is called, decrement top.
When top() is called, return A[top].
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
5
Example
MyStack myStack = new MyStack();
myStack.push(A);
myStack.push(B);
Push A
Push B
B
A
top(0)
top(1)
A
top(-1)
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
6
Array Doubling
When array-based stack is constructed, instantiate an
array with a “default” size.
When the array underlying the stack is full (not the
stack itself!), we can increase the array through array
doubling.
Allocate a new array twice the size, and copy the old
array to the first half of the new array:
Thing[] newA = new Thing[oldA.length*2];
for(int ii=0; ii<oldA.length; ii++)
newA[ii] = oldA[ii];
oldA = newA;
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
7
Running Time
Without array doubling, all stack operations
take constant time – O(1).
With array doubling, push() may be O(N),
but this happens quite rarely: array doubling
due to data size N must be preceded by N/2
push() non-doubling calls.
Effectively, still constant time Amortization.
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
8
Stack Implementation: Array
public class MyArrayStack<T>
{
private T[] array;
private int topOfStack;
private static final int DEFAULT_CAPACITY = 10;
public
public
public
public
public
public
public
MyArrayStack() …
boolean isEmpty() …
void makeEmpty() …
T top() …
void pop() …
T topAndPop() …
void push(T x) …
private void doubleArray() …
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
9
Stack Implementation: Linked List
First item in list = top of stack (if empty: null)
push(Thing x):
 Create a new node containing x
 Insert it as the first element
pop():
 Delete first item (i.e. move “top” to the second
item)
top():
 Return the data of the first element
d
c
b
a
topOfStack
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
10
Stack Implementation: Linked List
public class MyLinkedListStack<T>
{
private ListNode<T> topOfStack;
public
public
public
public
public
public
public
MyLinkedListStack() …
boolean isEmpty() …
void makeEmpty() …
T top() …
void pop() …
T topAndPop() …
void push(T x) …
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
11
Queue
Last item added is enqueued (added) to the back.
First item added is dequeued (removed) from the front.
First item added can be accessed: getFront.
These operations all take constant time – O(1).
A typical queue interface:
void enqueue(Thing newThing);
void dequeue();
Thing getFront();
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
12
Queue Implementation: Simple Idea
Store items in an array A
Maintain index: back
Front of queue = A[0]
Back of queue = A[back]
Enqueue is easy & fast: store at A[back], back++
Dequeue is inefficient: A[1] to A[back] needs to be
shifted (and back--)  O(N)
enqueue(X)
enqueue(Y)
enqueue(Z)
dequeue()
X
X
X
Y
back
Ruli Manurung (Fasilkom UI)
Y
Y
Z
back
IKI10100I: Data Structures & Algorithms
back
Z
back
Week 7
13
Queue Implementation: Better Idea
Add another index: front, which records the front of
the queue
Dequeue is now done by incrementing front
Both enqueue and dequeue are now O(1).
enqueue(X)
enqueue(Y)
enqueue(Z)
X
Y
front
dequeue()
Z
Y
back
dequeue()
Z
front back
Z
front
back
Question: what happens if we enqueue then
dequeue array.length-1 items?
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
14
Queue Implementation: “Circular” Array
After the array.length-1-th item is
enqueued, the underlying array is full, even
though the queue is not  logically, it should
be (almost?) empty.
Solution: wraparound
Re-use cells at beginning of array that are
‘empty’ due to dequeue.
When either front or back is incremented
and points “outside array” (≥array.length),
reset to 0.
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
15
Circular Example
Both front and back indexes “wraparound” the
array. Think of the array as a circle…
P
Q
R
front
P
Q
back
front
T
P
Q
T
back
R
S
Q
back
back
T
R
S
front
front
T
front
R
S
S
back
back front
T
R
back
S
front
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
16
Java Implementation
Fairly straightforward. Basically, maintain
 Front
 Back
 Number of items in queue
When is the underlying array really full?
How do we do array doubling?
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
17
Queue Implementation: Array
public class MyArrayQueue<T>
{
private T[] array;
private int front,back,currentSize;
private static final int DEFAULT_CAPACITY = 10;
public
public
public
public
public
public
public
MyArrayQueue() …
boolean isEmpty() …
void makeEmpty() …
T getFront() …
void dequeue() …
T getFrontAndDequeue() …
void enqueue(T x) …
private void doubleQueue() …
private int increment(int x) …
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
18
Queue Implementation: Linked List
Maintain 2 node references: front & back
An empty queue: front = back = null.
enqueue(Thing X):
 Create a new node N containing X
 If queue empty: front = back = N
 Else append N and update back
dequeue():
 Delete first item (referenced by front)
getFront():
 Return data of first element
a
b
front
Ruli Manurung (Fasilkom UI)
c
d
back
IKI10100I: Data Structures & Algorithms
Week 7
19
Queue Implementation: Linked List
public class MyLinkedListQueue<T>
{
private ListNode<T> front;
private ListNode<T> back;
public
public
public
public
public
public
public
MyLinkedListQueue() …
boolean isEmpty() …
void makeEmpty() …
T getFront() …
void dequeue() …
T getFrontAndDequeue() …
void enqueue(T x) …
}
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
20
Summary
Both versions, array and linked-list, run
in O(1)
Linked-list implementation requires
extra overhead due to next reference at
each node
(Circular) array implementation of
queues can be quite tricky
Array space doubling needs memory at
least 3x size of actual data.
Ruli Manurung (Fasilkom UI)
IKI10100I: Data Structures & Algorithms
Week 7
21