Stack Data Structure PDF
Document Details
Uploaded by EnterprisingOrchid199
Tags
Summary
This document explains stack data structures, outlining their characteristics, operations (push and pop), memory management, and applications. Examples of C++ implementation and diagrams demonstrating stack operations, ensuring comprehensive understanding of this fundamental concept in computer science, like recursion and expression evaluation.
Full Transcript
A Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). - LIFO implies that the element that is inserted last, comes out first and -FILO implies that the element that is inserted f...
A Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). - LIFO implies that the element that is inserted last, comes out first and -FILO implies that the element that is inserted first, comes out last. Example stack Applications of Stack Data Structures -Recursion -Expression Evaluation and Parsing -Depth-First Search (DFS) -Undo/Redo Operations -Browser History -Function Calls Stack Representation in Memory The Stack is stored in memory as a sequence of elements, typically in a dedicated region called Stack Memory. A special pointer called the Stack Pointer (SP) is used to track the top element of the Stack. With each Push operation, a new element is added to the top of the Stack, and the Stack Pointer moves upward. With each Pop operation, the top element is removed, and the Stack Pointer moves downward. Memory Management: In modern systems, a specific area of memory is reserved for the Stack, known as the "Stack Segment.“ The size of the Stack can either be dynamic or fixed, depending on the system and the program. Common Scenarios: Stack Overflow: Occurs when attempting to add elements to a full Stack. Stack Underflow: Occurs when attempting to remove elements from an empty Stack. Key Operations on Stack Data Structures The following are some common operations implemented on the stack: push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs. pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state. isEmpty(): It determines whether the stack is empty or not. isFull(): It determines whether the stack is full or not.' peek(): It returns the element at the given position. count(): It returns the total number of elements available in a stack. change(): It changes the element at the given position. display(): It prints all the elements available in the stack. The steps involved in the PUSH operation is given below: - Before inserting an element in a stack, we check whether the stack is full. - If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs. - When we initialize a stack, we set the value of top as -1 to check that the stack is empty. - When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top. - The elements will be inserted until we reach the max size of the stack. POP operation The steps involved in the POP operation is given below: - Before deleting the element from the stack, we check whether the stack is empty. - If we try to delete the element from the empty stack, then the underflow condition occurs. - If the stack is not empty, we first access the element which is pointed by the top - Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1. C++ program to show how to use the stack::push() #include #include using namespace std; int main() { stack st; // Inserting an element in stack // with push() method st.push(0); // Inserting more elements in the stack st.push(1); st.push(2); // Printing stack while (!st.empty()) { cout