Python Data Structure Stacks Notes & Important Points
Introduction:
A data structure is a group of data that have different data types which can be accessed as a unit. It has well-defined operations, properties and behaviours. Data structure is a way of storing and organising information in the computer. General data structure types include array, file, record, table, tree and so on.
Advantages of Data Structure
- Data structures are used in almost every program or software.
- Specific data structures are essential ingredients of many efficient algorithms and make possible the management of huge amounts of data, such as a large integrated collection of databases.
- Some programming languages emphasize data structures rather than algorithms as the key organising factor in software design.
Types of Data Structure
- Linear data structures These are single-level data structures, having their elements in a sequence. e.g. array, stack, queue and linked list.
- Non-linear data structures These are multilevel data structures. e.g. tree and graph.
On the basis of their expansion i.e. size, Data structures can be classified as
- Static data structures These data structures are those whose size, structure, and associated memory locations are fixed at compile time. e.g. array, list, tuple
- Dynamic data structures These data structures are those, which can shrink or expand as required during the program execution and their associated memory locations that will be changed. e.g. linked list.
Common Data Structures :
Array It refers to the name of list of elements in a specific order, typically all elements are of the same type. Elements are accessed using index number. Arrays may be fixed length or resizable
Stack is a LIFO (Last In First Out) data structure which allows last in first out. In stack insertion and deletion of elements take place at one end called the top of the stack. It has two main operation : Push, which adds an element to the collection and Pop, which removes the last element that was added.
Queue It is also a limited form of array based on FIFO (First In First Out), where insertion of elements take place at one end called the Front and deletion of elements take place at the other end called the Rear.
Linked list – is a data structure that consists of nodes. Each node in the linked list contains data and the next/link pointer. Where the data part stores the information while the next/link stores the address of the next node. It is a dynamically memory-allocated data structure.
Basic Operations performed on Data Structure
- Insertion – Adding a new data element to a data structure.
- Deletion – Removing a data element from a data structure.
- Searching – Searching for the specific data element in a data structure.
- Traversal – means accessing and processing all the data elements.
- Sorting – means arranging data elements of a data structure in a specific order (ascending/increasing or descending/decreasing).
- Merging – Combining elements of two similar data structures to form a new data structure of the same type is called merging.
What is Stack?
A stack is a linear or user-defined data structure based on the principle of Last In First Out (LIFO).
A stack is a list where insertion and deletion can take place only at one end called Top.
A static stack (fixed size) can be implemented using list, tuples, array and A dynamic stack (size is depends on memory) can be implemented using linked list structure.
Uses of Stack:
Stacks are used in the basic design of an operating system for interrupt handling and operating system method calls.
Some of the examples of stack in real life are
- Stack of coins.
- Plates are placed one above another.
- Pile of books.
- Pile of clothes in an almirah.
- Multiple chairs in a vertical pile.
Implementation of Stack
Stack is open at one end, so operations can be performed on a single end. We have two primitive operations that can be performed on stack data structure:
(i) Push
(ii) Pop
Stack Terminology:
| Terms / Operations | Definition / Explanation |
| TOP | TOP variable or pointer points at the topmost position i.e. last item/element of stack. |
| PUSH | The procedure of inserting a new element to the top of the stack is known as PUSH operation. |
| POP | The procedure of removing/deleting elements from the top of the stack is called POP operation. |
| PEEK | Refer to the inspecting the value at the stack’s top without moving it. It is also sometimes referred to as inspection. |
| UNDERFLOW | UNDERFLOW is an error condition, it occurs when the STACK is EMPTY, and try to delete an item from the stack. |
| OVERFLOW | OVERFLOW is an error, it occurs when STACK is full, and you try to insert new element in the stack. |
PUSH and POP Operations
PUSH adds a new element at the TOP of the stack. It is an insertion operation. We can add elements to a stack until it is full.
A stack is full when no more elements can be added to it. Add an element to a full-stack results in an exception called ‘overflow’
Summary (NCERT book based):
Stack is a data structure in which insertion and deletion is done from one end only, usually referred to as TOP.
Stack follows LIFO principle using which an element inserted in the last will be the first one to be out.
PUSH and POP are two basic operations performed on a stack for insertion and deletion of elements, respectively.
Trying to pop an element from an empty stack results into a special condition underflow.
In Python, list is used for implementing a stack and its built-in-functions append and pop are used for insertion and deletion, respectively. Hence, no explicit declaration of TOP is needed.
Any arithmetic expression can be represented in any of the three notations viz. Infix, Prefix and Postfix.
While programming, Infix notation is used for writing an expression in which binary operators are written in between the operands.
A single traversal from left to right of Prefix/ Postfix expression is sufficient to evaluate the expression as operators are correctly placed as per their order of precedence.
Stack is commonly used data structure to convert an Infix expression into equivalent Prefix/Postfix notation.
While conversion of an Infix notation to its equivalent Prefix/Postfix notation, only operators are PUSHed onto the Stack.
When evaluating any Postfix expression using Stack, only operands are PUSHed onto it.
- CBSE Board Class 12 Answer Key Computer Science 083
- Class 12 Computer Science Ch 11 Data Communication NCERT Book Exercise Solution
- Class 12 Computer Science Answer Key (083) Term 1 Question Paper download pdf
- Class 11 Computer Science Chapter 5 Getting Started with Python NCERT Solution
- Input Output in Python
- Python Data Types
- Class 12 Computer Science File Handling in Python NCERT Exercise solution
- Class 12 Computer Science – Exception Handling in Python NCERT Exercise Solutions
- Python 3 Setup and Installation Guide
- Encoding Schemes and Number Systems NCERT Exercise solutions
- Python Important Programs and Practical’s
- CBSE Annual Exam Question Paper for Class 11 Computer Science Sample Papers
- Ch 2 Emerging Trends NCERT Exercise Solution – Class 11 Computer Science
- 110+ Important Networking Full Form List – Download PDF
- Class 12 Computer Science NCERT Exercise Solution
- Class 11 Computer Science NCERT Exercise Solution
- Computer System: Overview – Notes
- Number Systems & Encoding Scheme – Notes
- Boolean Logics – Notes
- Emerging Trends – Notes
- Introduction to Problem Solving – Notes
- Getting Started with Python – Notes
- Python Fundamentals – Notes
- Data Handling – Notes
- Tuples Manipulation in Python Notes
- Introduction to Python Module – Notes
- Python Revision Tour I : Basics of Python – Notes
- Data Structure: Stacks – Notes
- Society, Law, and Ethics: Societal Impacts – Notes
