Stacks and Linked Lists
Stacks and Linked Lists
Stacks and Linked Lists
…
S
0 1 2 t
Array-based Stack (cont.)
• The array storing the
stack elements may
become full Algorithm push(e)
if t = S.length 1 then
• A push operation will throw FullStackException
then throw a else
FullStackException tt+1
– Limitation of the S[t] e
array-based
implementation
– Not intrinsic to the
Stack ADT
…
S
0 1 2 t
Performance and Limitations
(array-based implementation of stack ADT)
• Performance
– Let n be the number of elements in the stack
– The space used is O(n)
– Each operation runs in time O(1)
• Limitations
– The maximum size of the stack must be defined a
priori , and cannot be changed
– Trying to push a new element into a full stack causes
an implementation-specific exception
Growable Array-based Stack
• In a push operation, when Algorithm push(o)
the array is full, instead of if t = S.length 1 then
A new array of
throwing an exception, we size …
can replace the array with a for i 0 to t do
A[i] S[i]
larger one SA
• How large should the new tt+1
S[t] o
array be?
– incremental strategy:
increase the size by a
constant c
– doubling strategy: double
the size
Comparison
public:
ArrayStack(int c) : capacity(c) {
S = new Type [ capacity ];
t = -1;
}
head tail
head tail
head tail
head tail
head tail
Inserting at the Front
1. Allocate a new node
2. Have new node point to old head
3. Update head to point to new node
head tail
Raj
Inserting at the Front
1. Allocate a new node
2. Have new node point to old head
3. Update head to point to new node
4. If tail is NULL, update tail to point to the head
node head tail
Raj
Removing at the Front
head tail
head tail
head tail
head tail
head tail
head tail
Sheldon
Removing at the Front
head tail
Sheldon
Removing at the Front
head tail
Sheldon
Removing at the Front
head tail
Sheldon
Removing at the Front
Leonard Sheldon Howard
Raj
Inserting at the Back
1. Allocate a new node
2. If tail is NULL, update head and tail to point to
the new node; otherwise
1. Have the old tail point to the new node
2. Update tail to point to new node
head tail
head tail
nodes
top t
elements
Stack Summary
• Stack Operation Complexity for Different
Implementations
Array Array
Fixed-Size Expandable (doubling
Singly
Linked
strategy) List
Pop() O(1) O(1) O(1)
wrapped-around configuration
Q
0 1 2 r f
Queue Operations
• We use the Algorithm size()
return (N - f + r) mod N
modulo operator
Algorithm isEmpty()
(remainder of return (f = r)
division)
Q
0 1 2 f r
Q
0 1 2 r f
Queue Operations (cont.)
• Operation enqueue throws an Algorithm enqueue(o)
exception if the array is full if size() = N 1 then
throw FullQueueException
• This exception is
else
implementation-dependent
Q[r] o
r (r + 1) mod N
Q
0 1 2 f r
Q
0 1 2 r f
Queue Operations (cont.)
• Operation dequeue Algorithm dequeue()
throws an exception if isEmpty() then
if the queue is throw EmptyQueueException
else
empty o Q[f]
• This exception is f (f + 1) mod N
specified in the return o
queue ADT
Q
0 1 2 f r
Q
0 1 2 r f
Performance and Limitations
- array-based implementation of queue ADT
• Performance
– Let n be the number of elements in the queue
– The space used is O(n)
– Each operation runs in time O(1)
• Limitations
– The maximum size of the queue must be defined a
priori , and cannot be changed
– Trying to enqueue a new element into a full queue
causes an implementation-specific exception
Growable Array-based Queue
• In an enqueue operation, when the array is full,
instead of throwing an exception, we can
replace the array with a larger one
• Similar to what we did for an array-based stack
• The enqueue operation has amortized running
time
– O(n) with the incremental strategy
– O(1) with the doubling strategy
Exercise
head tail
head tail
head tail
Doubly Linked List Node in C++
template <class Type>
class DLinkedListNode { prev next
public:
Type elem;
DLinkedListNode<Type> *prev, *next;
elem
}; node
head tail
head tail
Bernadette
head tail
Bernadette
head tail
Bernadette
head tail
head tail
Sheldon
head tail
Adding a Node
1. Allocate a new node
2. Have new node point to the previous and next
nodes
3. Update the previous and next nodes to point to
the new node
Sheldon
head tail
Adding a Node
1. Allocate a new node
2. Have new node point to the previous and next
nodes
3. Update the previous and next nodes to point to
the new node
Sheldon
head tail
Adding a Node
1. Allocate a new node
2. Have new node point to the previous and next
nodes
3. Update the previous and next nodes to point to
the new node
head tail
Sheldon
Removing a Node
1. Have the prev node’s next point to the next of
the current node
2. Have the next node’s prev point to the prev of
the current node
3. Delete the current node
head tail
head tail
head tail
head tail
head tail
head tail
• Performance
– Let n be the number of elements in the deque
– The space used is O(n)
– Each operation runs in time O(1)
• Limitations
– NOTE: we do not have the limitation of the array
based implementation on the size of the deque b/c
the size of the linked list is not fixed, I.e., the deque is
NEVER full.
Deque Summary
• Deque Operation Complexity for Different
Implementations
Array Array List List
Fixed- Expandable Singly- Doubly-
Size (doubling strategy) Linked Linked
removeFirst(), O(1) O(1) O(1) – O(1)
removeLast() removeFirst,
O(n) –
removeLast
insertFirst(o), O(1) O(n) Worst Case O(1) O(1)
InsertLast(o) O(1) Best Case
O(1) Average Case
first(), last O(1) O(1) O(1) O(1)