CS174: Stack And Queue ADTs

Developed by Professor Tralie and Professor Mongan.

Watch the video below on the Stack and Queue abstract data types. Code can be found at this link.

Notes

  • An abstract data type (ADT) is a specification of functionality of a data container, without specifying how it's actually going to work.

  • A Stack is an abstract data type which is Last In First Out (LIFO); that is, we add something to the top of it with push(), and we remove what's at the top with pop(). In other words, we remove and add from the same place

  • A Stack can be implemented efficiently with an underlying singly-LinkedList

  • A Queue is an abstract data type which is First In First Out (FIFO); that is, we add something to the end of the line with enqueue(), and we remove what's at the front of the line with dequeue()

  • We cannot implement a Queue efficiently with a singly-linked list, because adding to the end of a singly-linked list is expensive; we have to loop through all elements of the list until we get there.

Code

Click here to see the code from the video