Stacks and time

This is a discussion on Stacks and time within the C++ Programming forums, part of the General Programming Boards category; I wrote the push and pop operations for my stack. I'm trying to figure out what the worst case time ...

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    46

    Stacks and time

    I wrote the push and pop operations for my stack. I'm trying to figure out what the worst case time complextiy is using asymptotic notation for these two operations is......i'm guessing Big O(log n)?..but i'm not sure..

    Code:
    void stack::push(int x){
    
      if(size < 3){
        top++;
        stackArray[size] = x;
        size++;
    
    
      }
    }
    
    int stack::pop(){
    
      int x = stackArray[top];
      top--;
      size--;
      return x;
    
    
    
    }

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,588
    Considering there are no loops or recursion, and all I see are simple comparisons, increment, assignment, decrement, I'd say the best, average and worst case complexity for both is constant time.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    ah..see what you mean. If I added an operation called peek that would look at the next item below the top of the stack... wouldn't that add more steps? How would you figure out the asymptotic time complexity. ...wouldn't it add two more steps?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,588
    If I added an operation called peek that would look at the next item below the top of the stack... wouldn't that add more steps?
    No matter how large the stack, peek (or pop and push, for that matter) would still take roughly the same number of operations.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    hmm... I don't understand

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,588
    hmm... okay, this is how I might implement the stack operations you mentioned:
    Code:
    void stack::push(int x) {
        // Implemented with fixed size array, so no expansion.
        if (size < MAX_SIZE) {
            stackArray[size] = x;
            ++size;
        }
    }
    
    void stack::pop() {
        if (size > 0) {
            --size;
        }
    }
    
    int& stack::peek() {
        return stackArray[size - 1];
    }
    
    const int& stack::peek() const {
        return stackArray[size - 1];
    }
    Look at push(). Suppose the array has no elements. We know that(size < MAX_SIZE) will be true, hence we have an assignment and an increment. Suppose the array has MAX_SIZE-1 elements. We still have an assignment and an increment. If the array has MAX_SIZE elements, the only operation performed is the comparison. So, the size of the array does not change the complexity of push().

    Look at pop(). Suppose the array has no elements. We know that (size > 0) is false, so the only operation is the comparison. Suppose the array has MAX_SIZE elements. (size > 0) is true, so besides the comparison we have a decrement. That's all, so the size of the array does not change the complexity of pop().

    For your implementation of pop() this is true as well. It does not matter how large is the array, the same sequence of:
    Code:
    int x = stackArray[top];
    top--;
    size--;
    return x;
    will be performed.

    It is clear that both non-const and const versions of peek() run in constant time since they just access the array by index, and arrays have random access.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Apr 2007
    Posts
    46
    wow that really helped me! Thanks alot.. This might be a dumb question but how many steps would it take to perform the peek operation?

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Quote Originally Posted by cjwenigma View Post
    how many steps would it take to perform the peek operation?
    Quote Originally Posted by laserlight
    peek() run in constant time since they just access the array by index, and arrays have random access.
    as mentioned, for your array implementation of the stack, accessing the first (or last, or any) index of an array is constant time, since you can jump directly to that memory location.

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If, on the other hand, you implemented the stack as a linked list, and made a "peek(x)" function that gives you the xth element, this function would be O(n), as you'd have to search through the list to find the xth element.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Looping & stacks
    By @nthony in forum C Programming
    Replies: 9
    Last Post: 06-04-2007, 04:44 PM
  2. Help With Stacks
    By penance in forum C Programming
    Replies: 7
    Last Post: 10-09-2005, 02:47 PM
  3. stacks postfix aww fooey
    By drdodirty2002 in forum C++ Programming
    Replies: 3
    Last Post: 09-25-2004, 10:00 AM
  4. stacks and queues
    By j0hnb in forum C Programming
    Replies: 4
    Last Post: 04-16-2003, 09:44 PM
  5. Stacks & Strings
    By AdioKIP in forum C++ Programming
    Replies: 2
    Last Post: 02-11-2002, 12:08 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21