Please enable JavaScript.

Coggle requires JavaScript to display documents.

Stacks, Queues - Coggle Diagram

- - - - this is Particularly effective when elements are taken from one stack and given to the other. If instead both stacks grow at the same time, then the free space in the middle of the array will be exhausted quickly
- - - - As with lists, there are many variations on stack implementation. The two ap- proaches presented here are array-based and linked stacks, which are analogous to array-based and linked lists, respectively.
        
        Array Based Stacks
        
        the array-based stack implementation is essentially a simplified version of the array-based list. The only important design decision to be made is which end of the array should represent the top of the stack
        
        The other choice is have the top element be at position n − 1 when there are n elements in the stack. In other words, as elements are pushed onto the stack, they are appended to the tail of the list. Method pop removes the tail element. In this case, the cost for each push or pop operation is only Θ(1). For the implementation of Figure 4.18, top is defined to be the array index of the first free position in the stack. Thus, an empty stack has top set to 0, the first available free position in the array
        
        Methods push and pop simply place an element into, or remove an element from, the array position indicated by top. Because top is assumed to be at the first free position, push first inserts its value into the top position and then increments top, while pop first decrements top and then removes the top element.
        
        Linked Stacks
        
        Elements are inserted and removed only from the head of the list. A header node is not used because no special-case code is required for lists of zero or one elements
        
        Methods
        
        Push
        
        he only data member is top, a pointer to the first (top) link node of the stack. Method push first modifies the next field of the newly created link node to point to the top of the stack and then sets top to point to the new link node.
        
        Pop
        
        Method pop is also quite simple. Variable temp stores the top nodes’ value, while ltemp links to the top node as it is removed from the stack. The stack is updated by setting top to point to the next link in the stack. The old top node is then returned to free store (or the freelist), and the element value is returned
        
        Create
        
        Algorithm: Stack create stack()
        
        1 s.top ← NULL;
        
        2 s.size ← 0;
        
        3 return s;
- - - - Algorithm: E dequeue(Queue q)
      - 1 if q.size = 0 then error;
      - 2 it ← q.front.next.element;
      - 3 q.front.next ← q.front.next.next;
      - 4 if q.front.next = NULL then q.rear ← q.front;
      - 5 q.size-- ;
      - 6 return it;