Sy BCS || Semester 3 || Data Structure 1 || 4.Stack || Complete Chapter || SPPU || NEP Pattern ||

Stack Fundamentals

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle: the most recently added element is the first one removed. A pile of plates is a familiar example, since plates are added to and taken from the top.

A stack is also an abstract data type (ADT) used in programming languages such as C and Java.

Core Operations

• Push: Add an element to the top of the stack. Pushing onto a full stack causes overflow.
• Pop: Remove the top element. Popping from an empty stack causes underflow.
• Peek/Top: Inspect the top element without removing it.
• isEmpty: Check whether the stack contains no elements. In the array example, an empty stack has top = -1.
• isFull: Check whether the stack has reached its capacity.
• Count: Return the number of elements in the stack.
• Change: Replace the element at a specified position.
• Display: Print the stack’s elements.

Stack Representations

Array-Based (Static) Representation

An array-based stack has a fixed size determined when it is created. Its elements occupy contiguous memory, and indexing provides fast direct access. However, allocating more space than needed can waste memory, and inserting or deleting elements at arbitrary positions may require shifting elements.

Linked-List (Dynamic) Representation

A linked-list stack can grow or shrink at runtime. Its nodes are stored in non-contiguous memory, with each node containing data and a link to the next node. Access may be slower because nodes must be traversed, but insertions and deletions are generally faster because they require changing links rather than shifting elements. Memory is allocated as needed, reducing unused reserved space.

Applications

• Function calls and recursion: A call stack stores information such as local variables and return addresses. A function call pushes a record onto the stack; when the function returns, the record is popped and control returns to the calling function.
• Reversing a string: Push each character onto a stack, then pop the characters into a new string. LIFO order produces the reversed result.

Stacks are also used in other areas of computer science.

Expression Notations

The position of the operator relative to the operands determines the notation:

• Infix: The operator appears between the operands, as in a + b.
• Prefix: The operator appears before the operands, as in + a b.
• Postfix: The operator appears after the operands, as in a b +.

Array-Based C Program Demonstration

The instructor demonstrates a menu-driven integer stack using an array with a maximum capacity of five. The implementation:

• Defines the stack capacity and declares an array of that size.
• Initializes top to -1 to indicate an empty stack.
• Checks whether the stack is empty with top == -1.
• Checks whether the stack is full with top == MAX - 1.
• For push, checks that the stack is not full, increments top, and stores the value.
• For pop, checks that the stack is not empty, then decrements top.
• For peek, checks that the stack is not empty and reports the top value.
• For display, prints elements from the top down.
• Uses a menu and switch-case statements to select operations.

In the demonstration, pushing 25 and then 26 places 26 at the top. Popping removes 26, leaving 25 in the stack.

Speakers and Sources

• Kadam’s Study Center presenter/instructor: The only identifiable speaker, explaining the concepts and demonstrating the program.
• Visual aids and code demonstration: Stack diagrams, slides, and a C programming environment or terminal are used. No other speaker or external source is identified.