stacks_n_queues.md

Stacks and Queues

Restricted forms of list: Sometimes we only want to insert or remove from one end of the list

Queue ADT

• Elements are added to the rear and removed from the front
• A queue is a FIFO "first in, first out" list

Operations

• enqueue
• dequeue

change states

• front
• isEmpty
• size

observe states

For what types of problems would queue be useful?

Various servers that serve requests in First Come First Serve order

• printer server (a queue of print jobs),
• disk driver (a queue of disk input/output requests)
• CPU scheduler (a queue of processes waiting to be executed)

Implementation

• Array-based queue
• Linked queue

Code could be found in textbook; explanation in VoiceThread

Key points: All operations take constant time

Stack ADT

• Elements are added and removed from only one end (i.e.,at the top of the stack)
• A stack is a LIFO "last in, first out" list

For what types of problems would stack be useful?

• LIFO: good for reversing data
  • If we push a, b, c, d into a stack, and then pop all elements out, we get d, c, b, a
• In OS/language: function call stack
• Finding Palindromes
• Expression evaluation and syntax parsing

Use stack to reverse

Sometimes you need to output in reverse orders

// Convert decimal to binary
DisplayInBinary(int num)
    while (num > 0)
        digit = num % 2 // remainder
        print digit
        num = num / 2   // quotient

The binary representation is printed backward (Trace it with num=4, outputs 001)

Solution: push each digit onto a stack in the loop, after the loop, pop digits out one by one and display

Operations

• push
• pop

change states

• top
• isEmpty
• size

observe states

Implementation

• Array-based stack
• Linked stack (LStack in Lab 5)

Code could be found in textbook

Key points: All operations take constant time

C++ Standard Template Library

A set of C++ class templates that provides common programming data structures and functions: http://www.cplusplus.com/reference/stl/

All data structures/container are implemented as class template, which can be parameterized

• vector<int>, vector<char>, ...
• stack<int>, stack<double>, ...
• the type in <> is type parameter, specifying the type of items

Sample code using STL stack

#include <iostream>
#include <stack>
using namespace std;

void showStack(stack<int> s) {
    while (!s.empty()) {
        cout << '\t' << s.top();
        s.pop();
    }
    cout << endl;
}

int main() {
    stack<int> s;
    s.push(10);
    s.push(30);
    s.push(20);

    cout << "Size:\t" << s.size() << endl;

    cout << "Stack:";
    showStack(s);

    return 0;
}

Lab 5: Stacks

1. Check for balanced brackets '(', ')', '{', '}', '[', ']'
2. Decoding strings

Proj 1: Integers of Unlimited Size

1. Implement BigInt to store integers of unlimited size (using list)
2. Basic calculator for BigInt using stack