Scribd
Upload
15 views2 pages

Stack Implementation: Array vs Linked List

The document outlines the implementation of stacks using arrays and linked lists, emphasizing the Last-In First-Out (LIFO) principle. It details the operations of push and pop for both implementations, along with their advantages and disadvantages. A summary of differences between the two methods is also provided, highlighting aspects such as memory allocation and size constraints.

Uploaded by

divyaraikwar0304
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views2 pages

Stack Implementation: Array vs Linked List

The document outlines the implementation of stacks using arrays and linked lists, emphasizing the Last-In First-Out (LIFO) principle. It details the operations of push and pop for both implementations, along with their advantages and disadvantages. A summary of differences between the two methods is also provided, highlighting aspects such as memory allocation and size constraints.

Uploaded by

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

STACK IMPLEMENTATION USING ARRAY & LINKED LIST

(Handwritten-Style Notes)

------------------------------------------------
STACK (LIFO)
------------------------------------------------
A stack works on Last-In First-Out rule.
Two common implementations:
1. Array
2. Linked List

================================================
1. STACK USING ARRAY
================================================

• Implemented using fixed-size array


• Uses TOP variable
• Initially TOP = -1

-------------------------
Handwritten-Like Diagram:
-------------------------
Index: 0 1 2 3 4
-----------------
Stack: |10|20|30| | |
-----------------
TOP → 2

PUSH (Insert):
• Check overflow (TOP == size-1)
• TOP++
• stack[TOP] = value

POP (Delete):
• Check underflow (TOP == -1)
• Remove stack[TOP]
• TOP--

Advantages:
• Simple, fast
• Direct indexing

Disadvantages:
• Fixed size
• Possible overflow

================================================
2. STACK USING LINKED LIST
================================================

• Uses nodes (data + next)


• TOP points to first node

-------------------------
Handwritten-Like Diagram:
-------------------------
TOP
↓
+-------+ +-------+ +-------+
| 40 | --> | 30 | --> | 20 |
+-------+ +-------+ +-------+
↓
NULL

PUSH:
• Create node
• [Link] = TOP
• TOP = node

POP:
• If TOP == NULL → underflow
• Delete TOP
• TOP = [Link]

Advantages:
• Dynamic size
• No memory wastage

Disadvantages:
• Extra pointer memory
• Slightly slower

================================================
DIFFERENCE SUMMARY
================================================
• Array = fixed; Linked = dynamic
• Array = continuous memory; Linked = nodes
• Overflow possible in array

END OF NOTES

You might also like