Stacks

Data Types

• a set of values
• operations that can be performed on those values
• int, float, double, char(alphabet,+, $, %), boolean, byte

Abstract Data Types(ADT)

• set of value, operaion, algorithm
• Interface
  : type, actual value, operation
• Implementation
  : organization, algorithms

ADT Benefits

• easier to understand, changing, reused, facilitate unit testing

Types of ADTs

Linear ADTs

• Restricted List
  - stack
  - queue
  -General List
  -Arrays
  -Linked List
  -Doubly Linked List
  -Circular Linked List

Non-Linear ADTs
-Tress
-Graphs
-Hash Tables

Stack

• Last In First Out or Fist in Last Out (LIFO, FILO)
• Addition/Removal takes place at same end(TOP)
• base--> bottem longes item
• recently added -->removed first
• Top : newer items

Operations of Stack

• PUSH: Adding elements to the Top of stack
• POP : Deleting elements and accessing elements from the Top of Stack
• TOP : Points to the current newest element of the stack

 

Representation of Stack in Memory

Using arrays (Static implementation)

Using pointer (Dynamic implementation)

Stack Conditions

Stack Overflow
necessary to check if the stack is full
attempt the add an item to a full stack-stack overflow error

Stack underflow
necessary to check if the stack if empty
attempt to remove an item from and empty stack-stack underflow error

stack operation

 

Stack : array implementation

 

stack : pointer implementation

• pointer, node(data/element, pointer)
  

  

  
  

  

Application of stack

• function call mechanisms and recursive programming
• reversing words : push the word to stack ; pop letters from the stack
• Expression Conversion
  -In-fix to Post-fix
  -In-fix to Pre-fix
  -Backtracking
  -Undo mechanisms in word editors
• Language Processing: complier' syntac check for matching braces
• decimal number to binary
• solve tower of Hanoi,Wearing/Removing Bangles
• check if delimiters are matched
  -{,} , [,] , (,)

Arithmetic Expression

• expression: combination of operands and operators that after evaluation results in a single value.
• Operand: constants, variables
• Operators: {, +, -, *, /, ), ]
  Infix Expression
  a+b
  Postfix
  ab+
  Prefix Expression
  +ab

Infix Expression Evaluation

-five types of input characters
-opening brackets, numbers, operators, closing brackets, new line characters
-Data structure requirements : a character stack

Postfix Expression Evaluation

Recursion

• procedure calls itself
  

  

static implementation

dynamic implementation