Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | 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

**Related Topics **

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