Computer Science: Class 12 — Chapter 3: Stack

A data structure defines a mechanism to store, organise, and access data along with operations (processing) that can be efficiently performed on the data. Grouping multiple data elements in a particular way allows for faster accessibility and efficient storage.

A linear data structure is one in which elements are organised in a sequential order. Examples include arrays, linked lists, stacks, and queues.

A Stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. In a stack, addition of new elements and removal of existing elements occur at the same end, commonly referred to as the TOP of the stack. The element inserted last is always the first one to be retrieved.

A stack supports two fundamental operations that modify its state:

• PUSH : An insertion operation that adds a new element to the TOP of the stack. Attempting to push an element onto a stack that has reached its maximum capacity results in an exception called overflow .
• POP : A deletion operation that removes and returns the topmost element of the stack. Attempting to pop an element from an empty stack results in an exception called underflow .

In Python, a stack can be easily implemented using the built-in list data type. The list methods append() and pop() naturally insert and delete elements at the rightmost end (the end of the list), which serves as the TOP of the stack. This eliminates the need for an explicit TOP pointer variable.

Below is a complete Python program implementing a stack of glasses:

  
  def isEmpty(glassStack):
    if len(glassStack) == 0:
        return True
    else:
        return False

def opPush(glassStack, element):
    glassStack.append(element)

def size(glassStack):
    return len(glassStack)

def top(glassStack):
    if isEmpty(glassStack):
        print('Stack is empty')
        return None
    else:
        x = len(glassStack)
        element = glassStack[x-1]
        return element

def opPop(glassStack):
    if isEmpty(glassStack):
        print('underflow')
        return None
    else:
        return glassStack.pop()

def display(glassStack):
    x = len(glassStack)
    print("Current elements in the stack are: ")
    for i in range(x-1, -1, -1):
        print(glassStack[i])

Arithmetic expressions can be represented in three distinct notations depending on the placement of operators relative to their operands:

Compilers convert human-readable infix expressions to postfix expressions to eliminate ambiguity and evaluate expressions in a single linear scan without needing parentheses.

Example Trace: Convert the infix expression $(x + y) / (z \\times 8)$ to postfix notation.

---

Socio-Technical Analysis & Core Systemic Impact: This conversion process ensures that operators with higher precedence are positioned after their operands in the exact order they must be executed. The stack acts as a temporary holding area for operators, deferring their placement until their operands have been processed. The resulting postfix expression is $x y + z 8 \\times /$, which can be evaluated linearly without backtracking.

Postfix expressions are evaluated using a stack by processing the expression from left to right. Operands are pushed onto the stack, and operators trigger the retrieval and processing of these operands.

Example Trace: Evaluate the postfix expression $7\ 8\ 2\ \times\ 4\ /\ +$.

---

Socio-Technical Analysis & Core Systemic Impact:
1. Push $7$, $8$, and $2$ onto the stack. [Stack: $7, 8, 2$]
2. Encounter operator $\\times$. Pop $2$ and $8$. Compute $8 \\times 2 = 16$. Push $16$. [Stack: $7, 16$]
3. Push $4$ onto the stack. [Stack: $7, 16, 4$]
4. Encounter operator $/$. Pop $4$ and $16$. Compute $16 / 4 = 4$. Push $4$. [Stack: $7, 4$]
5. Encounter operator $+$. Pop $4$ and $7$. Compute $7 + 4 = 11$. Push $11$. [Stack: $11$]
6. End of expression. Pop the final result: $11$.