Data Structure - Stacks

tags:
data structure and algorithms
dsa
linear data structure
stacks
push
pop
display
isempty
isfull
LIFO
FILO
array
linked list
coding
programming
C language
C
infix
prefix
postfix
towers of hanoi
tree traversal
BTECH
CSE

1. Name: Sampad Kar Student Code: BWU/BTA/22/225 Course Name: Data Structure And Algorithms Course Code: BSCM302 Group: D Session: 2023-24

2. Understanding the Stack Data Structure

3. Contents What is Stack Key Operations On a Stack Visualization Common Use Cases Implementations and Variations Advantages and Disadvantages Examples in Programming

4. What is Stack? Definition : A stack is a fundamental linear data structure that follows the Last In, First Out (LIFO) principle or First In, Last Out (FILO) Principle. It means that the last element added to the stack is the first one to be removed. Visual Representation : Imagine a stack of books on a table. We add books to the top of the stack and remove them from the same top position.

5. Push Operation: Description: Adds an element to the top of the stack. Time Complexity: O(1) - constant time complexity. Pop Operation: Description: Removes the top element from the stack. Time Complexity: O(1) - constant time complexity. Peek Operation: Key Operations On a Stack

6. Display Operation: Description: Prints or displays the contents of the stack. Time Complexity: O(n) - linear time complexity, where n is the number of elements in the stack. IsEmpty Operation: Checks if the stack is empty. IsFull Operation: Checks if the stack is full. Key Operations On a Stack

7. Visualization

8. Implementations and Variations Array-Based Implementation: Description: Stacks can be implemented using arrays. Elements are added or removed from the end of the array, representing the top of the stack. Linked List-Based Implementation: Description: Stacks can also be implemented using linked lists. Each node in the linked list represents an element in the stack.

9. Examples in Programming

10. Examples in Programming

11. Examples in Programming

12. Applications The following are the applications of stacks • Evaluating arithmetic expressions Infix To Prefix Infix To Postfix • Balancing the parenthesis • Towers of Hanoi • Function calls • Tree traversal

13. Advantages and Disadvantages Advantages: Stacks are simple and intuitive data structures, making them easy to understand and implement. Key operations such as push, pop, and peek have constant time complexity (O(1)). Disadvantages: Stacks do not support direct access to elements in the middle. Access is limited to the top element. Some stack implementations have fixed-size constraints, limiting the number of elements that can be stored.