Stacks Data Structures
Mam Iram
Table of content
• Introduction
• Array based Implementation
• Creating stack
• Operations (Push, Pop, Top, Is Empty)
• Resizing stack
• Time and space complexity
• Implementation of stacks (pre -fix, in -fix, post -
fix)
• Time and space complexity
Stacks Data Structure
A stack is a linear data structure that follows the
Last In, First Out (LIFO) principle. This means
that the last element added to the stack will
be the first one to be removed.
1. Introduction to Stacks
Key Features:
– LIFO: Last-in, first-out order of operations.
– Operations are restricted to one end of the stack
called the top.
Applications: Reversing strings
• Expression evaluation and conversion (prefix,
infix, postfix)
• Function call management in recursion
• Undo operations in text editors
2. Array-Based Implementation
In an array-based implementation, a stack is
represented as a fixed-size array. A variable top is
used to keep track of the index of the topmost
element.
Steps to Implement:
Define an array to hold the stack elements.
• Initialize a variable top = -1, which represents the
top of the stack.
• The size of the stack is predefined, and resizing must
be handled explicitly.
3. Creating a Stack
• Below is a sample structure for a stack using
an array in C++:
#include <iostream>
using namespace std;
class Stack {
private:
int *arr; // Pointer to dynamically allocate array
int capacity; // Maximum size of the stack
int top; // Index of the top element
public:
// Constructor
Stack(int size) {
capacity = size;
arr = new int[capacity];
top = -1;
}
// Destructor
~Stack() {
delete[] arr;
}
// Stack operations
void push(int value);
int pop();
int peek();
bool isEmpty();
void resize();
4. Operations
Push
Adds an element to the top of the
stack.
Example:
Example:
void Stack::push(int value) {
if (top == capacity - 1)
{
resize(); // Resize if the stack is full
}
arr[++top] = value; // Increment top and insert value
}
Pop
Removes and returns the top element.
Example:
int Stack::pop()
{
if (isEmpty())
{ cout << "Stack Underflow\n";
return -1;
}
return arr[top--]; // Return the top element and decrement top
}
Peek (Top)
Returns the top element without removing it.
Example:
int Stack::peek()
{
if (isEmpty())
{
cout << "Stack is empty\n";
return -1;
}
return arr[top];
}
Is Empty
Checks if the stack is empty.
bool Stack::isEmpty()
{
return (top == -1);
}
Resizing the Stack
Dynamically increases the stack's size when it becomes full.
Example:
void Stack::resize()
{
int newCapacity = capacity * 2; // Double the capacity
int *newArr = new int[newCapacity];
for (int i = 0; i <= top; i++)
{
newArr[i] = arr[i];
}
delete[] arr; // Free old memory
arr = newArr;
capacity = newCapacity;
}
5. Time and Space Complexity
Push:
Time: O(1) for normal insertion; O(n) if resizing is needed.
Space: O(1) for normal insertion; O(n) additional space if resizing.
Pop:
Time: O(1)
Space: O(1)
Peek (Top):
Time: O(1)
Space: O(1)
Resizing:
Time: O(n) due to copying elements.
Space: O(n) additional space for a new array.
6. Implementation of Prefix, Infix, and Postfix
Stacks are often used for expression evaluation
and conversion.
Infix to Postfix Conversion
Infix expressions have operators between
operands (e.g., A + B). Postfix expressions have
operators after operands (e.g., AB+).
Steps:
Use a stack to temporarily store operators.
Output operands directly.
Pop and output operators when precedence
conditions are met.
#include <iostream>
#include <stack>
#include <string>
using namespace std;
// Function to check precedence
int precedence(char op) {
if (op == '+' || op == '-') return 1;
if (op == '*' || op == '/') return 2;
return 0;
}
// Function to convert infix to postfix
string infixToPostfix(string infix) {
stack<char> s;
string postfix = "";
for (char ch : infix) {
if (isalnum(ch)) {
postfix += ch; // Append operands directly
} else if (ch == '(') {
s.push(ch);
} else if (ch == ')') {
while (!s.empty() && s.top() != '(') {
postfix += s.top();
s.pop();
}
s.pop(); // Remove '('
} else {
while (!s.empty() && precedence(s.top()) >= precedence(ch)) {
postfix += s.top();
s.pop();
}
s.push(ch);
}
}
while (!s.empty()) {
postfix += s.top();
s.pop();
}
return postfix;
}
int main() {
string infix = "(A+B)*(C-D)";
cout << "Postfix: " << infixToPostfix(infix) << endl;
return 0;
}
7. Summary
Stack is a simple and efficient data structure with
various applications.
• Array-based implementation is easy to
understand but requires resizing for dynamic
capacity.
• Core operations (push, pop, top, and isEmpty)
are implemented in O(1) time.
• Stacks are vital for expression evaluation,
recursion, and undo functionality.
Any Question?
Thank you
