DSA chapter 4

stack

• Linear list

• All deletions/insertions occur at one end known as the TOP

• Is a LIFO (last in first out structure)

  • Elements are stored by order of insertion from “bottom” to “top”

  • Items are added to the top

  • Only the “top” element can be accessed or removed

goal of stack

Every operation on a stack should be O(1)

basic operations on a stack

• Push

• Pop

• Peek

other stack operations

• initalize():

• isFull():

• isEmpty():

• makeEmpty():

• getSize():

• display():

stack in computer science

• Function/method calls are placed onto stacks

• Compilers use stacks to evaluate expressions

• Stacks are great for reversing things, matching up related pairs of things, and backtracking algorithms

• Stack programming problems:

  • Reverse letters in a string, reverse words in a line, or reverse a list of numbers.

  • Find out whether a string is a palindrome.

  • Examine a file to see if its braces { } and other operators' match.

arrays or linked lists

Stack structures are usually implemented using _____ or _______ _____

array-based stack implementation

• Use TOP variable to represent top most element of stack

• MAX_STACK gives maximum number of elements that can be stored in stack

• Prevents the push operation from adding an item to the stack if the stack’s size limit has been reached.

stack overflow

When new data is to be inserted into a stack but there is no available space

stack underflow

When a data is to be removed/deleted from a stack but there is no available data

linked list implementation of stack

• Pointer based implementation

• Required when the stack needs to grow/shrink dynamically (does not put a limit on the size of the stack)

• TOP is a reference to the head of a linked list of items

applications of stack

• Variable declaration

• Function Calling

• Reversing Data

• Converting Decimal to Binary

• Evaluation of Algebraic expression

• Converting Infix to Postfix

• Page-visited history in a Web browser

• To Undo and Redo in a text editor:

reversing data

Very useful for finding palindromes:

1. read(data)

2. loop (data not EOF and stack not full)

   1. push (data)

   2. read (data)

3. Loop (while stack not empty)

   1. pop (data)

   2. print (data)

converting decimal to binary

1. Read (number)

2. Loop (number > 0)

   1. digit = number modulo (%) 2

   2. print (digit)

   3. number = number / 2

3. push resulting number onto the stack and pop out each digit to print it

types of algebraic expressions

• Infix notation

• Prefix notation

• Postfix notation

infix notation

• A + B

• Used in mathematics

• Suitable for humans'

• Uses BODMAS

prefix notation

• + A B

• C++ notation for functions (add(A, B))

postfix notation

• A B +

• Suitable for computers

• Arithmetic and Logical Unit (ALU) designed using this notation

advantage of using postfix notation

• No need to apply operator precedence and other rules

• Parentheses are unnecessary

• Easy for the compiler to evaluate an arithmetic expression

• Is taken from post-order traversal of an expression tree

postfix expression evaluating algorithm

• An algorithm exists to evaluate postfix expressions using a stack.

• The single value on the stack is the desired result.

• Binary operators: +, -, *, /, etc.,

• Unary operators: unary minus, square root, sin, cos, exp, etc.,

converting infix to postfix

1. Parenthesize from left to light, higher precedence operators parenthesized first.

2. The sub-expression (part of expression), which has been converted into postfix, is treated as single operand.

3. Once the expression is converted to postfix form, remove the parenthesis.

importance of infix to postfix conversion

• In high level languages, infix notation cannot be used to evaluate expressions.

• We must analyze the expression to determine the order in which we evaluate it.

• A common technique is to convert an infix notation into postfix notation, then evaluating it.

1. Operands immediately go directly to output

2. Operators are pushed into the stack (including parenthesis)

• Check to see if stack top operator is less than current operator

  • If the top operator is less than, push the current operator onto stack

• If the top operator is greater than the current, pop top operator and append on postfix notation, push current operator onto stack.

• If we encounter a right parenthesis, pop from stack until we get matching left parenthesis. Do not output parenthesis.

precedence of operators in postfix notation

• Priority 4: ‘(‘ - only popped if a matching ‘)’ is found.

• Priority 3: All unary operators (-, sine, cosine,….)

• Priority 2: / *

• Priority 1: + -

undo and redo in a text editor

Pseudocode:

• Accept the command

• if(command==Undo)

  • push_RS(pop_US( ))

• else if(command==Redo)

  • push_US(pop_RS())

• else

  • push_US(command)