DancingWithDataStructures: Stacks and Queues

Introduction to Data Structures

Stack:

A sequential data structure that resembles a stack. Imagine a stack of plates: you would put one on top of the other and you would remove plates by removing the ones on top first. So basically: last in first out

Queue:

Also a sequential data structure, just like the name suggests it is just line that earlier data would be removed first. So: first in first out

Why learning these:

Although it is unlikely that you would have to implement these when you are coding for work or personal projects because Array can pretty much do all things Stack and Queue

During interviews, interviewers might still asks you to re-implement them to see if you know common data structures and algorithms.

Implementation

how would you implement these two classes?

Requirements:

1. both would need the following properties:
2. implement them without using Arrays

Methods:

for stack: insert, remove, peak, for queue: enqueue, dequeue, peek,

Attributes:

for both: length

Classic Questions

balanced Parens

Write a function that takes a string checks and see if all the parentheses match correctly

Ex:

  balancedParens('(hi)');
  // returns true
  balancedParens('}nope{');
  // returns false

current min of a stack

Write a method that returns the current minimum value of a stack without going through the entire stack.

  var stack = new Stack();
  stack.insert(4);
  stack.insert(8);
  stack.currentMin();
  // returns 4;
  stack.insert(1);
  stack.currentMin();
  // return 1;

  stack.remove();
  stack.remove();
  // both 1 and 8 are removed
  stack.currentMin();
  // returns 4;

Reimplementation(Using Other Data Structures)

using at most two stacks to implement a queue class

Define a Queue class by using at most two stacks Design an experiment to test the performance of your implementations

Next Steps

Check out linked lists, and reimplement the queue again using this type of data structure (link), and compare the performance with your earlier implementations.

Build a calculator using your new found knowledge of stacks