Data Structures: Stacks and Lists

Introduction to Data Structures

• Data structures are ways of grouping multiple data elements for faster access and efficient storage.
• They define mechanisms to store, organize, and access data along with operations for efficient processing.
• Examples include strings (sequences of characters) and lists (sequences of potentially different data types).
• An example of an operation that can be performed on a list includes reversal, slicing, counting.
• Organizes multiple elements in a way that operations can be performed easily, on each element, and the collective data unit.
• Examples of important data structures in Computer Science: Array, Linked List, Binary Trees, Heaps, Graph, Sparse Matrix, etc.
• A data structure in which elements are organized in a sequence is a linear data structure.

Stack Data Structure

• Stack and Queue are two popular data structures used in programming.
• A stack is a linear arrangement of elements where new elements are added or removed from the same end, called the "top" of the stack.
• Analogous to piles of books or stacks of plates where items are added or removed from the top, preventing inconvenient access to items in between or at the bottom.
• Follows the Last-In-First-Out (LIFO) principle, meaning the most recently inserted element is the first one to be taken out.

Applications of Stacks

• Real-life examples: piles of clothes in an almirah, multiple chairs in a vertical pile, bangles worn on wrist, piles of boxes of eatables in pantry or on a kitchen shelf.
• Programming Applications include:
  • Reversing a string by traversing it from the last character to the first character and putting characters in a stack.
  • For text/image editors to redo/undo the editing by using stacks to save the recent system editing.
  • Browsing history on the web is as stack. The back button takes you back to the last visited web page i.e a stack order.
  • Compilers use stacks to check for the proper nesting of parentheses in arithmetic expressions.

Stack Operations

• A stack that implements the LIFO arrangement adds and deletes elements from the stack from one end only.
• The end from which elements are added or deleted is called the "top" of the stack.
• The two fundamental operations:
  • PUSH: adds a new element at the top.
  • POP: removes the top element.
• PUSH is an insertion operation, adding elements until the stack is full.
• An attempt to add an element to a full stack results in the 'overflow' exception.
• POP removes the topmost element and is a deletion operation, and can be performed until the stack is empty.
• Trying to delete an element from an empty stack will result in an exception called ‘underflow'.

Stack operations with Python

• Implementing a stack in Python can be easily achieved using the list data type.
• To implement using lists requires implementation of stacks of glasses to insert, delete, check is empty , find # of elements, read out the top most element.
• The methods append() and pop() are built-in list methods for implementation of a stack.
  • insert/delete elements (glasses).
  • check if the STACK is empty (no glasses in the stack).
  • find the number of elements (glasses) in the STACK.
  • read the value of the topmost element (number on the topmost glass) in the STACK.
• glassStack = list() creates an empty stack.
• isEmpty(glassStack) checks if the stack is empty; returns True if empty, otherwise False.
• Returns True if the list is empty with with len(glassStack)==0
• 'opPush(glassStack,element)' inserts a new element and uses the built in append() list method, that always adds to the end of the list.
• 'size(glassStack)' reads the number of elements in the glassStack using len().
• 'top(glassStack)' reads the top most recent element TOP, in the stack.
• 'opPop (glassStack)' is used to delete the topmost element.
• 'display(glassStack)' is used to show contents of the stack.

Arithmetic Expressions and Notations

• Used for writing arithmetic expressions in a program,
• Stacks are used to handle matching parenthesis.

Infix Notation

• Operators are between operands (e.g., x + y, 2 - 3 * y).
• Use parentheses to order the evaluation.
• Follow the BODMAS rule.

Polish or Prefix Notation

• Invented by Jan Lukasiewicz in the 1920s
• Operators are written before operands (e.g., +xy).
• Called prefix notation.
• Order of operations and operands determine result
• Eliminates the need for parenthesis.

Reverse Polish or Postfix Notation

• Operators are positioned after their operands (e.g., xy+).

Conversion from Infix to Postfix

• Stacks are used to keep track of operators encountered in the infix expression during conversion.
• For the conversion algorithm:
  • Algorithm stores converted postfix expressions in a string
  • It inputs infix and processes each character.

Evaluation of Postfix Expressions

• Stacks evaluate expressions in postfix notation.
• Assumes operators are binary.
• In the evaluation algorithm:
  • Postfix expression is input in a variable.
  • The system looks for an operand or character.