So, in short you are using a BST and a FIFO linked list. Whereas, a
Stack is actually a LIFO linked list. Am i right?
On Aug 25, 11:37 pm, Don dondod...@gmail.com wrote:
You will have to keep two pointers, one to the root of the tree and
one to the head of the FIFO linked list.
To push, insert
The only way I see to be able to search in O(log n) and push/pop in
O(1) would be to have each node contain 4 pointers: left, right, and
parent pointers for the binary search tree and next pointer for the
stack linked list. The stack would be a linked list using the next
pointer, and the search
@don how will you keep track of the latest element inserted in a bst ?
O(1) for pop ? similarly how to get O(1) for push ?
Stack can be implemented with bst but the time complexity will increase.
Anyone with different views ?
On Thu, Aug 25, 2011 at 11:37 PM, Don dondod...@gmail.com wrote:
You will have to keep two pointers, one to the root of the tree and
one to the head of the FIFO linked list.
To push, insert the item into both the bst and the linked list.
To pop, set a pointer to the first item in the linked list. Delete it
from the bst. It will always be a leaf, so deleting
