Thread: Stack::push

  1. #1
    Registered User
    Join Date
    Jan 2004
    Posts
    22

    Stack::push

    This is the struct Stack:

    Code:
    struct Stack {
      struct Link {
        void* data;
        Link* next;
        void initialize(void* dat, Link* nxt);
      }* head;
      void initialize();
      void push(void* dat);
      void* peek();
      void* pop();
      void cleanup();
    };
    Here is the definitions of functions push() and initialize() of struct Stack:

    Code:
    void Stack::push(void* dat) {
      Link* newLink = new Link;
      newLink->initialize(dat, head);
      head = newLink;
    }
    
    void Stack::Link::initialize(void* dat, Link* nxt) {
      data = dat;
      next = nxt;
    }
    This is a comment on push():

    " (1) The next pointer is assigned to the current head. (2) Then head is assigned to the new Link pointer. (3) This effectively pushes the Link in at the top of the list. "

    I don't understand how (1) and (2) cause (3) to happen. Please explain.

    Thanks for your interest.
    Last edited by kasun; 02-22-2004 at 12:03 PM.

  2. #2
    Registered User
    Join Date
    Feb 2004
    Posts
    46
    Consider a stack.
    Code:
    head
    |
    5->4->3
    You want to push 6. Following the algorithm.

    Link* newLink = new Link;
    newLink->initialize(dat, head);

    This creates 6 and sets its next pointer to point to 5, so we have this stack.
    Code:
       head
       |
    6->5->4->3
    head = newLink;

    Now the algorithm sets head, which is 5, to point to 6. The result is thus.
    Code:
    head
    |
    6->5->4->3

  3. #3
    Registered User
    Join Date
    Jan 2004
    Posts
    22
    Thanks.
    But, could you please be little more specific about how

    Code:
    newLink->initialize(dat, head);
    points head to 5 and then

    Code:
    head = newLink;
    points head back to 6 ?

  4. #4
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    newLink->initialize(dat, head);



    points head to 5 and then
    It doesn't. It points the next pointer of 6 to 5.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  5. #5
    Registered User
    Join Date
    Feb 2004
    Posts
    46
    You're looking at a simple assignment of pointers. With the complexity of an explicit constructor call removed, the code would look like this.
    Code:
    void Stack::Push(void* dat) {
      Link* newLink = new Link;
      newLink->data = dat;
      newLink->next = head; // newLink points to head
      head = newLink; // newLink becomes head
    }
    Those operations are consistent with the diagrams I gave you previously. Please note that this is not as much an issue of the stack abstraction as a general linked list paradigm. Adding to the front of a singly linked list is a fundamental operation and you should be familiar with it.
    Code:
    #include <iostream>
    
    using std::cout;
    using std::endl;
    using std::cin;
    
    struct node {
        int cont;
        node *next;
    };
    
    int main()
    {
        node *head = 0; // Null to mark the end of the list
        int input;
    
        while (cin>> input) {
            node *add = new node; // Allocate space for a new node
            add->cont = input; // Set the content
            add->next = head; // Set the next pointer to be the head of the list
            head = add; // Reseat the head of the list to the new node
        }
        while (head != 0) {
            node *save = head->next;
            cout<< head->cont <<' ';
            delete head;
            head = save;
        }
        cout<<endl;
    }

Popular pages Recent additions subscribe to a feed