Data Structures/Stacks and Queues
From
(→Related Links) |
m (1 revision) |
Current revision as of 14:13, 9 April 2009
Data Structures
Introduction - Asymptotic Notation - Arrays - List Structures & Iterators
Stacks & Queues - Trees - Min & Max Heaps - Graphs
Hash Tables - Sets - Tradeoffs
[TODO: queue implemented as an array: circular and fixed-sized]
Contents |
Stacks and Queues
Stacks
A stack is a basic data structure that is used all throughout programming. The idea is to think of your data as a stack of plates or books where you can only take the top item off the stack in order to remove things from it.
A stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data.
Stack<item-type> Operations
push(new-item:item-type)- Adds an item onto the stack.
top():item-type- Returns the last item pushed onto the stack.
pop()- Removes the most-recently-pushed item from the stack.
is-empty():Boolean- True if no more items can be popped and there is no top item.
is-full():Boolean- True if no more items can be pushed.
get-size():Integer- Returns the number of elements on the stack.
All operations except get-size() can be performed in O(1) time. get-size() runs in at worst O(N).
Linked List Implementation
The basic linked list implementation is one of the easiest linked list implementations you can do. Structurally it is a linked list.
type Stack<item_type>
data list:Singly Linked List<item_type>
constructor()
list := new Singly-Linked-List()
end constructor
Most operations are implemented by passing them through to the underlying linked list. When you want to push something onto the list, you simply add it to the front of the linked list. The previous top is then "next" from the item being added and the list's front pointer points to the new item.
method push(new_item:item_type)
list.prepend(new_item)
end method
To look at the top item, you just examine the first item in the linked list.
method top():item_type
return list.get-begin().get-value()
end method
When you want to pop something off the list, simply remove the first item from the linked list.
method pop()
list.remove-first()
end method
A check for emptiness is easy. Just check if the list is empty.
method is-empty():Boolean
return list.is-empty()
end method
A check for full is simple. Linked lists are considered to be limitless in size.
method is-full():Boolean
return False
end method
A check for the size is again passed through to the list.
method get-size():Integer
return list.get-size()
end method
end type
A real Stack implementation in a published library would probably re-implement the linked list in order to squeeze the last bit of performance out of the implementation by leaving out unneeded functionality. The above implementation gives you the ideas involved, and any optimization you need can be accomplished by inlining the linked list code.
Performance Analysis
In a linked list, accessing the first element is an O(1) operation because the list contains a pointer dihecks for empty/fullness as done here are also O(1). depending on what time/space tradeoff is made. Most of the time, users of a Stack do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.
Since all operations are at the top of the stack, the array implementation is now much, much better.
public class StackArray implements Stack
{
protected int top;
protected Object[] data;
...
The array implementation keeps the bottom of the stack at the beginning of the array. It grows toward the end of the array. The only problem is if you attempt to push an element when the array is full. If so
Assert.pre(!isFull(),"Stack is not full.");
will fail, raising an exception. Thus it makes more sense to implement with Vector (see StackVector) to allow unbounded growth (at cost of occasional O(n) delays).
Complexity:
All operations are O(1) with exception of occasional push and clear, which should replace all entries by null in order to let them be garbage-collected. Array implementation does not replace null entries. The Vector implementation does.
Related Links
Queues
A queue is a basic data structure that is used throughout programming. You can think of it as a line in a grocery store. The first one in the line is the first one to be served.Just like a queue.
A queue is also called a FIFO (First In First Out) to demonstrate the way it accesses data.
Queue<item-type> Operations
enqueue(new-item:item-type)- Adds an item onto the end of the queue.
front():item-type- Returns the item at the front of the queue.
dequeue()- Removes the item from the front of the queue.
is-empty():Boolean- True if no more items can be dequeued and there is no front item.
is-full():Boolean- True if no more items can be enqueued.
get-size():Integer- Returns the number of elements in the queue.
All operations except get-size() can be performed in O(1) time. get-size() runs in at worst O(N).
Linked List Implementation
The basic linked list implementation uses a singly-linked list with a tail pointer to keep track of the back of the queue.
type Queue<item_type>
data list:Singly Linked List<item_type>
data tail:List Iterator<item_type>
constructor()
list := new Singly-Linked-List()
tail := list.get-begin() # null
end constructor
When you want to enqueue something, you simply add it to the back of the item pointed to by the tail pointer. So the previous tail is considered next compared to the item being added and the tail pointer points to the new item. If the list was empty, this doesn't work, since the tail iterator doesn't refer to anything
method enqueue(new_item:item_type)
if is-empty()
list.prepend(new_item)
tail := list.get-begin()
else
list.insert_after(new_item, tail)
tail.move-next()
end if
end method
The front item on the queue is just the one referred to by the linked list's head pointer
method front():item_type
return list.get-begin().get-value()
end method
When you want to dequeue something off the list, simply point the head pointer to the previous from head item. The old head item is the one you removed of the list. If the list is now empty, we have to fix the tail iterator.
method dequeue()
list.remove-first()
if is-empty()
tail := list.get-begin()
end if
end method
A check for emptiness is easy. Just check if the list is empty.
method is-empty():Boolean
return list.is-empty()
end method
A check for full is simple. Linked lists are considered to be limitless in size.
method is-full():Boolean
return False
end method
A check for the size is again passed through to the list.
method get-size():Integer
return list.get-size()
end method
end type
Performance Analysis
In a linked list, accessing the first element is an O(1) operation because the list contains a pointer directly to it. Therefore, enqueue, front, and dequeue are a quick O(1) operations.
The checks for empty/fullness as done here are also O(1).
The performance of getSize() depends on the performance of the corresponding operation in the linked list implementation. It could be either O(n), or O(1), depending on what time/space tradeoff is made. Most of the time, users of a Queue do not use the getSize() operation, and so a bit of space can be saved by not optimizing it.
Circular Array Implementation
Performance Analysis
Related Links
Deques
As a start
Data Structures
Introduction - Asymptotic Notation - Arrays - List Structures & Iterators
Stacks & Queues - Trees - Min & Max Heaps - Graphs
Hash Tables - Sets - Tradeoffs
