Chapter: Programming and Data Structures - Linear Data Structures - Stacks, Queues

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

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 ADT

 

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[1],a[2],.......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 ).

2.       linked list (dynamic memory)

 

The operations of stack is

1.       PUSH operations

2.       POP operations

3.       PEEK operations

 

The Stack ADT

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 )

procedure add(item : items);

 

{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;

end: {of add}


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


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.