(4)Stack

Stacks

Objectives

• Understand the main concepts of stacks

• Examine various stack operations

• Learn how to implement a stack as an array

• Learn how to implement a stack as a linked list

• Discover stack applications

Introduction

• Stacks can be visualized as multiple layers or items stacked on top of one another.

• Examples of stacks include:

  • Stack of boxes

  • Stack of books

  • Stack of trays

  • Stack of coins

Stack Abstract Data Type (ADT)

• Definition of Stack ADT: A specific type of data structure that follows the Last In First Out (LIFO) principle.

• UML Class Diagram Representation:

  • stackType<Type>

  • Attributes:

  • maxStackSize: int

  • stackTop: int

  • *list: Type

  • Methods:

  • +operator=(const stackType<Type>&): const stackType<Type>&

  • +initializeStack(): void

  • +isEmptyStack() const: bool

  • +isFullStack() const: bool

  • +push(const Type &): void

  • +top() const: Type

  • +pop(): void

  • +copyStack(const stackType<Type>&): void

  • +stackType(int=100)

  • +stackType(const stackType<Type>&)

  • +~stackType()

Stack Implementation as Arrays

Overview

• When implementing a stack as an array, the first stack element is placed in the first array slot, the second element in the second slot, and so forth.

• stackTop variable:

  • Represents the number of elements in the stack.

  • The value of stackTop - 1 points to the top item of the stack.

Example of a Stack

• Max size of stack: 100

• Stack elements filled:

  • list[0]: A

  • list[1]: B

  • list[2]: C

  • list[3]: D

• Current stackTop: 4

Stack Operations

1. Initialize, Empty, and Full Operations:

   • initializeStack(): Sets stackTop to 0.

   • isEmptyStack(): Returns true if stackTop == 0.

   • isFullStack(): Returns true if stackTop == maxStackSize.

2. Return Top Element Function:

   • top(): Returns the element at the location pointed by stackTop-1.

   • Uses assert(stackTop != 0) to check for an empty stack.

3. Push Function:

   • Adds a new item to the stack.

   • Steps:

   1. Check if the stack is full.

   2. If not full, assign newItem to list[stackTop] and increment stackTop.

   3. If full, output a message saying the stack cannot accept more items.

4. Pop Function:

   • Removes the top element of the stack by decrementing stackTop.

   • If the stack is empty, notify that no deletion occurs.

Homework Exercises

• Homework Problem 1: Given a stack object S1, the result of executing S1.copyStack(S2) needs to be shown.

• Homework Problem 2: Show results of code operations using push, pop, and top functions in a stack object.

• Homework Problem 3: Modify the stack by filtering out a specific item during the pop operations.

• Homework Problem 4: Write two specific functions in C++ for string reversal.

Stack Implementation: Linked Stacks

Overview

• In a linked stack, nodes are used instead of arrays to store data.

• stackTop: Points to the top node, allowing dynamic memory allocation.

Operations in Linked Stacks

1. Empty and Full Check:

   • Stack is empty if stackTop is NULL.

   • A linked stack can grow and does not become full due to dynamic allocation.

2. Reinitialize Stack:

   • Deallocates all nodes and sets stackTop to NULL.

3. Push Operation:

   • Create a new node, point it to the previous top node, and update stackTop to this new node.

4. Pop Operation:

   • Remove the node at the top and adjust stackTop to point to the next node in the stack.

5. Copy Stack Function:

   • Copies one stack onto another node by node, handling memory allocation correctly.

Time Complexity of Linked Stacks

• isEmptyStack: O(1)

• initializeStack: O(n)

• top: O(1)

• push: O(1)

• pop: O(1)

• copyStack: O(n)

Practical Applications

• Stacks are used for various applications such as parsing expressions, backtracking algorithms, and reversing data structures.

• They enable non-recursive solutions to problems like printing a linked list backward by using a stack to temporarily hold the elements.

Stacks

What We'll Learn

• Learn what stacks are

• See how stacks work (like putting things in and taking things out)

• Learn how to build a stack using a simple list (array)

• Learn how to build a stack using connecting pieces (linked list)

• Find out where we use stacks in real life

What's a Stack?

• Imagine stacking things up, one on top of the other, like a pile of blocks or coins.

• That's what a stack is! When you add a new block, it goes on top. When you want a block, you take the top one first.

• Examples of stacks include:

  • Stack of boxes

  • Stack of books

  • Stack of trays

  • Stack of coins

Stack Rules (Abstract Data Type - ADT)

• A Stack ADT is like a special rule for our stack of blocks. It says:

  • "Last In, First Out (LIFO)": This means the last block you put on top is the first one you have to take off!

  • Think of a Pringles can – you can only take the top chip, and the last chip put in was the one on top before you started eating.

Building a Stack with a Simple List (Arrays)

How it Works

• When we build a stack using a simple list (which we call an array), we just put our items one after the other in a line.

• We use a special counter called stackTop to remember how many items are in our stack.

• If stackTop is $4$, it means we have $4$ items, and the very top item is the $4$th one we put in.

Example of a Stack

• Let's say our stack of blocks can hold $100$ blocks.

• If we put in block A, then B, then C, then D, our stack looks like:

  • D (on top)

  • C

  • B

  • A (at the bottom)

• Our stackTop counter would be $4$, because we have $4$ blocks.

Stack Actions

1. Starting, Empty, and Full Operations:

   • initializeStack(): We make our stack empty by setting our stackTop counter to $0$.

   • isEmptyStack(): We check if stackTop is $0$. If it is, the stack is empty!

   • isFullStack(): We check if stackTop is as big as the maximum number of blocks our stack can hold. If it is, the stack is full!

2. Look at the Top Block (top()):

   • This lets us peek at the very top block without taking it off.

   • But we can only do this if the stack is not empty!

3. Put a Block On (push()):

   • We put a new block on top of the stack.

   • Steps:

     1. First, we make sure the stack isn't full.

     2. If there's space, we put the new block on top and make our stackTop counter go up by one.

     3. If the stack is full, we can't add any more blocks!

4. Take a Block Off (pop()):

   • We take the very top block off the stack.

   • We just make our stackTop counter go down by one.

   • If the stack is empty, there are no blocks to take off!

Fun Challenges

• Challenge 1: Imagine you have two stacks. How would you make one stack into an exact copy of the other?

• Challenge 2: Practice using the 'put a block on' (push), 'take a block off' (pop), and 'look at the top block' (top) actions.

• Challenge 3: What if you only want to take off certain blocks, and leave others?

• Challenge 4: Can you use a stack to say a word backward, like turning 'cat' into 'tac'?

Building a Stack with Connected Boxes (Linked Stacks)

How it Works

• Sometimes, instead of a simple list, we use little 'boxes' that are all connected together. We call these 'nodes'.

• Each box holds one item and points to the next box below it.

• stackTop still points to the very top box. This way, our stack can grow as big as we need it to be!

Actions in Linked Stacks

1. Empty and Full Check:

   • Our stack is empty if stackTop isn't pointing to any box.

   • Good news! A stack made of connected boxes never really gets full because we can always add more boxes!

2. Make Stack Empty Again:

   • We throw away all the boxes and make stackTop point to nothing, so the stack is empty.

3. Put a Box On (push()):

   • We make a new box for our item, connect it to the top box that was there before, and then make stackTop point to our brand new box (which is now on top).

4. Take a Box Off (pop()):

   • We take the top box away, and then stackTop points to the next box that is now on top.

5. Make a Copy:

   • This is like making an exact duplicate stack, box by box.

How Fast Stacks Work (Time Complexity)

• isEmptyStack: Checking if the stack is empty is super fast, like just one quick look.

• initializeStack: Making the stack empty by throwing away all the boxes takes a little longer if there are many boxes.

• top: Peeking at the top block is super fast, just one quick look.

• push: Putting a new block on top is super fast.

• pop: Taking a block off the top is super fast.

• copyStack: Making a copy of the whole stack takes longer if there are many blocks, because you have to copy each one.

Where We Use Stacks

• Stacks are very useful! For example, when you use a calculator, it uses a stack to figure out math problems.

• When you click 'undo' on a computer, it's often using a stack to remember all the past steps.

• If you want to print a list of items backward, you can put all the items into a stack, and then take them out one by one – they'll come out in reverse order!

Stacks

/

Objectives

• Understand the main concepts of stacks

• Examine various stack operations

• Learn how to implement a stack as an array

• Learn how to implement a stack as a linked list

• Discover stack applications

Introduction

• Stacks can be visualized as multiple layers or items stacked on top of one another.

• Examples of stacks include:

  • Stack of boxes

  • Stack of books

  • Stack of trays

  • Stack of coins

Stack Abstract Data Type (ADT)

• Definition of Stack ADT: A specific type of data structure that follows the Last In First Out (LIFO) principle.

• UML Class Diagram Representation:

  • stackType<Type>

  • Attributes:

  • maxStackSize: int

  • stackTop: int

  • *list: Type

  • Methods:

  • +operator=(const stackType<Type>&): const stackType<Type>&

  • +initializeStack(): void

  • +isEmptyStack() const: bool

  • +isFullStack() const: bool

  • +push(const Type &): void

  • +top() const: Type

  • +pop(): void

  • +copyStack(const stackType<Type>&): void

  • +stackType(int=100)

  • +stackType(const stackType<Type>&)

  • +~stackType()

Stack Implementation as Arrays

Overview

• When implementing a stack as an array, the first stack element is placed in the first array slot, the second element in the second slot, and so forth.

• stackTop variable:

  • Represents the number of elements in the stack.

  • The value of stackTop - 1 points to the top item of the stack.

Example of a Stack

• Max size of stack: 100

• Stack elements filled:

  • list[0]: A

  • list[1]: B

  • list[2]: C

  • list[3]: D

• Current stackTop: 4

Stack Operations

1. Initialize, Empty, and Full Operations:

   • initializeStack(): Sets stackTop to 0.

   • isEmptyStack(): Returns true if stackTop == 0.

   • isFullStack(): Returns true if stackTop == maxStackSize.

2. Return Top Element Function:

   • top(): Returns the element at the location pointed by stackTop-1.

   • Uses assert(stackTop != 0) to check for an empty stack.

3. Push Function:

   • Adds a new item to the stack.

   • Steps:

   1. Check if the stack is full.

   2. If not full, assign newItem to list[stackTop] and increment stackTop.

   3. If full, output a message saying the stack cannot accept more items.

4. Pop Function:

   • Removes the top element of the stack by decrementing stackTop.

   • If the stack is empty, notify that no deletion occurs.

Array-Based Stack C++ Implementation Example

// Define a template class for an array-based stack
template <class Type>
class arrayStackType {
private:
    int maxStackSize; // Maximum number of elements the stack can hold
    int stackTop;     // Index of the top element of the stack (also number of elements)
    Type *list;       // Pointer to the dynamic array that stores stack elements

public:
    // Constructor: Initializes the stack with an optional size parameter
    arrayStackType(int stackSize = 100) {
        if (stackSize <= 0) { // Validate stackSize to ensure it's positive
            maxStackSize = 100; // Default to 100 if invalid size is given
        } else {
            maxStackSize = stackSize; // Set maxStackSize to the provided value
        }
        stackTop = 0;              // Initialize stackTop to 0, indicating an empty stack
        list = new Type[maxStackSize]; // Dynamically allocate memory for the array of 'Type' elements
    }

    // Destructor: Cleans up dynamically allocated memory when the stack object is destroyed
    ~arrayStackType() {
        delete[] list; // Deallocate the array pointed to by 'list'
    }

    // Function to set the stack to an empty state
    void initializeStack() {
        stackTop = 0; // Reset stackTop to 0, effectively clearing the stack without deallocating memory
    }

    // Function to check if the stack currently contains no elements
    bool isEmptyStack() const {
        return (stackTop == 0); // Returns true if stackTop is 0, false otherwise
    }

    // Function to check if the stack has reached its maximum capacity
    bool isFullStack() const {
        return (stackTop == maxStackSize); // Returns true if stackTop equals maxStackSize, false otherwise
    }

    // Function to add a new item to the top of the stack
    void push(const Type& newItem) {
        if (!isFullStack()) {         // First, check if there is space in the stack
            list[stackTop] = newItem; // Place the 'newItem' at the current 'stackTop' index
            stackTop++;               // Increment 'stackTop' to reflect the new element and point to the next available position
        } else {
            // If the stack is full, output an error message (or handle with exception)
            // std::cout << "Cannot add to a full stack." << std::endl;
        }
    }

    // Function to retrieve the element at the top of the stack without removing it
    Type top() const {
        // Assert that the stack is not empty before attempting to access top element
        // assert(stackTop != 0); // Requires #include <cassert> -- will terminate if stack is empty
        if (isEmptyStack()) { // A safer check for an empty stack
            // Handle error, e.g., throw exception or return a default-constructed object
            // std::cout << "Stack is empty, cannot return top element." << std::endl;
            return Type(); // For example, return a default value for safety
        }
        return list[stackTop - 1]; // Return the element at the index just below 'stackTop'
    }

    // Function to remove the element from the top of the stack
    void pop() {
        if (!isEmptyStack()) { // Check if the stack contains elements to remove
            stackTop--;        // Decrement 'stackTop', effectively removing the top element by making it inaccessible
        } else {
            // If the stack is already empty, output an error message (or handle with exception)
            // std::cout << "Cannot remove from an empty stack." << std::endl;
        }
    }
};

Homework Exercises

• Homework Problem 1: Given a stack object S1, the result of executing S1.copyStack(S2) needs to be shown.

• Homework Problem 2: Show results of code operations using push, pop, and top functions in a stack object.

• Homework Problem 3: Modify the stack by filtering out a specific item during the pop operations.

• Homework Problem 4: Write two specific functions in C++ for string reversal.

Stack Implementation: Linked Stacks

Overview

• In a linked stack, nodes are used instead of arrays to store data.

• stackTop: Points to the top node, allowing dynamic memory allocation.

Operations in Linked Stacks

1. Empty and Full Check:

   • Stack is empty if stackTop is NULL.

   • A linked stack can grow and does not become full due to dynamic allocation.

2. Reinitialize Stack:

   • Deallocates all nodes and sets stackTop to NULL.

3. Push Operation:

   • Create a new node, point it to the previous top node, and update stackTop to this new node.

4. Pop Operation:

   • Remove the node at the top and adjust stackTop to point to the next node in the stack.

5. Copy Stack Function:

   • Copies one stack onto another node by node, handling memory allocation correctly.

Linked List-Based Stack C++ Implementation Example

// Define a struct for a node in the linked list
template <class Type>
struct nodeType {
    Type info;         // Data stored in this node of the stack
    nodeType<Type> *link; // Pointer to the next node in the stack (the node logically below this one)
};

// Define a template class for a linked list-based stack
template <class Type>
class linkedStackType {
private:
    nodeType<Type> *stackTop; // Pointer to the top node of the stack

public:
    // Constructor: Initializes an empty stack
    linkedStackType() {
        stackTop = nullptr; // Set stackTop to nullptr, indicating an empty stack initially
    }

    // Destructor: Deallocates all nodes in the stack to prevent memory leaks
    ~linkedStackType() {
        initializeStack(); // Call initializeStack to clear all nodes
    }

    // Function to initialize the stack to an empty state by deallocating all nodes
    void initializeStack() {
        nodeType<Type> *temp; // Temporary pointer to help deallocate nodes

        while (stackTop != nullptr) { // Loop as long as there are nodes in the stack
            temp = stackTop;           // Store the current top node in 'temp'
            stackTop = stackTop->link; // Move 'stackTop' to the next node (the one below the current top)
            delete temp;               // Delete the node that was previously at the top
        }
    }

    // Function to check if the stack currently contains no elements
    bool isEmptyStack() const {
        return (stackTop == nullptr); // Returns true if stackTop is nullptr, false otherwise
    }

    // Function to check if the stack is full. Linked stacks grow dynamically.
    bool isFullStack() const {
        return false; // Linked stacks typically do not become full unless memory is exhausted
    }

    // Function to add a new item to the top of the stack
    void push(const Type& newItem) {
        nodeType<Type> *newNode;   // Declare a pointer for the new node
        newNode = new nodeType<Type>; // Dynamically allocate memory for the new node
        newNode->info = newItem;   // Store the 'newItem' data in the new node's 'info' field
        newNode->link = stackTop;  // Make the new node point to what was previously the top node
        stackTop = newNode;        // Update 'stackTop' to point to the 'newNode', making it the new top
    }

    // Function to retrieve the element at the top of the stack without removing it
    Type top() const {
        // Assert that the stack is not empty before attempting to access top element
        // assert(stackTop != nullptr); // Requires #include <cassert> -- will crash if stack is empty
        if (isEmptyStack()) { // A safer check for an empty stack
            // Handle error, e.g., throw exception or return a default-constructed object
            // std::cout << "Stack is empty, cannot return top element." << std::endl;
            return Type(); // For example, return a default value for safety
        }
        return stackTop->info; // Return the data from the node that 'stackTop' is pointing to
    }

    // Function to remove the element from the top of the stack
    void pop() {
        nodeType<Type> *temp; // Temporary pointer to help deallocate the top node

        if (!isEmptyStack()) { // Check if the stack contains elements to remove
            temp = stackTop;           // Store the current top node in 'temp'
            stackTop = stackTop->link; // Move 'stackTop' to the next node, effectively unlinking the current top
            delete temp;               // Delete the node that was previously at the top
        } else {
            // If the stack is already empty, output an error message (or handle with exception)
            // std::cout << "Cannot remove from an empty stack." << std::endl;
        }
    }
};

Time Complexity of Linked Stacks

• isEmptyStack: O(1)

• initializeStack: O(n)

• top: O(1)

• push: O(1)

• pop: O(1)

• copyStack: O(n)

Practical Applications

• Stacks are used for various applications such as parsing expressions, backtracking algorithms, and reversing data structures.

• They enable non-recursive solutions to problems like printing a linked list backward by using a stack to temporarily hold the elements.

Stacks

What We'll Learn

• Learn what stacks are

• See how stacks work (like putting things in and taking things out)

• Learn how to build a stack using a simple list (array)

• Learn how to build a stack using connecting pieces (linked list)

• Find out where we use stacks in real life

What's a Stack?

• Imagine stacking things up, one on top of the other, like a pile of blocks or coins.

• That's what a stack is! When you add a new block, it goes on top. When you want a block, you take the top one first.

• Examples of stacks include:

  • Stack of boxes

  • Stack of books

  • Stack of trays

  • Stack of coins

Stack Rules (Abstract Data Type - ADT)

• A Stack ADT is like a special rule for our stack of blocks. It says:

  • "Last In, First Out (LIFO)": This means the last block you put on top is the first one you have to take off!

  • Think of a Pringles can – you can only take the top chip, and the last chip put in was the one on top before you started eating.

Building a Stack with a Simple List (Arrays)

How it Works

• When we build a stack using a simple list (which we call an array), we just put our items one after the other in a line.

• We use a special counter called stackTop to remember how many items are in our stack.

• If stackTop is $4$, it means we have $4$ items, and the very top item is the $4$th one we put in.

Example of a Stack

• Let's say our stack of blocks can hold $100$ blocks.

• If we put in block A, then B, then C, then D, our stack looks like:

  • D (on top)

  • C

  • B

  • A (at the bottom)

• Our stackTop counter would be $4$, because we have $4$ blocks.

Stack Actions

1. Starting, Empty, and Full Operations:

   • initializeStack(): We make our stack empty by setting our stackTop counter to $0$.

   • isEmptyStack(): We check if stackTop is $0$. If it is, the stack is empty!

   • isFullStack(): We check if stackTop is as big as the maximum number of blocks our stack can hold. If it is, the stack is full!

2. Look at the Top Block (top()):

   • This lets us peek at the very top block without taking it off.

   • But we can only do this if the stack is not empty!

3. Put a Block On (push()):

   • We put a new block on top of the stack.

   • Steps:

     1. First, we make sure the stack isn't full.

     2. If there's space, we put the new block on top and make our stackTop counter go up by one.

     3. If the stack is full, we can't add any more blocks!

4. Take a Block Off (pop()):

   • We take the very top block off the stack.

   • We just make our stackTop counter go down by one.

   • If the stack is empty, there are no blocks to take off!

Fun Challenges

• Challenge 1: Imagine you have two stacks. How would you make one stack into an exact copy of the other?

• Challenge 2: Practice using the 'put a block on' (push), 'take a block off' (pop), and 'look at the top block' (top) actions.

• Challenge 3: What if you only want to take off certain blocks, and leave others?

• Challenge 4: Can you use a stack to say a word backward, like turning 'cat' into 'tac'?

Building a Stack with Connected Boxes (Linked Stacks)

How it Works

• Sometimes, instead of a simple list, we use little 'boxes' that are all connected together. We call these 'nodes'.

• Each box holds one item and points to the next box below it.

• stackTop still points to the very top box. This way, our stack can grow as big as we need it to be!

Actions in Linked Stacks

1. Empty and Full Check:

   • Our stack is empty if stackTop isn't pointing to any box.

   • Good news! A stack made of connected boxes never really gets full because we can always add more boxes!

2. Make Stack Empty Again:

   • We throw away all the boxes and make stackTop point to nothing, so the stack is empty.

3. Put a Box On (push()):

   • We make a new box for our item, connect it to the top box that was there before, and then make stackTop point to our brand new box (which is now on top).

4. Take a Box Off (pop()):

   • We take the top box away, and then stackTop points to the next box that is now on top.

5. Make a Copy:

   • This is like making an exact duplicate stack, box by box.

How Fast Stacks Work (Time Complexity)

• isEmptyStack: Checking if the stack is empty is super fast, like just one quick look.

• initializeStack: Making the stack empty by throwing away all the boxes takes a little longer if there are many boxes.

• top: Peeking at the top block is super fast, just one quick look.

• push: Putting a new block on top is super fast.

• pop: Taking a block off the top is super fast.

• copyStack: Making a copy of the whole stack takes longer if there are many blocks, because you have to copy each one.

Where We Use Stacks

• Stacks are very useful! For example, when you use a calculator, it uses a stack to figure out math problems.

• When you click 'undo' on a computer, it's often using a stack to remember all the past steps.

• If you want to print a list of items backward, you can put all the items into a stack, and then take them out one by one – they'll come out in reverse order!