Scribd
Upload
22 views

Stack Data Structure

Uploaded by

pranshusahu862
Copyright
© © All Rights Reserved
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
22 views

Stack Data Structure

Uploaded by

pranshusahu862
Copyright
© © All Rights Reserved
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
You are on page 1/ 5

Stacks in Data Structures

1. Introduction to Stacks
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The element
added most recently to the stack is the first one to be removed.
Stacks are analogous to a stack of plates in a cafeteria, where the last plate placed on top is the first
one removed.

2. Basic Terminology
• Push: The operation of adding an element to the stack.
• Pop: The operation of removing the top element from the stack.
• Peek (or Top): Fetching the value of the top element without removing it.
• Underflow: A condition where a pop operation is attempted on an empty stack.
• Overflow: A condition where a push operation is attempted on a full stack (in fixed-size
implementations).

3. Representation of Stacks
Stacks can be implemented in two main ways:
1. Using Arrays:
• Fixed size.
• Requires keeping track of the top index.
2. Using Linked Lists:
• Dynamic size.
• Each node contains the data and a pointer to the next node.

4. Operations on Stacks
Below are the primary operations performed on stacks:

4.1 Push Operation


Adds an element to the top of the stack.
Algorithm:
1. Check if the stack is full (for array-based stacks).
2. If not, increment the top index and insert the element.
Code Example (C):
c
Copy code
void push(int stack[], int *top, int max, int value) {
if (*top == max - 1) {
printf("Stack Overflow\n");
} else {
*top = *top + 1;
stack[*top] = value;
}
}

4.2 Pop Operation


Removes and returns the top element of the stack.
Algorithm:
1. Check if the stack is empty.
2. If not, return the element at the top and decrement the top index.
Code Example (C):
c
Copy code
int pop(int stack[], int *top) {
if (*top == -1) {
printf("Stack Underflow\n");
return -1;
} else {
int value = stack[*top];
*top = *top - 1;
return value;
}
}

4.3 Peek Operation


Fetches the top element without removing it.
Code Example (C):
c
Copy code
int peek(int stack[], int top) {
if (top == -1) {
printf("Stack is Empty\n");
return -1;
} else {
return stack[top];
}
}

5. Stack Applications
Stacks are widely used in various domains, including:
1. Expression Evaluation:
• Used in converting infix expressions to postfix or prefix.
• Evaluating postfix expressions.
2. Backtracking:
• For example, in solving maze problems, the last attempted path is retried.
3. Undo/Redo Operations:
• Used in text editors where the last action is undone or redone.
4. Call Stack:
• Manages function calls in programming.
5. Parenthesis Matching:
• Used to check for balanced parentheses in expressions.

6. Array-Based Implementation of Stacks


In this implementation:
1. The stack is represented as an array.
2. A variable (top) keeps track of the index of the top element.

Advantages:
• Simplicity.
• Efficient for fixed-size stacks.
Disadvantages:
• Fixed size may lead to stack overflow.

7. Linked List-Based Implementation of Stacks


In this implementation:
1. Each node contains two fields: data and a pointer to the next node.
2. The head pointer represents the top of the stack.
Advantages:
• Dynamic size; no fixed capacity.
Disadvantages:
• Extra memory required for pointers.
Code Example (C):
c
Copy code
struct Node {
int data;
struct Node* next;
};
void push(struct Node** top, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *top;
*top = newNode;
}

int pop(struct Node** top) {


if (*top == NULL) {
printf("Stack Underflow\n");
return -1;
} else {
struct Node* temp = *top;
int value = temp->data;
*top = (*top)->next;
free(temp);
return value;
}
}

8. Stack Operations for Expression Evaluation


8.1 Infix to Postfix Conversion
Rules:
1. Operands are written in the same order.
2. Operators are pushed onto the stack.
3. Parentheses are handled with priority.

8.2 Postfix Expression Evaluation


Using a stack:
1. Push operands onto the stack.
2. When an operator is encountered, pop two elements, apply the operator, and push the result
back.

9. Complexity Analysis
Operation Time Complexity
Push O(1)
Pop O(1)
Peek O(1)

10. Applications in Real Life


1. Reversal of Strings:
• Stacks are used to reverse strings by pushing characters onto the stack and popping
them in reverse order.
2. Web Browsing History:
• The backtracking feature in web browsers uses a stack to manage the history of
visited pages.

You might also like