CHPT10 Basic Data structure

We can implement stack and queue using array and pointers.

Stack and Queue

Stack

Stack uses array and a pointer that indicates the top of the stack.

operations:

  1. Check empty : if the stack.top is at the beginning it is empty:
STACK_EMPTY(S):
if S.top == 0:
    return True
else:
    return False
  1. Push we can push to the top + 1 of the array We need to check if we “overflow”, if we ran out of space in the stack.
PUSH(S,x):
    if S.top + 1 > len(S): error overflow
    S.top = S.top + 1
    S[S.top] = x
  1. Pop the last element at S.top(), if the stack is empty then just return error.

Queue

Queue has insert and delete as well. They are called Enqueue and Dequeue. They follow FIFO, just like the line. The guy who first entered it will leave it first. Since the operations will happen on both side of the queue, we will need TWO pointers to keep the head and the tail. And we can allow the Queue “wrap around” in the array. The elements will consist of Q.head, Q.head + 1, Q.head + 2, Q.head + 3… Q tail – 2, Q tail – 1.
The queue is empty when Q.head == Q.tail. The queue is full when Q.head == Q.tail + 1

Implementation

  1. Enqueue(Q,x)

    Q[Q.tail] = x if Q.tail == len(Q): Q.tail = 0 #wrap around to 0 else: Q.tail = Q.tail + 1

So the Q.tail will always point to something outside of the Queue, except when the queue is full.

2.Dequeue(Q):

x = Q[Q.head()]
if Q.head == len(Q):
    Q.head = 0
else: Q.head += 1
return x



##Deque(double ended queue)
Deque allows insertation and deletion at both ends.
Deque can be used in solving this problem:
[Sliding window maximum][1]


##Problems in stack and queue

###How to implement a queue using two stacks?
Observe that when we pop an stack off and store the result in another stack, the order will be reversed.
pop S1=[1,2,3] off until empty and push then onto an empty stack S2 we get [3,2,1] and the element we want to deque, in this case, number 1 now can be poped off from S2. This might take O(n) time at worst because we have to pop S1 empty(potentially size n) to access the element at the very beginning.

###How to implement a stack using two queues.
Given two queues q1 and q2. when we push to stack we push to stack, we push to q1. When when pop, we want to access the top of the q1. We can dequeue q1 to q2 until q1 is empty and the top element will be at the very beginning of q2 and we can dequeue q2. This takes O(n) at worst



#Linked list
A linear ordered data structure where the order is determined by the pointer.
##Types
Single:where each node keeps only the next  
Double:Each node keeps prev and next  
Circular: Head node's prev = tail. tail.next = head

##Common ops
###Search element and return that node
```python
search(L, x):
    while  L.head != None:
        if x != L.value:
            L.head = L.head.next
        else: return L
```

###Insert front(x is a node
```python
insert_front(L,x):
    x.next = L.nead
    if L.head != None: L.head.prev = x
    L.head = x

Delete

Need to add in the edge case when the element found is at the beginning(L.head)

LIST-DELETE.(L,x): (x is a node)
if x.prev != None:
    x.prev.next = x.next
else:
    L.head = x.next

if x.next != None: #Not at the tail
    x.next.prev = x.prev
else:
    x.prev = None

But with the use of Dummy variable,( a nominal head) we can make the code clearer. It is called Sentinel. It reminds me of the thing in the Matrix.

Instead of using L.head to point to the first node, we use L.nil. It will lie between head and tail and L.head.prev = L.nil and L.tail.next = L.nil. Subsequently L.nil.next = L.head and L.nil.prev = tail.

If we add then in then delete would become python
delete(L,x):
node = search(L,x):
node.prev.next = node.next
node.next.prev = node.prev

Since even x is at the beginning, node.prev.next == L.nil.next and that is the head. and we update head with node.next. If node is at the very end, then node.next will be L.nil and L.nil.prev points to the end of the tail, in this case, node.prev.

Questions from the book about linked-list

in search we have two conditions: while( x!= L.nil and x.key !=k). How to shrink it to one condition check?

We can let L.nil.value = k and it will return L.nil if none is found. 2.Union 2 set S1 and S2 in O(1) time.
S1 and S2 are in doubly linked list. We want to let the end of S1 points to the start of S2. We use sentinels.\ Let l1.nil be S1’s sentinel and l2.nil be S2’s sentinel. We first let l1.nil.prev points to l2.nil.next. This let the tail of l1 points to the beginning of l2.

We then let l2.nil.next.prev = l1.nil.prev. This let the head of l2 points to the tail of l1.

We also have to let l1.nil.next.prev = l2.nil.prev. Head of l1 points to the tail of l2

And l2.prev = l1.nil.next.

We need 4 operations. It makes sense since we have to change two sentinel and each has two pointers.

How to reverse a single linked list?

First we could do this with recursion. Then non recursively

Tree

Binary tree.

We could use a ternary linked list with parent, left and right children pointer.

tree with at most k children

Each node will have k + 1 poitner, where 1 is for pointer to the parent. If you don’t have that many children, just let them point to null.

Unbounded children?

The previous implementation would break down. it breaks down because the parent has to keep track of all the children. But we could solve this by **left children, right sibling ** method. We will have three pointers in a node. one for parent and one for the left most child and one for the sibling on the right.

We lose access to all children at the parent but we can store then in O(n) space.

Questions

1

Write an O(n) time recursive procedure that, given an n-node binary tree, prints out the key of each node in the tree.

2

Write an O(n) time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node in the tree. Use a stack as an auxiliary data structure.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax