Stacks ADT - Linear Data Structures

“A stack is an ordered list in which all insertions and deletions are made at one end, called the top”stacks. are sometimes referred to as Last In First Out (LIFO) lists

STACK :

“A stack is an ordered list in which all insertions and deletions are made at one end, called the top”stacks. are sometimes referred to as Last In First Out (LIFO) lists

Stacks have some useful terminology associated with them:

Push To add an element to the stack

Pop To remove an element from the stock

Peek To look at elements in the stack without removing them

LIFO Refers to the last in, first out behavior of the stack

FILO Equivalent to LIFO

stack (data structure) Simple representation of a stack

Given a stack S=(a,a,.......a[n]) then we say that a1 is the bottom most element

and element a[i]) is on top of element a[i-1], 1<i<=n.

Implementation of stack :

1.       array (static memory ).

The operations of stack is

1.       PUSH operations

2.       POP operations

3.       PEEK operations

A stack S is an abstract data type (ADT) supporting the following three methods:

push(n) :     Inserts the item n at the top of stack

pop() :        Removes the top element from the stack and returns that top element. An error

occurs if the stack is empty.

peek():Returns the top element and an error occurs if the stack is empty.

1. Adding an element into a stack.  ( called PUSH operations )

Adding element into the TOP of the stack is called PUSH operation.

Check conditions :

TOP = N , then STACK FULL where N is maximum size of the stack.

Adding into stack ( PUSH algorithm )

{add item to the global stack stack ; top is the current top of stack and n is its maximum size}

begin

if top = n then stackfull; top := top+1;

stack(top) := item; Implementation in C

/* here, the variables top and size are global variables */

void push (int item)

{

if (top == size-1)

printf(“Stack        is   Overflow”);

else

{

top = top + 1; stack[top] = item;

}

}

2. Deleting an element from a stack.  (  called POP operations )

Deleting or Removing element from the TOP of the stack is called POP operations.

Check Condition:

TOP = 0, then STACK EMPTY

Deletion in stack  ( POP Operation )

procedure delete(var item : items);

{remove top element from the stack stack and put it in the item} begin

if top = 0 then stackempty; item := stack(top);

top := top-1; end; {of delete} Implementation in using array:

/* here, the variables stack, and top are global variables */

int pop ( )

{

if (top == -1)

{

printf(“Stack is Underflow”); return (0);

}

else

{

return (stack[top--]);

}

}

3. Peek Operation:

ü   Returns the item at the top of the stack but does not delete it.

ü   This can also result in underflow if the stack is empty. Algorithm:

PEEK(STACK, TOP)

BEGIN

/* Check, Stack is empty? */

if (TOP == -1) then

print “Underflow” and return 0. else

item = STACK[TOP] / * stores the top element into a local variable */

return item           / * returns the top element to the user */

END

Implementation in C using array:

/* here, the variables stack, and top are global variables */ int pop ( )

{

if (top == -1)

{

printf(“Stack is Underflow”); return (0);

}

else

{

return (stack[top]);

}

}

Applications of Stack

1.     It is very useful to evaluate arithmetic expressions. (Postfix Expressions)

2.     Infix to Postfix Transformation

3.     It is useful during the execution of recursive programs

4.     A Stack is useful for designing the compiler in operating system to store local variables inside a function block.

5.     A stack (memory stack) can be used in function calls including recursion.

6.     Reversing Data

7.     Reverse a List

8.     Convert Decimal to Binary

9.     Parsing –It is a logic that breaks into independent pieces for further processing

10.                        Backtracking

Note :

1. Infix notation   A+(B*C)

equivalent   Postfix        notation      ABC*+

2. Infix notation   (A+B)*C

Equivalent Postfix notation   AB+C*

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Related Topics