Shtack

LIFO Stacks for ES6

Description

ES6 implementation of the stack data structure with TypeScript support.

Come over to Twitter to share your thoughts on the project.

Visit the contributing guidelines to learn more on how to translate this document into more languages.

Contents

• Description
• Install
• In Depth
• Usage
• API
• Development
• Related
• Team
• License

Install

Yarn

yarn add shtack

NPM

npm install shtack

In Depth

A stack is an data structure that serves as a collection of elements, with two principal operations:

• push which adds an element to the collection, and
• pop which removes the most recently added element that was not yet removed.

Additionally, a peek operation gives access to the top element without mutating the stack. The order in which elements come off a stack gives rise to its alternative name, LIFO which stands for last in, first out. Shtack stacks are implemented using a linear singly linked list as their backbone, since stacks are linear data structures, or more abstractly sequential collections, where the push and pop operations occur only at one end of the structure, referred to as the top of the stack, which internally corresponds to the head node of the singly linked list.

Usage

Shtack exposes a chainable API, that can be utilized through a simple and minimal syntax, allowing you to combine methods effectively.

Usage examples can be also found at the test directory.

'use strict';
const {Stack} = require('shtack');

const stack = new Stack();
//=> Stack { head: null, size: 0 }

stack.isEmpty();
//=> true

stack.push(10);
//=> Stack { head: Item { value: 10, next: null }, size: 1 }

stack.isEmpty();
//=> false

stack.peek();
//=> 10

stack
  .push(20)
  .push(30)
  .push(40)
  .push(50);
//=> Stack { head:
// Item { value: 50, next:
// Item { value: 40, next:
// Item { value: 30, next:
// Item { value: 20, next: 
// Item { value: 10, next: null } } } } }, size: 5 }

stack.includes(30);
//=> true

stack.includes(60);
//=> false

stack.pop();
//=> 50

stack.peek();
//=> 40

stack.toArray();
//=> [ 40, 30, 20, 10 ]

stack.rotateRight(3);
//=> Stack { head:
// Item { value: 10, next:
// Item { value: 40, next:
// Item { value: 30, next:
// Item { value: 20, next: null } } } }, size: 4 }

stack.toArray();
//=> [ 10, 40, 30, 20 ]

stack.rotateLeft(1);
//=> Stack { head:
// Item { value: 20, next:
// Item { value: 10, next:
// Item { value: 40, next:
// Item { value: 30, next: null } } } }, size: 4 }

stack.toArray();
//=> [ 20, 10, 40, 30 ]

stack
  .swap()
  .duplicate()
  .toArray();
//=> [ 10, 10, 20, 40, 30 ]

stack.reverse().toArray();
//=> [30, 40, 20, 10, 10]

API

stack.size

• Return Type: Number

Returns the total number of values in the stack.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30);
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } }, size: 3 }
stack.size;
//=> 3

stack.clear()

• Return Type: Stack

Mutates the stack by removing all residing values and returns it empty.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30);
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } }, size: 3 }
stack.size;
//=> 3
stack.clear();
//=> Stack { head: null, size: 0 }
stack.size;
//=> 0

stack.duplicate()

• Return Type: Stack

Mutates the stack by removing the top-most value, and then pushing it twice, so that an additional copy of the former top-most value is now on the top, with the original below it. Returns the stack itself.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30);
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } }, size: 3 }
stack.duplicate();
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } } }, size: 4 }

stack.forEach(fn)

• Return Type: Stack

Traverses the stack, top to bottom, and executes the provided fn function once for each traversed element without mutating the stack. Returns the stack itself at the end of the traversal.

fn

• Type: Function

Unary function to execute for each traversed value.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30)
  .push(40);
//=> Stack { head:
// Item { value: 40, next:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } } }, size: 4 }
stack.forEach(console.log);
//=> 40
// 30
// 20
// 10

stack.includes(value)

• Return Type: Boolean

Determines whether the stack includes a certain value, returning true or false as appropriate.

value

• Type: Any

Value to search for.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30);
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } }, size: 3 }
stack.includes(10);
//=> true
stack.includes(40);
//=> false
stack.includes(20);
//=> true

stack.isEmpty()

• Return Type: Boolean

Determines whether the stack is empty, returning true or false as appropriate.

const {Stack} = require('shtack');

const stack = new Stack();

stack.push(10);
//=> Stack { head: Item { value: 10, next: null }, size: 1 }
stack.isEmpty();
//=> false
stack.clear().isEmpty();
//=> true

stack.peek()

• Return Type: Any | undefined

Returns the top-most value of the stack, without mutating the stack itself. If the stack is empty undefined is returned.

const {Stack} = require('shtack');

const stack = new Stack();

stack.push(10);
//=> Stack { head: Item { value: 10, next: null }, size: 1 }
stack.peek();
//=> 10

stack.pop()

• Return Type: Any | undefined

Mutates the stack by removing and returning the top-most value. If the stack is empty undefined is returned.

const {Stack} = require('shtack');

const stack = new Stack();

stack.push(10);
//=> Stack { head: Item { value: 10, next: null }, size: 1 }
stack.pop();
//=> 10
stack.pop();
//=> undefined

stack.push(value)

• Return Type: Stack

Mutates the stack by inserting a new value at the top. Returns the stack itself.

value

• Type: Any

Value to insert.

const {Stack} = require('shtack');

const stack = new Stack();

stack.push(10);
//=> Stack { head: Item { value: 10, next: null }, size: 1 }
stack.push(20).push(30);
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } }, size: 3 }
stack.size;
//=> 3

stack.reverse()

• Return Type: Stack

Mutates the stack by reversing in-place the contained values. The top-most value becomes the bottom-most one, and the bottom-most one becomes the top-most. Returns the stack itself.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30);
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } }, size: 3 }
stack.reverse();
//=> Stack { head:
// Item { value: 10, next:
// Item { value: 20, next:
// Item { value: 30, next: null } } }, size: 3 }

stack.rotateLeft(n)

• Return Type: Stack

Mutates the stack by moving the n bottom-most values to the top in a rotating fashion. Returns the stack itself.

n

• Type: Number

Number of bottom-most values to be rotated.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30)
  .push(40)
  .push(50);
//=> Stack { head:
// Item { value: 50, next:
// Item { value: 40, next:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } } } }, size: 5 }
stack.toArray();
//=> [ 50, 40, 30, 20, 10 ]
stack.rotateLeft(2);
//=> Stack { head:
// Item { value: 20, next:
// Item { value: 10, next:
// Item { value: 50, next:
// Item { value: 40, next:
// Item { value: 30, next: null } } } } }, size: 5 }
stack.toArray();
//=> [ 20, 10, 50, 40, 30 ]

stack.rotateRight(n)

• Return Type: Stack

Mutates the stack by moving the n top-most values to the bottom in a rotating fashion. Returns the stack itself.

n

• Type: Number

Number of top-most values to be rotated.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30)
  .push(40)
  .push(50);
//=> Stack { head:
// Item { value: 50, next:
// Item { value: 40, next:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } } } }, size: 5 }
stack.toArray();
//=> [ 50, 40, 30, 20, 10 ]
stack.rotateRight(2);
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next:
// Item { value: 50, next:
// Item { value: 40, next: null } } } } }, size: 5 }
stack.toArray();
//=> [ 30, 20, 10, 50, 40 ]

stack.swap()

• Return Type: Stack

Mutates the stack by exchanging the positions of the two top-most values. Returns the stack itself.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30);
//=> Stack { head:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } }, size: 3 }
stack.toArray();
//=> [ 30, 20, 10 ]
stack.swap();
//=> Stack { head:
// Item { value: 20, next:
// Item { value: 30, next:
// Item { value: 10, next: null } } }, size: 3 }
stack.toArray();
//=> [ 20, 30, 10 ]

stack.toArray()

• Return Type: Array<Any>

Traverses the stack, from top to bottom, and stores each traversed value in an array. The array is returned at the end of the traversal.

const {Stack} = require('shtack');

const stack = new Stack();

stack
  .push(10)
  .push(20)
  .push(30)
  .push(40)
  .push(50);
//=> Stack { head:
// Item { value: 50, next:
// Item { value: 40, next:
// Item { value: 30, next:
// Item { value: 20, next:
// Item { value: 10, next: null } } } } }, size: 5 }
stack.toArray();
//=> [ 50, 40, 30, 20, 10 ]

Development

For more info on how to contribute to the project, please read the contributing guidelines.

• Fork the repository and clone it to your machine
• Navigate to your local fork: cd shtack
• Install the project dependencies: npm install or yarn install
• Lint the code and run the tests: npm test or yarn test

Related

• avlbinstree - AVL self-balancing binary search trees for ES6
• binoheap - Binomial heaps for ES6
• binstree - Binary search trees for ES6
• doublie - Doubly circular & linear linked lists for ES6
• kiu - FIFO Queues for ES6
• mheap - Binary min & max heaps for ES6
• prioqueue - Priority queues for ES6
• singlie - Singly circular & linear linked lists for ES6

Team

• Klaus Sinani (@klaussinani)

License

MIT