Stacks

By Notes Vandar

2.1 Definition

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. It operates like a pile of items where only the topmost item can be accessed, added, or removed.

Key Operations of a Stack:

  1. Push: Add an element to the top of the stack.
  2. Pop: Remove and return the top element from the stack.
  3. Peek/Top: View (but not remove) the top element of the stack.
  4. isEmpty: Check if the stack is empty.
  5. isFull (for fixed-size stacks): Check if the stack is full.

Example:

Imagine a stack of plates:

  • When you add a plate, it goes on top (push).
  • When you remove a plate, you take the top one (pop).
  • The only plate you can see or remove is the one on top (peek).

Real-Life Examples:

  • Undo functionality in text editors (last action is the first to be undone).
  • Browser history (last visited page is the first to be revisited).

Visual Representation:

Stack: [3, 5, 7]
Top -> 7
  • Push(9): Add 9 to the stack: [3, 5, 7, 9]
  • Pop(): Remove 9: [3, 5, 7]
  • Peek(): Top element is 7.

2.2 Stack as an ADT

A Stack is an Abstract Data Type (ADT) because it defines a collection of elements and a set of operations that can be performed on these elements, without specifying how these operations are implemented. The stack ADT provides a logical description of the data structure and its behavior, abstracting away the underlying details of how the data is stored or managed.

In the case of the stack ADT, the following fundamental operations are defined, based on the Last In, First Out (LIFO) principle:

Stack ADT Operations

  1. Push(element):
    • Description: Adds a new element to the top of the stack.
    • Input: The element to be added.
    • Output: None.
    • Precondition: The stack is not full (if it’s a fixed-size stack).
    • Postcondition: The new element is added to the top.
  2. Pop():
    • Description: Removes and returns the element from the top of the stack.
    • Input: None.
    • Output: The top element of the stack.
    • Precondition: The stack is not empty.
    • Postcondition: The top element is removed, and the next element becomes the new top.
  3. Peek()/Top():
    • Description: Returns the element at the top of the stack without removing it.
    • Input: None.
    • Output: The top element of the stack.
    • Precondition: The stack is not empty.
    • Postcondition: The stack remains unchanged.
  4. isEmpty():
    • Description: Checks if the stack is empty.
    • Input: None.
    • Output: true if the stack is empty, otherwise false.
    • Precondition: None.
    • Postcondition: None (the stack remains unchanged).
  5. isFull() (optional for fixed-size stacks):
    • Description: Checks if the stack is full.
    • Input: None.
    • Output: true if the stack is full, otherwise false.
    • Precondition: None.
    • Postcondition: None (the stack remains unchanged).

Stack ADT Properties

  • Linear Structure: Stack elements are ordered in a linear manner, and new elements are always added to or removed from one end (the top).
  • LIFO Principle: The last element added is the first one to be removed.
  • Restricted Access: Unlike other linear structures like arrays, only the topmost element can be accessed, added, or removed.

Stack ADT in Different Implementations

The stack ADT can be implemented in different ways, but its behavior and interface remain the same. Some common implementations are:

  1. Array-based Stack: Uses a fixed-size array to store elements. The push and pop operations involve adding/removing elements from the top index of the array.
  2. Linked List-based Stack: Uses a dynamic linked list where each node points to the next. The top element is represented by the head of the linked list.

Stack ADT Interface Example in Pseudocode:

Stack ADT:
Data: A collection of elements stored in a stack structure.

Methods:
1. Push(element)
Input: element to be added to the top of the stack
Output: None
Precondition: The stack is not full (in case of fixed-size implementation)

2. Pop()
Input: None
Output: The top element of the stack
Precondition: The stack is not empty

3. Peek()
Input: None
Output: The top element without removing it
Precondition: The stack is not empty

4. isEmpty()
Input: None
Output: True if the stack is empty, False otherwise

5. isFull() (for fixed-size stack)
Input: None
Output: True if the stack is full, False otherwise

Example: Stack ADT Usage

Imagine a browser’s back button:

  • Push: Each time you visit a new page, the URL is pushed onto the stack.
  • Pop: When you click the back button, the most recent URL is popped from the stack, and the browser takes you to the previous page.
  • Peek: When you hover over the back button, the top URL can be shown (without removing it from the stack).
  • isEmpty: When there is no more history to go back to, the stack is empty.

 

2.3 Stack Operations

A stack is a linear data structure that operates on the Last In, First Out (LIFO) principle, where the last element added to the stack is the first one to be removed. In this section, we will focus on the essential operations that can be performed on a stack.

Basic Operations in a Stack

  1. Push
    Description: Adds an element to the top of the stack.

    • Input: An element to be added.
    • Output: None.
    • Behavior: The new element is placed on top of the stack, increasing the size of the stack by one.

    Example:

    Stack before Push: [10, 20, 30] (Top -> 30)
    Push(40)
    Stack after Push: [10, 20, 30, 40] (Top -> 40)
  2. Pop
    Description: Removes and returns the top element from the stack.

    • Input: None.
    • Output: The top element of the stack.
    • Behavior: The top element is removed, and the next element below it becomes the new top. The size of the stack is reduced by one.

    Example:

    Stack before Pop: [10, 20, 30, 40] (Top -> 40)
    Pop()
    Output: 40
    Stack after Pop: [10, 20, 30] (Top -> 30)
  3. Peek (or Top)
    Description: Returns the top element of the stack without removing it.

    • Input: None.
    • Output: The top element of the stack.
    • Behavior: The element at the top of the stack is returned, but the stack remains unchanged.

    Example:

    Stack: [10, 20, 30] (Top -> 30)
    Peek()
    Output: 30
  4. isEmpty
    Description: Checks whether the stack is empty.

    • Input: None.
    • Output: Returns true if the stack is empty, otherwise returns false.
    • Behavior: This operation checks the size of the stack. If the stack has no elements, it returns true; otherwise, it returns false.

    Example:

    Stack: []
    isEmpty()
    Output: true
  5. isFull (Optional for fixed-size stacks)
    Description: Checks whether the stack is full (in case of a fixed-size stack).

    • Input: None.
    • Output: Returns true if the stack is full, otherwise returns false.
    • Behavior: This operation checks whether the stack has reached its maximum capacity.

    Example:

    Stack: [10, 20, 30, 40] (Max size = 4)
    isFull()
    Output: true

Additional Operations (Optional)

  1. Size
    Description: Returns the number of elements in the stack.

    • Input: None.
    • Output: The current size of the stack.
    • Behavior: This operation returns the total number of elements present in the stack.

    Example:

    Stack: [10, 20, 30]
    Size()
    Output: 3
  2. Clear
    Description: Removes all elements from the stack.

    • Input: None.
    • Output: None.
    • Behavior: This operation removes all elements from the stack, making it empty.

    Example:

    Stack before Clear: [10, 20, 30]
    Clear()
    Stack after Clear: []

Pseudocode for Stack Operations

1. Push Operation

Procedure Push(Stack, Element)
If Stack is full
Print “Stack Overflow”
Else
Increment Top by 1
Stack[Top] = Element
EndIf
EndProcedure

2. Pop Operation

Procedure Pop(Stack)
If Stack is empty
Print “Stack Underflow”
Else
Element = Stack[Top]
Decrement Top by 1
Return Element
EndIf
EndProcedure

3. Peek Operation

Procedure Peek(Stack)
If Stack is empty
Print “Stack is empty”
Else
Return Stack[Top]
EndIf
EndProcedure

4. isEmpty Operation

Procedure isEmpty(Stack)
If Top is equal to -1
Return true
Else
Return false
EndIf
EndProcedure

Example: Stack Operations Implementation in C

#include <stdio.h>
#include <stdlib.h>
#define MAX 5 // Maximum size of the stack

int stack[MAX]; // Stack array
int top = -1; // Variable to track the top of the stack

// Function to push an element into the stack
void push(int value) {
if (top == MAX – 1) {
printf(“Stack Overflow! Cannot push %d\n”, value);
} else {
top++;
stack[top] = value;
printf(“%d pushed into stack.\n”, value);
}
}

// Function to pop an element from the stack
int pop() {
if (top == -1) {
printf(“Stack Underflow! Cannot pop\n”);
return -1;
} else {
int poppedValue = stack[top];
top–;
return poppedValue;
}
}

// Function to peek at the top element of the stack
int peek() {
if (top == -1) {
printf(“Stack is empty.\n”);
return -1;
} else {
return stack[top];
}
}

// Function to check if the stack is empty
int isEmpty() {
return top == -1;
}

// Main function to demonstrate stack operations
int main() {
push(10);
push(20);
push(30);
printf(“Top element is %d\n”, peek());

printf(“Popped element is %d\n”, pop());
printf(“Popped element is %d\n”, pop());

if (isEmpty()) {
printf(“Stack is empty.\n”);
} else {
printf(“Stack is not empty.\n”);
}

return 0;
}

Output:

10 pushed into stack.
20 pushed into stack.
30 pushed into stack.
Top element is 30
Popped element is 30
Popped element is 20
Stack is not empty.

2.4 Stack Application: Infix to Postfix/Prefix Conversion and Evaluation

Stacks play a critical role in expression evaluation and conversion between different forms of mathematical expressions, such as infix, postfix, and prefix notations. This section covers:

  • Conversion from infix to postfix/prefix.
  • Evaluation of postfix/prefix expressions.

1. Expression Notations Overview

  • Infix Notation: Operators are written between operands. Example: A + B.
  • Postfix Notation (Reverse Polish Notation): Operators are written after their operands. Example: A B +.
  • Prefix Notation (Polish Notation): Operators are written before their operands. Example: + A B.

Conversion from Infix to Postfix/Prefix

Infix to Postfix Conversion

  • In this process, we rearrange the infix expression to move operators after operands while maintaining the same precedence and associativity rules.
  • Algorithm:
    1. Scan the infix expression from left to right.
    2. Use a stack to temporarily hold operators and parentheses.
    3. If an operand (number/variable) is encountered, add it to the output (postfix expression).
    4. If an operator is encountered:
      • Pop operators from the stack with higher or equal precedence than the current operator and append them to the output.
      • Push the current operator to the stack.
    5. If an opening parenthesis is encountered, push it onto the stack.
    6. If a closing parenthesis is encountered, pop operators from the stack and append to the output until an opening parenthesis is encountered (then discard it).
    7. After scanning the expression, pop and append all remaining operators in the stack to the output.

Example of Infix to Postfix Conversion:

Infix Expression: (A + B) * (C - D)

  1. Scan ( → push (.
  2. Scan A → output A.
  3. Scan + → push +.
  4. Scan B → output B.
  5. Scan ) → pop + and append → output A B +, discard (.
  6. Scan * → push *.
  7. Scan ( → push (.
  8. Scan C → output C.
  9. Scan - → push -.
  10. Scan D → output D.
  11. Scan ) → pop - and append → output C D -, discard (.
  12. Pop * from the stack and append → Postfix: A B + C D - *.

Infix to Prefix Conversion

The process is similar to the infix-to-postfix conversion but in reverse order:

  1. Reverse the infix expression.
  2. Apply the infix-to-postfix algorithm (with operators being placed in reverse order).
  3. Reverse the result to get the prefix expression.

Example of Infix to Prefix Conversion:

Infix Expression: (A + B) * (C - D)

  1. Reverse: ) D - C ( * ) B + A (
  2. Apply the infix-to-postfix algorithm → A B + C D - *
  3. Reverse the result → Prefix: * + A B - C D.

2. Evaluation of Postfix/Prefix Expressions

Once an expression is converted into postfix or prefix, it can be evaluated easily using a stack because operators appear after their operands (in postfix) or before their operands (in prefix).

Evaluation of Postfix Expression

In a postfix expression, we evaluate from left to right:

  • When encountering an operand, push it onto the stack.
  • When encountering an operator, pop the required number of operands from the stack, perform the operation, and push the result back onto the stack.
  • At the end, the stack contains the final result.

Postfix Evaluation Example

Postfix Expression: 2 3 + 4 *
Steps:

  1. Push 2 onto the stack.
  2. Push 3 onto the stack.
  3. Encounter +: pop 2 and 3, calculate 2 + 3 = 5, push 5 onto the stack.
  4. Push 4 onto the stack.
  5. Encounter *: pop 5 and 4, calculate 5 * 4 = 20, push 20 onto the stack.
  6. Final result is 20.

Evaluation of Prefix Expression

In a prefix expression, we evaluate from right to left:

  • When encountering an operand, push it onto the stack.
  • When encountering an operator, pop the required number of operands from the stack, perform the operation, and push the result back onto the stack.

Prefix Evaluation Example

Prefix Expression: * + 2 3 4
Steps:

  1. Scan 4 → push 4 onto the stack.
  2. Scan 3 → push 3 onto the stack.
  3. Scan 2 → push 2 onto the stack.
  4. Scan +: pop 2 and 3, calculate 2 + 3 = 5, push 5 onto the stack.
  5. Scan *: pop 5 and 4, calculate 5 * 4 = 20, push 20 onto the stack.
  6. Final result is 20.

Implementation of Infix to Postfix Conversion and Postfix Evaluation

C Program: Infix to Postfix Conversion

#include <stdio.h>
#include <ctype.h> // For isdigit() function
#include <stdlib.h>

#define MAX 100

// Stack structure for operators
char stack[MAX];
int top = -1;

// Push operation for stack
void push(char c) {
if (top == MAX – 1) {
printf(“Stack Overflow\n”);
} else {
stack[++top] = c;
}
}

// Pop operation for stack
char pop() {
if (top == -1) {
printf(“Stack Underflow\n”);
return -1;
} else {
return stack[top–];
}
}

// Function to check precedence of operators
int precedence(char c) {
if (c == ‘+’ || c == ‘-‘) {
return 1;
} else if (c == ‘*’ || c == ‘/’) {
return 2;
} else if (c == ‘^’) {
return 3;
}
return 0;
}

// Function to check if character is an operator
int isOperator(char c) {
return (c == ‘+’ || c == ‘-‘ || c == ‘*’ || c == ‘/’ || c == ‘^’);
}

// Function to convert infix to postfix
void infixToPostfix(char* infix) {
char postfix[MAX];
int i = 0, j = 0;

while (infix[i] != ‘\0’) {
char c = infix[i];

// If the character is an operand, add it to postfix expression
if (isalnum(c)) {
postfix[j++] = c;
}
// If the character is an opening parenthesis, push it to stack
else if (c == ‘(‘) {
push(c);
}
// If the character is a closing parenthesis, pop until ‘(‘ is found
else if (c == ‘)’) {
while (stack[top] != ‘(‘) {
postfix[j++] = pop();
}
pop(); // Remove ‘(‘ from stack
}
// If the character is an operator
else if (isOperator(c)) {
while (top != -1 && precedence(stack[top]) >= precedence(c)) {
postfix[j++] = pop();
}
push(c);
}
i++;
}

// Pop all remaining operators from the stack
while (top != -1) {
postfix[j++] = pop();
}

postfix[j] = ‘\0’; // Null-terminate the string
printf(“Postfix Expression: %s\n”, postfix);
}

// Main function to test the infix to postfix conversion
int main() {
char infix[MAX];

printf(“Enter an infix expression: “);
scanf(“%s”, infix);

infixToPostfix(infix);

return 0;
}

Write a program to implement stack operations

Here’s a simple C program that implements stack operations such as push, pop, peek, isEmpty, and isFull. This program uses an array to store stack elements and provides the basic operations on the stack.

C Program to Implement Stack Operations

#include <stdio.h>
#include <stdlib.h>

#define MAX 5 // Define the maximum size of the stack

int stack[MAX]; // Array to store stack elements
int top = -1; // Variable to track the top of the stack

// Function to check if the stack is full
int isFull() {
return top == MAX – 1;
}

// Function to check if the stack is empty
int isEmpty() {
return top == -1;
}

// Function to push an element into the stack
void push(int value) {
if (isFull()) {
printf(“Stack Overflow! Cannot push %d\n”, value);
} else {
top++;
stack[top] = value;
printf(“%d pushed into stack.\n”, value);
}
}

// Function to pop an element from the stack
int pop() {
if (isEmpty()) {
printf(“Stack Underflow! Cannot pop\n”);
return -1;
} else {
int poppedValue = stack[top];
top–;
printf(“%d popped from stack.\n”, poppedValue);
return poppedValue;
}
}

// Function to peek the top element of the stack
int peek() {
if (isEmpty()) {
printf(“Stack is empty.\n”);
return -1;
} else {
return stack[top];
}
}

// Function to display the stack elements
void display() {
if (isEmpty()) {
printf(“Stack is empty.\n”);
} else {
printf(“Stack elements: “);
for (int i = 0; i <= top; i++) {
printf(“%d “, stack[i]);
}
printf(“\n”);
}
}

// Main function to test the stack operations
int main() {
int choice, value;

while (1) {
printf(“\nStack Operations:\n”);
printf(“1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n”);
printf(“Enter your choice: “);
scanf(“%d”, &choice);

switch (choice) {
case 1:
printf(“Enter value to push: “);
scanf(“%d”, &value);
push(value);
break;
case 2:
pop();
break;
case 3:
value = peek();
if (value != -1) {
printf(“Top element is %d\n”, value);
}
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf(“Invalid choice. Please try again.\n”);
}
}

return 0;
}

Explanation of the Code:

  1. isFull(): Checks if the stack is full by comparing the value of top with MAX - 1. If top is equal to MAX - 1, the stack is full.
  2. isEmpty(): Checks if the stack is empty by checking if top is -1. If top == -1, the stack is empty.
  3. push(): Adds a new element to the top of the stack. Before pushing, it checks if the stack is full. If not, it increments the top and adds the value to the stack.
  4. pop(): Removes and returns the top element of the stack. Before popping, it checks if the stack is empty. If not, it decrements the top and returns the value.
  5. peek(): Returns the top element of the stack without removing it. If the stack is empty, it returns -1.
  6. display(): Displays all elements of the stack from bottom to top.

Sample Output:

Stack Operations:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to push: 10
10 pushed into stack.

Stack Operations:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 1
Enter value to push: 20
20 pushed into stack.

Stack Operations:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 4
Stack elements: 10 20

Stack Operations:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 3
Top element is 20

Stack Operations:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 2
20 popped from stack.

Stack Operations:
1. Push
2. Pop
3. Peek
4. Display
5. Exit
Enter your choice: 5

Previous Chapter Next Chapter
Important Questions
Comments
Discussion
0 Comments
  Loading . . .