Stack

3 Stack

3.1 Introduction

In this chapter, we explore the stack data structure. A stack is used to store multiple elements where the elements can be accessed in a specific order. Stacks allow operations to be performed in a Last-In-First-Out (LIFO) manner. This concept is fundamental in both computer science and programming.

A data structure defines how data is organized and accessed. While understanding stacks, we should also be familiar with other data structures like arrays, linked lists, and queues that help to handle data effectively.

3.2 Stack

A stack behaves like a pile of plates or books. You add to and remove items from the top of the pile. The operations performed on a stack are:

• PUSH: Adds an element to the top.
• POP: Removes the topmost element.

Common real-life examples and programming uses of stacks include:

• Managing function calls in programming languages.
• Undo/Redo functionality in text/image editors.
• Backtracking in web browsers (navigating to a previous page).
• Matching parentheses in mathematical expressions.

3.3 Operations on Stack

There are two fundamental stack operations:

• PUSH: Used to insert a new element at the top of the stack.
• POP: Used to remove the top element from the stack.

If an attempt is made to pop an element from an empty stack, it results in underflow. Conversely, trying to push an element onto a full stack results in overflow. In Python, lists can be utilized to simulate stacks since they allow for dynamic sizing.

3.4 Implementation of Stack in Python

Python’s built-in list type can be utilized to implement stacks simply. The methods append() and pop() can be applied for pushing and popping elements. Here’s how to implement a basic stack:

class Stack:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        return 'underflow'
    
    def size(self):
        return len(self.items)
    
    def top(self):
        if not self.is_empty():
            return self.items[-1]
        return 'stack empty'
    
    def display(self):
        return self.items[::-1]  # returns a reversed list for display

3.5 Notations for Arithmetic Expressions

Mathematical expressions can be represented in different formats:

• Infix (e.g., x + y)
• Prefix (Polish Notation, e.g., +xy)
• Postfix (Reverse Polish Notation, e.g., xy+)

Postfix and prefix notations allow easier evaluation of expressions, eliminating the need for parentheses to indicate order of operations.

3.6 Conversion from Infix to Postfix Notation

Converting infix notation to postfix requires a stack to keep track of operators and their precedence. An algorithm for this conversion involves processing each character, pushing operators to the stack and building the output string accordingly.

3.7 Evaluation of Postfix Expression

Postfix expressions can be evaluated using a stack to store operands. The algorithm involves pushing operands onto the stack and performing operations when an operator is encountered. This is efficient as operators follow operands directly, maintaining a clear order of calculations.

Summary

• Stack is a data structure where operations occur at one end (TOP).
• Follows LIFO principle: last element in is the first out.
• Operations include PUSH (insert) and POP (delete).
• In Python, use built-in list methods for stack implementation.
• Convert and evaluate expressions in infix, prefix, and postfix formats using stacks.

1. Stack is a linear data structure with LIFO principle.
2. Allows PUSH (insert) and POP (delete) operations.
3. An attempt to POP from an empty stack results in underflow; pushing to a full stack results in overflow.
4. In Python, lists can be used to implement stacks.
5. PUSH adds an element at the top of the stack; POP removes the topmost element.
6. Various applications of stacks include function calls in programming and undo/redo operations in software.
7. Different notations for arithmetic expressions include infix, prefix, and postfix.
8. Conversion from infix to postfix involves using a stack to maintain operator precedence.
9. Stacks are also essential for evaluating postfix expressions efficiently.