Data Structures and Programming: Lecture on Stacks

Recap of Previous Lecture

• 3-D matrix
• Practice Problems

Topics to be Covered

• Stack as a data structure
• push operation
• pop operation
• init function
• isEmpty function

Question

• Consider a linear array A[-4..4][0...8]. Non-zero elements are stored in row-major order.
• What is the address of A[0][3]?
• Base address is 1000, and the size of each element is 2B.

Linear Search

• Count: $O(n)$, where $n$ is the length.
• Time complexity: $O(n)$
• Binary Search
  • Depends upon the length.
  • Best time = worst time: $\Theta(1)$
  • Minimum for an ordered array (incorporating elements to be searched) = $O(1)$. Return the first element.

Traversal

• Visiting each element.

• Example: Find the maximum in an array a[] = {1, 19, 20, 19, 5}.

• Using a for loop to visit array elements.

• Length-dependent.

• Code:

  int max = a[0];
  for (int i = 1; i <= n - 1; i++) {
      if (a[i] > max) {
          max = a[i];
      }
  }
  return max;
  

• Time complexity: $O(n)$

Dictionary Search

• Searching words in an ordered dictionary.
  • Words are ordered lengthwise.
  • Alphabetical ordering (Lexicographic).
  • Backward and forward iteration.

Binary Search Process

• Requires an ordered array.
• Example array: 2 3 4 5 6 7 8 10 12 23 73 89 90 120 122 127
• If a[mid] == x, the element is found.
• If a[mid] > x, update the upper bound: ub = mid - 1.
• If a[mid] < x, update the lower bound: lb = mid + 1.
• Repeat the process.
• Best case: $O(1)$
• Worst case: $O(\log n)$. Size is reduced by half in each comparison.

Binary Search Complexity

• 1 comparison ≈ 1/2
• 2 comparisons ≈ 1/4 = $\frac{1}{2^2}$
• 3 comparisons ≈ 1/8 = $\frac{1}{2^3}$
• $k^{th}$ comparison ≈ $\frac{n}{a^k}$
• $\Rightarrow \frac{n}{2^k} = 1$
• $n = 2^k$
• $k = \log_2 n$
• Binary search worst case depends upon the size: $O(\log n)$

Linear Search

• Compare each element one after another.
  • Best case: $O(1)$. Independent of length.
  • Worst case: $O(n)$. Maximum time.
  • Average case: Last index $O(n)$

Stack as LIFO

• Stack is a linear data structure.
• Stack is a one-ended data structure.
• Stack is based on the principle of Last In, First Out (LIFO).

Stack LIFO Explanation

• Analogy: A lift or elevator.
• The last person to enter the lift is the first to exit.

Stack Details

• Array data structure allows random access.
• Stack allows access of elements only using the top index.

Stack Operations: Push

• push: Insert an element into the stack.
• Increment the top index to point to the next available slot.

Stack Operations: Pop

• pop: Remove the top element from the stack.
• The last element pushed onto the stack is the first one popped.
• After popping all elements, the stack will become empty.

Stack Implementation Details

• #define Max 100
  • Max is a macro. Wherever Max appears in the program, it will be replaced by 100.
  • #define is a preprocessor directive.

Stack Application: Init Function

• void init() { top = -1; }
• The init function initializes the top to -1.
• C-array indices start from 0.

Stack Application: Is Empty Function

• int isEmpty() { if (top == -1) { return 1; // Stack is empty } else { return 0; // Stack is non-empty } }
• The isEmpty function returns 1 if the stack is empty and 0 if the stack is non-empty.

Stack Application: Push Function

• void push(int data) { if (top == Max - 1) { printf("Stack is full"); // Stack overflow return; } top = top + 1; // Increment the top a[top] = data; // Put the element in the top index }
• If top == Max - 1, the stack is full (stack overflow).
• Increment the top index.
• Insert the data at the top index.

Stack Application: Pop Function

• int pop() { int data; if (isEmpty()) { printf("Stack is Empty"); // Stack underflow return -1; } data = a[top]; top = top - 1; return data; }
• If isEmpty() is true, the stack is empty (stack underflow).
• Return -1 to indicate an error (or some other predefined error value).
• Retrieve the data from the top index.
• Decrement the top index.
• Return the retrieved data.

Stack Question

• Consider a stack of size 100 (lower bound is 0).
• Operations performed:
  • push(1)
  • push(2)
  • push(3)
  • push(50)
  • pop()
  • pop()
  • pop()
  • pop()
  • pop() 25 times
  • push(100)
  • push(98)
  • push(97)
  • pop()
• If the base address (BA) is 100 and the size is 2B, then find the value of x + y where x is the index of the top and y is the address of A[top].

Stack Question Solution

• After push(1), push(2), push(3), push(50): top = 49
• After 25 pop operations: top = 24
• After push(100), push(98), push(97): top = 27
• After the final pop(): top = 26
• Therefore, x = 26
• Address of A[26]: 100 + (26 - 0) * 2 = 100 + 52 = 152
• y = 152
• Thus, x + y = 26 + 152 = 178

Summary

• Array operations
• Stack
  • push, pop
  • isEmpty(), init()