InstructorBasarat Ali Syed

Published 7 years ago

Updated 3 years ago

A stack is an abstract data type that stores a collection of elements, with two principal operations:

- push: adds an element to the collection
- pop: removes the most recently added element that was not yet removed.

The order in which elements are poped is `Last In First Out`

aka. `LIFO`

. In this lesson we discuss how to implement it using JavaScript / TypeScript.

[00:00] A stack is a last-in/first-out data structure with key operations having a time complexity of O(1). We can model this easily in TypeScript using the generic class for items of type T.

[00:22] The stack data structure has two key operations. The first one is push, which adds an item in O(1). The other key operation pops an item from the stack, again in O(1). If there are no more items, we can return an out-of-bound value, for example, undefined. This fact can be modeled into the type system by using a union of T and undefined.

[01:00] The objective is to implement these push and pop operations such that they operate in O(1) time. Fortunately, in JavaScript implementations, array functions that do not require any changes to the index of the current items have an average runtime of O(1).

[01:18] Therefore, we can simply implement the operations of this data structure using an array. On push, we simply push the new item into the array. As it doesn't change the index of the current items, this is O(1). Similarly, on pop, we simply pop the last value from the array. Again, it doesn't change the index of the other items in the array, so it is O(1).

[01:47] A common additional operation for collection data structures is the size, as it allows you to safely iterate the elements and find out if there are any more elements present in the data structure. Fortunately, JavaScript arrays implement this for us in the form of the length property.

egghead

~ an hour ago

Markdown supported.

Become a member to join the discussionEnroll Today

Member comments are a way for members to communicate, interact, and ask questions about a lesson.

The instructor or someone from the community might respond to your question Here are a few basic guidelines to commenting on egghead.io

Be on-TopicComments are for discussing a lesson. If you're having a general issue with the website functionality, please contact us at support@egghead.io.

Avoid meta-discussionCode Problems?Should be accompanied by code! Codesandbox or Stackblitz provide a way to share code and discuss it in context

Details and ContextVague question? Vague answer. Any details and context you can provide will lure more interesting answers!