Sunday, April 6, 2014

CS131: Stack

Stack is linear list data structure which allows all operations at one end of the list. The operations are usually performed at one end called the top. The top item is inserted last. Any other item that is not at the top of the stack is not allowed to be accessed. Since we can access last item inserted in the list first stack is called to be a Last In First Out (LIFO) data structure.

Fig: Stack with top, insert and remove positions

Stack supports three operations- push, pop and top

Push operation

Inserts an item on top of the stack.

    if top >= max items allowed  //overflow
        throw error

Pop operation

Removes the item at the top from the stack and returns it.

    if top<0
        throw error

    item= stack[top]
    return item

Top operation

Returns the item at top of the stack

    if top<0
        throw error  //underflow
    return stack[top]

Stack operation example

Start with an empty stack

[    |    |     |    |     |    |     ]  top=-1


[ 15 |    |     |    |     |    |     ] top = 0


[ 15 | 18 |     |    |     |    |     ] top = 1


[ 15 | 18 |  3  |    |     |    |     ] top = 2

Pop() ---> returns 3

[ 15 | 18 |     |    |     |    |     ] top = 1

Overflow and underflow

Stack usually has an upper limit of number of items that can be inserted before we run out of memory. If we try to push an item on the stack when stack is full and no more memory can be allocated an error condition is occured. This condition is known as overflow.

Another error condition occured when the stack is empty and pop() method is called. This is called underflow.

Fixed and Dynamic stack

Stack can be implemented such that maximum amount of memory that can be used is allocated when stack in created nad this amount is fixed. This type of implementation may use a fixed array.

Another implementation may allocate memory dynamically as the stack grows and overflow occurs only when the application can no longer allocate more memory. When items are popped from the stack the extra memory may be released. This type of application may use a linked list that grows and shrinks dynamically.