View on GitHub


This is the lab related content for the module CS2040C (Data structures and Algorithms)

Lab 04

Here is a pdf version of the ppt I covered during the lab. And the codes that I (skimmed through) / (demonstrated live).

content.pdf (The pdf version of the ppt shown)

postfix_eval.cpp (Using STL Stack to evaluate a postfix expression)

Challenge Questions -

Q) Try to modify/implement a new postfix evaluator which can take in numbers consisting of more than 1 digit.

Solution TBA

Q) Read up/Try to find the differences between STL Deque (Double Ended Queue) and STL List (Doubly linked list)

Solution Apart from that the broad differences I am able to find are -
  1. DEQUE is like a superset of VECTOR. It is VECTOR ABILITIES + PUSH_FRONT + POP_FRONT.
  2. The only feature lacking in DEQUE that is there in vector is mehtod capacity and reserve.
  3. List differs from vector, in mainly back-end implementation and some pros and cons as follows -
    1. Vector/Deque has O(constant time) access to a random element, whereas List has O(N).
    2. List can do insertion in O(1) in between, given it has an iterator to the immediate previous/next element where we want to insert. For a vector/deque the insertion in between is always O(N) (irrespective of the fact that we have an iterator or not)

Visit here for more info