Scribd
Upload
51 views

Balancing of Symbols Infix To Postfix: Tower of Hanoi, Tree Traversals

1) A stack is a linear data structure that follows LIFO (Last In First Out) or FILO (First In Last Out) order. Basic operations include push to add an item, pop to remove an item from the top, peek to return the top item, and isEmpty to check if empty. 2) Common applications include balancing symbols, converting infix to postfix notation, undo-redo features, and algorithms like Tower of Hanoi and tree traversals. 3) Stacks can be implemented using arrays or linked lists. The array implementation uses a fixed-size array, top index, and overflow checking on push.

Uploaded by

Sumit Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
51 views

Balancing of Symbols Infix To Postfix: Tower of Hanoi, Tree Traversals

1) A stack is a linear data structure that follows LIFO (Last In First Out) or FILO (First In Last Out) order. Basic operations include push to add an item, pop to remove an item from the top, peek to return the top item, and isEmpty to check if empty. 2) Common applications include balancing symbols, converting infix to postfix notation, undo-redo features, and algorithms like Tower of Hanoi and tree traversals. 3) Stacks can be implemented using arrays or linked lists. The array implementation uses a fixed-size array, top index, and overflow checking on push.

Uploaded by

Sumit Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
You are on page 1/ 3

Basic Data Structure

1) Stack
It is a linear datastructure which follows a particular order in which the operations are
performed.The order may be LIFO(Last In First Out) or FILO(First IN Last Out).

--Basic Operations:
I.Push:
Add an item in the stack.If the stack is full, report stack overflow.
II. Pop:
Removes an item from the top of stack.Items are removed in the reversed order in
which they are pushed.If the stack is empty, then report “Stack Underflow”
III.Peek:
Returns the top element of stack.
IV.IsEmpty:
Returns true if stack is empty, else false.

Example:
Plates stacked over one another in a canteen. The plate at the top is removed at first,i.e
bottommost plate remains fot the longest period of time.

Applications of stack:
•Balancing of symbols

•Infix to Postfix /Prefix conversion

•Redo-undo features at many places like editors, photoshop.

•Forward and backward feature in web browsers

•Used in many algorithms like Tower of Hanoi, tree traversals, stock span

problem, histogram problem.

•Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen

problem and sudoku solver

•In Graph Algorithms like Topological Sorting and Strongly Connected Components


Implementation:

There are two ways to implement a stack:

•Using array

•Using linked list

A. Using Array:

Procedure:

structure stack:

maxsize :int

top : int

items : array of item of size maxsize

procedure initialize(stk:stack,size:int):

stk.items←new array of size items;

stk.maxsize← size

stk.top← -1 //initially empty

procedure push(stk:stack,x:item):

if(stk.top>stk.maxsize) :
Queue:
Array Implementation:

-works as FIFO basis(First In First Out ) or in first come first serve basis.

procedure:

structure queue:
final maxSize :int
front : int
[]items : is an array for queue

procedure initialize(qu:Queue,size:int)
maxSize=size
qu.items=new int array of size
front=-1 //initally empty

procedure boolean push(qu:Queue,x:item):


if qu.front==maxSize-1:
report overflow error
return false
else:
qu.items[++front]=x
return true

procedure int pop(qu.Queue):


if(qu.front==-1):
report underflow error
else:
int removed=qu.items[front]
front--
return removed

procedure boolean isEmpty(qu.Queue):


if qu.front==-1
return true
return false

You might also like