Formula Sheets Stacks & Queues - Programming and Data Structures - Computer

 Page 1


Stac ks and Queues F orm ula Sheet
Stac k Basics
• Definition : LIF O (Last In, First Out) data structure.
• Op erations : Push (add to top), P op (remo v e from top), P eek (view top).
• Time Complexit y (Arra y/Link ed List) :
– Push: O(1) , P op: O(1) , P eek: O(1) .
• Space Complexit y : O(n) , where n is n um b er of elemen ts.
• Arra y Implemen tation : Fixed size S
stac k
=n·S
elemen t
, top index t , 0=t<n .
• Link ed List Implemen tation : Dynamic size, S
stac k
=n·(S
data
+S
p oin ter
) , top p oin ter.
Queue B asics
• Definition : FIF O (First In, First Out) data structure.
• Op erations : Enqueue (add to rear), Dequeue (remo v e from fron t), F ron t (view fron t).
• Time Complexit y (Arra y/Link ed List) :
– Enqueue: O(1) , Dequeue: O(1) , F ron t: O(1) .
• Space Complexit y : O(n) , where n is n um b er of elemen ts.
• Arra y Implemen tation : S
queue
=n·S
elemen t
, fron t f , rear r , circular queue a v oids space w aste.
• Link ed List Implemen tation : S
queue
=n·(S
data
+S
p oin ter
) , fron t and rear p oin ters.
T yp e s of Queues
• Circular Queue :
– Rear Index: r = (r+1) mod n .
– F ron t Index: f = (f +1) mod n .
– F ull Condition: (r+1) mod n =f .
– Empt y Condition: f =r .
• Priorit y Queue :
– Time Complexit y (Heap-Based): Insert O(logn) , Extract-Min/Max O(logn) , P eek O(1) .
– Space Complexit y: O(n) .
– Heap Prop ert y: P aren t= (or= ) c hildren for min (or max) heap.
• Double-Ended Queue (Deque) :
– Op erations: A dd/Remo v e at b oth ends, Time Complexit y O(1) .
– Arra y: S
deque
=n·S
elemen t
, circ ular buffer.
– Link ed List: S
deque
=n·(S
data
+2·S
p oin ter
) (doubly link ed).
1
Page 2


Stac ks and Queues F orm ula Sheet
Stac k Basics
• Definition : LIF O (Last In, First Out) data structure.
• Op erations : Push (add to top), P op (remo v e from top), P eek (view top).
• Time Complexit y (Arra y/Link ed List) :
– Push: O(1) , P op: O(1) , P eek: O(1) .
• Space Complexit y : O(n) , where n is n um b er of elemen ts.
• Arra y Implemen tation : Fixed size S
stac k
=n·S
elemen t
, top index t , 0=t<n .
• Link ed List Implemen tation : Dynamic size, S
stac k
=n·(S
data
+S
p oin ter
) , top p oin ter.
Queue B asics
• Definition : FIF O (First In, First Out) data structure.
• Op erations : Enqueue (add to rear), Dequeue (remo v e from fron t), F ron t (view fron t).
• Time Complexit y (Arra y/Link ed List) :
– Enqueue: O(1) , Dequeue: O(1) , F ron t: O(1) .
• Space Complexit y : O(n) , where n is n um b er of elemen ts.
• Arra y Implemen tation : S
queue
=n·S
elemen t
, fron t f , rear r , circular queue a v oids space w aste.
• Link ed List Implemen tation : S
queue
=n·(S
data
+S
p oin ter
) , fron t and rear p oin ters.
T yp e s of Queues
• Circular Queue :
– Rear Index: r = (r+1) mod n .
– F ron t Index: f = (f +1) mod n .
– F ull Condition: (r+1) mod n =f .
– Empt y Condition: f =r .
• Priorit y Queue :
– Time Complexit y (Heap-Based): Insert O(logn) , Extract-Min/Max O(logn) , P eek O(1) .
– Space Complexit y: O(n) .
– Heap Prop ert y: P aren t= (or= ) c hildren for min (or max) heap.
• Double-Ended Queue (Deque) :
– Op erations: A dd/Remo v e at b oth ends, Time Complexit y O(1) .
– Arra y: S
deque
=n·S
elemen t
, circ ular buffer.
– Link ed List: S
deque
=n·(S
data
+2·S
p oin ter
) (doubly link ed).
1
Alternativ e Implemen tations
• Stac k Using T w o Queues :
– Push: Enqueue to Q
1
, Time Complexit y O(1) .
– P op: Dequeue all but last from Q
1
to Q
2
, dequeue last, sw ap Q
1
,Q
2
, Time Complexit y O(n) .
– Space Complexit y: O(n) .
• Queue Using T w o Stac ks :
– Enqueue: Push to S
1
, Time Complexit y O(1) .
– Dequeue: If S
2
empt y , p op all from S
1
to S
2
, p op from S
2
, Time Complexit y O(n) amortized
O(1) .
– Space Complexit y: O(n) .
Expression P arsing (Infix, P ostfix, Prefix)
• Infix to P ostfix (Using Stac k) :
– Time Complexit y: O(n) , where n is expression length.
– Space Complexit y: O(n) for stac k and o utput.
– Precedence R ule: Push higher precedence op erators, p op lo w er/equal precedence.
• P ostfix Ev aluation :
– Time Complexit y: O(n) , Space Complexit y: O(n) for stac k.
– Op eration: Push op erands, p op t w o for op erator, push result.
• Prefix Con v ersion/Ev aluation : Similar to p ostfix, rev erse scan for con v ersion, Time Complexit y
O(n) .
Expression T ree
• Construction (P ostfix Expression) :
– Time Complexit y: O(n) , Space Complexit y: O(n) for tree.
– Stac k Op eration: Push op erands, p op t w o for op erator, create no de, push ro ot.
• Ev aluation : P ostorder tra v ersal, Time Complexit y O(n) .
• Heigh t of T ree: h=n , t ypically O(logn) for balanced expressions.
T o w ers of Hanoi (Stac k-Based)
• Recurrence : T(n) = 2T(n-1)+1 , where n is n um b er of disks.
• Time Complexit y : T(n) = 2
n
-1˜O(2
n
) .
• Space Complexit y : O(n) (recursiv e stac k).
• Mo v es : Minim um mo v es = 2
n
-1 .
Fib onacci Series (Stac k/Queue-Based)
• Iterativ e (Queue-Based) :
– Time Complexit y: O(n) for n -th Fib onacci n um b er.
– Space Complexit y: O(1) (t w o v ariables) or O(n) (queue for series).
– F orm ula: F
n
=F
n-1
+F
n-2
, with F
0
= 0,F
1
= 1 .
• Stac k-Based (Recursiv e) : Time Complexit y O(2
n
) , Space Complexit y O(n) , optimized with
memoization to O(n) .
2
Page 3


Stac ks and Queues F orm ula Sheet
Stac k Basics
• Definition : LIF O (Last In, First Out) data structure.
• Op erations : Push (add to top), P op (remo v e from top), P eek (view top).
• Time Complexit y (Arra y/Link ed List) :
– Push: O(1) , P op: O(1) , P eek: O(1) .
• Space Complexit y : O(n) , where n is n um b er of elemen ts.
• Arra y Implemen tation : Fixed size S
stac k
=n·S
elemen t
, top index t , 0=t<n .
• Link ed List Implemen tation : Dynamic size, S
stac k
=n·(S
data
+S
p oin ter
) , top p oin ter.
Queue B asics
• Definition : FIF O (First In, First Out) data structure.
• Op erations : Enqueue (add to rear), Dequeue (remo v e from fron t), F ron t (view fron t).
• Time Complexit y (Arra y/Link ed List) :
– Enqueue: O(1) , Dequeue: O(1) , F ron t: O(1) .
• Space Complexit y : O(n) , where n is n um b er of elemen ts.
• Arra y Implemen tation : S
queue
=n·S
elemen t
, fron t f , rear r , circular queue a v oids space w aste.
• Link ed List Implemen tation : S
queue
=n·(S
data
+S
p oin ter
) , fron t and rear p oin ters.
T yp e s of Queues
• Circular Queue :
– Rear Index: r = (r+1) mod n .
– F ron t Index: f = (f +1) mod n .
– F ull Condition: (r+1) mod n =f .
– Empt y Condition: f =r .
• Priorit y Queue :
– Time Complexit y (Heap-Based): Insert O(logn) , Extract-Min/Max O(logn) , P eek O(1) .
– Space Complexit y: O(n) .
– Heap Prop ert y: P aren t= (or= ) c hildren for min (or max) heap.
• Double-Ended Queue (Deque) :
– Op erations: A dd/Remo v e at b oth ends, Time Complexit y O(1) .
– Arra y: S
deque
=n·S
elemen t
, circ ular buffer.
– Link ed List: S
deque
=n·(S
data
+2·S
p oin ter
) (doubly link ed).
1
Alternativ e Implemen tations
• Stac k Using T w o Queues :
– Push: Enqueue to Q
1
, Time Complexit y O(1) .
– P op: Dequeue all but last from Q
1
to Q
2
, dequeue last, sw ap Q
1
,Q
2
, Time Complexit y O(n) .
– Space Complexit y: O(n) .
• Queue Using T w o Stac ks :
– Enqueue: Push to S
1
, Time Complexit y O(1) .
– Dequeue: If S
2
empt y , p op all from S
1
to S
2
, p op from S
2
, Time Complexit y O(n) amortized
O(1) .
– Space Complexit y: O(n) .
Expression P arsing (Infix, P ostfix, Prefix)
• Infix to P ostfix (Using Stac k) :
– Time Complexit y: O(n) , where n is expression length.
– Space Complexit y: O(n) for stac k and o utput.
– Precedence R ule: Push higher precedence op erators, p op lo w er/equal precedence.
• P ostfix Ev aluation :
– Time Complexit y: O(n) , Space Complexit y: O(n) for stac k.
– Op eration: Push op erands, p op t w o for op erator, push result.
• Prefix Con v ersion/Ev aluation : Similar to p ostfix, rev erse scan for con v ersion, Time Complexit y
O(n) .
Expression T ree
• Construction (P ostfix Expression) :
– Time Complexit y: O(n) , Space Complexit y: O(n) for tree.
– Stac k Op eration: Push op erands, p op t w o for op erator, create no de, push ro ot.
• Ev aluation : P ostorder tra v ersal, Time Complexit y O(n) .
• Heigh t of T ree: h=n , t ypically O(logn) for balanced expressions.
T o w ers of Hanoi (Stac k-Based)
• Recurrence : T(n) = 2T(n-1)+1 , where n is n um b er of disks.
• Time Complexit y : T(n) = 2
n
-1˜O(2
n
) .
• Space Complexit y : O(n) (recursiv e stac k).
• Mo v es : Minim um mo v es = 2
n
-1 .
Fib onacci Series (Stac k/Queue-Based)
• Iterativ e (Queue-Based) :
– Time Complexit y: O(n) for n -th Fib onacci n um b er.
– Space Complexit y: O(1) (t w o v ariables) or O(n) (queue for series).
– F orm ula: F
n
=F
n-1
+F
n-2
, with F
0
= 0,F
1
= 1 .
• Stac k-Based (Recursiv e) : Time Complexit y O(2
n
) , Space Complexit y O(n) , optimized with
memoization to O(n) .
2
Applications
• Stac k : Expression ev aluation, paren thesis matc hing, function call stac k, undo mec hanisms.
• Queue : Pro cess sc heduling, breadth-first searc h, prin ter sp o oling, buffer managemen t.
• Priorit y Queue : Dijkstra’s algorithm, task sc heduling, Huffman co ding.
• Deque: Sliding windo w problems, palindrome c hec king, undo-red o op erations.
P e rformance Metrics
• Time Complexit y Comparison :
– Stac k/Queue Op erations: O(1) for push/p op, enqueue/dequeue.
– Stac k Using Queues: O(n) p op, Queue Using Stac ks: O(n) dequeue (amortized O(1) ).
– Expression P arsing: O(n) , T o w ers of H anoi: O(2
n
) .
• Space Complexit y :
– Arra y-Based: O(n) , fixed size.
– Link ed List-Based: O(n) , dynamic with p oin ter o v erhead.
– Expression T ree: O(n) , Priorit y Queue: O(n) .
• Ov erhead :
– Arra y: W asted space in circular queue if not full.
– Link ed List: S
p oin ter
p er no de (4/8 b ytes).
• E?iciency : Arra y-based b etter cac he lo calit y , link ed list-based flexible size.
3