Lesson 6 Stack and queue

Stack

Stack for Expression Evaluation

a/b-c+d_e-a_c

• procedence:{*, /} first; {+,_} later

• steps

  • f = a/b
  • g = f-c
  • h = d*e
  • i = g+h
  • j = a*c
  • l = i-j

Postfix Notation
same operand order,but put “operator” after needed operands
example : a b / ; f c -; d e
*tanslate to the computer computation language

Postfix from Infix (Usual) Notation

• infix:
  3 / 4 - 5 + 6 7 - 8 9
• parenthesize:
  ((((3/4)-5)+(6_7))-(8_9))
• for every triple in parentheses, switch orders
  (((3 4 /)5 -) (6 7 )+) (8 9 )-)
• remove parentheses
  3 4 / 5 - 6 7 + 8 9 -

Evaluate Postfix Expressions

    34/5-67*+89*-

• how to evaluate? left-to-right, “operate” when see operator
• 3, 4, / 0.75
• 0.75 ,5, - -4.25
• -4.25, 6, 7, * -4.25, 42(note: -4.25 stored for latter use)
• -4.25, 42, + 37.75
• 37.75, 8, 9, * 37.75, 72 (note: 37.75 stored for latter use)
• 37.75, 72, - …

Stack so closest operands will be considered first
Every time meets a number, push it to the stack. While meets operator, take the two closest numbers and calculate.

• Pstfix Evaluation Pseudocode

for each token in the input do
    if token is a number
        push token to the stack
    else if token is an operator
        sequentially pop operands $a_{t-1},...,a_0$ from the stack
        push token$a_0,a_1,a_{t-1}$ to the stack
    end if
end for
return the top of stack

Application: Expression Parsing

One-Pass Algorithm for Infix to Postfix

infix postfix efficiently?
a/b -c + d e - a c

• at /, not sure of what to do (need later operands) so store

• at -, know that a/b can be a b / because - is of lower precedence

• at +, know that ? -c can be ? c- because + is of same precedence but {-, +} is left-associative

• at *, notsure of what to do (need later operands) so store

• Stack Solution to infix-Postfix Translation

for each token in the input do
    if token is a number
        output token
    else if token is an operator
        while top of stack is of higher(or same) precedence do
            pop and output top of stack
        end while
        push token to the stack
    end if
end for

• here: infix to postfix with operator stack: closest operators will be considered first
• recall: postfix evaluation with operand stack: closest operands will be considered first
• mixing the two algorithms(say, use two stacks): simple calculator

More Hints on Infix-Postfix Translation

• for left associativity and binary operators

  • right associativity? same precedence needs to wait
  • unary/trinary operator? same

• parentheses? highest priority

  • at ‘(‘ cannot pop anything from stack
    —like seeing ‘*’ while having ‘+’ on the stack
  • at ‘)’, can pop until ‘(‘ —-like parentheses matching

What We Have Done

Queue

The Maze Problem

Given a (2D) maze, is there a way out?

Recursive Algorithm

GET-OUT-RECURSIVE(m(0,0))

GET-OUT-RECURSIVE(Maze m, Position(i,j))
    mark(i,j) as visited
    for each unmarked (k,l) reachable from (i,j) do
        if (k,l) is an exit
            return TRUE
        end if
        if GET-OUT-RECURSIVE(m,(k,l))
            return TRUE
        end if
    end for
    return FALSE

From Recursion to Stack
GET-OUT-STACK(Maze m, Position(i,j))

    while stack not empty do
        (i,j)<-pop from stack
        mark (i,j) as visited
        for each unmarked (k,l) rechable from(i,j) do
            if (k,l) is an exit
                return TRUE
            end if
            push(k,l) to stack and mark(k,l) as todo
        end for
    end while
    return FALSE

• similar result to recursive version, but conceptually different

  • recursive: one path on the system stack
  • stack: many positions-to-be-explored on the user stack

A General Maze Algorithm

GET-OUT-CONTAINER(Maze m, Position(i,j))

    while container not empty do
        (i,j) <- remove from container
        mark (i,j) as visited
        for each unmarked (k,l) reachable from (i,j) do
            if (k,l) is an exit
                return TRUE
            end if
            insert(k,l) to container [and mark (k,l) as todo]
        end for
    end while
    return FALSE

• if “random” remove from container: “random walk” to exit

Queues

Queue

• object: a container that holds some elements
  

• action: [constant-time] enqueue (to the rear), dequeue (from the front)

• first-in-first-out (FIFO): buy ticket

• also very restricted data structure, but also important for computers

implementation

• A C++ Queue Interface

template<typename E>
class Queue{
public:
    int size() const;
    bool empty() const;
    const E& front() const throw(QueueEmpty);
    void enqueue(const E& e);
    void dequeue() throw(QueueEmpty);
}

• Implementing a Queue with a Circularly Linked List
  

typedef string Elem; // queue element type
class LinkedQueue { // queue as doubly linked list
public:
    LinkedQueue(); // constructor
    int size() const; // number of items in the queue
    bool empty() const; // is the queue empty?
    const Elem& front() const throw(QueueEmpty); // the front element
    void enqueue(const Elem& e); // enqueue element at rear
    void dequeue() throw(QueueEmpty); // dequeue element at front
private: // member data
    CircleList C; // circular list of elements
    int n; // number of elements
}

Maze From Stack to Queue

GET-OUT-QUEUE(Maze m, Postion(i,j))

    while queue not empty do
        (i,j) <- dequeue from queue
        mark (i,j) as visited
        for each unmarked (k,l) reachable from (i,j) do
            if (k,l) is an exit
                return TRUE
            end if
            enqueue(k,l) to queue [and mark (k,l) as todo]
        end for
    end while
    return FALSE

• use of stack/queue: store the yet-to-be-explored positions
• stack version: first(lexicographically) way out (explore deeply) —-depth-first search (DFS)
• queue version: shortest way out (explore broadly) —-breadth-first search (BFS)