Stack Model:

Stack Model:
Stores a set of elements in a particular order Accessed in Last-In-First-Out (LIFO) fashion.


Main Stack Operations:
Push():Inserts an element on top of the stack.
Pop(): Removes and returns the last inserted element.
Auxiliary stack operations:
Top() : Returns the last inserted element without removing it.
Size(): Returns the number of elements stored on the stack..
IsEmpty(): Indicates whether no elements are stored.

Size()
return t
pop()
if isEmpty() then
Write(" UnderFlowStack")
else
return S[t ]
t ? t ? 1
push(x)
if t = S.length ? 1 then
Write( "OverFlowStack")
else
t ? t + 1
S[t] ? x
top()
if isEmpty() then
write(" UnderFlowStack")
else
return S[t ]
isEmpty() return t==0
Implementation of Stacks :
We will give two popular implementations. One uses pointers (linked list)and the other uses an array.
Linked List Stack Implementation
Benefits
• Avoids maximum stack size restriction
• Only allocates memory for stack elements actually used
How
• Allocate a node for each stack element
• Nodes are chained together by reference to next node in the chain
Array-based Stack Implementation
- Allocate array of some size ,which is the Maximum elements in
stack.
- Bottom stack element stored at index 0 .
- First index tells which element is the top .
- Increment first when element pushed, decrement when pop’d


Queue model
The Queue ADT stores arbitrary objects . Insertions and deletions follow the first-in first-out scheme .
Insertions are at the rear of the queue and removals are at the front of the queue.
Main queue operations:
- Enqueue(object): inserts an element at the end of the queue
-Object Dequeue(): removes and returns the element at the front of the queue.
Auxiliary queue operations:
-object front(): returns the element at the front without removing it.
-integer size(): returns the number of elements stored .
-boolean isEmpty(): indicates whether no elements are stored .




Array-based Queue
Use an array of size N in a circular fashion .Two variables keep track of the front and rear.
f index of the front element
r index immediately past the rear element
Array location r is kept empty





Queue Operations
We use the modulo operator (remainder of division)

size()
return (N ? f + r) mod N

isEmpty()
return (f = r)

Enqueue(x)
if size() = N ? 1 then
write ( Queue is Full )
else
Q[r] ? x
r ? (r + 1) mod N

Dequeue()
if isEmpty() then
write( Queue is Empty )
else
x ? Q[f]
f ? (f + 1) mod N
return x

Queue
Stores a set of elements in a particular order .
-Insertions and deletions follow the first-in first-out scheme
-Insertions are at the rear of the queue and removals are at the front of the queue
Main Queue Operations
En_queue(o)
Insert the object o at rear of the queue
Insert(x):
A[rear] ? x
rear ?(rear+1) mod N
Dequeue()
Remove object from front of queue
Remove():
x ? A[front]
front ?(front) mod N
return x
size( ): number of elements
isEmpty( ): size == 0?
front( ): look at object at front of queue



Array-based Queue Implementation
- Array of fixed size
- Index array element for front and rear of queue
-Indices “wrap around” when they cross end of array
List Queue Implementation
- Head and tail node references for front and rear of queue
-Insert at tail, remove from head
• Remove from tail too slow for singly linked list
-Updating tail reference with new tail takes full traversal
• So use tail of list for rear of queue