We use the Stack data structure to create a pile of data/information one after another and then process those from top to bottom. Items of a stack are accessed/processed on a Last-in-First-out basis. Stack support push and pop from the top.
NOTE
In this article, we are discussing in detail, the implementation of Stack in JavaScript and TypeScript.
In JavaScript we can implemen stack in 2 ways-
- Using Linked list
- Using JavaScript Array
Let’s check the implementation step by step-
Implementation #1: Stack using Linked List
Let’s implement the Stack data structure using Singly Linked List–
- The last inserted/added node is the “Top”.
- To push an item we add a new to at the “Top”.
- To pop items we remove them from “Top”.
Step #1: Node(Stack item) Class
We need a node class to store the Stack item.
// Node class for storing data and reference to the next node
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Node<T> {
data: T;
next: Node<T> | null;
constructor(data: T) {
this.data = data;
this.next = null;
}
}
NOTE
For TypeScript we are using a generic and passing the type as <T>. This “T” type will be the type of data.
Step #2: Stack Class
Stack class has 2 main functionality – push and pop.
// Stack class
class Stack {
constructor() {
this.top = null;
this.size = 0;
}
}
// Stack class
class Stack<T> {
public top: Node<T> | null;
public size: number;
constructor() {
this.top = null;
this.size = 0;
}
}
NOTE
For TypeScript we are using a generic and passing the type as <T>. We need to pass this type <T> to the “Node” item.
Step #3: Push
Add an item to top to push-
class Stack {
// ...
push(data) {
const newNode = new Node(data);
if (!this.top) {
this.top = newNode;
} else {
newNode.next = this.top;
this.top = newNode;
}
this.size++;
return this.size;
}
// ...
}
class Stack<T> {
//...
push(data: T): number {
const newNode = new Node(data);
if (!this.top) {
this.top = newNode;
} else {
newNode.next = this.top;
this.top = newNode;
}
this.size++;
return this.size;
}
//...
}
Step #4: Pop
Remove an item from the top to Pop-
class Stack {
// ...
pop() {
if (!this.top) {
return null; // Or return your expected empty value
}
const existingTop = this.top;
this.top = this.top.next;
this.size--;
return existingTop.data;
}
}
class Stack<T> {
//...
pop(): T|null {
if (!this.top) {
return null; // Or return your expected empty value
}
const existingTop = this.top;
this.top = this.top.next;
this.size--;
return existingTop.data;
}
//...
}
Full Implementation Code
Here is the full implementation, with all the functionality.
// stack.js
// Implementation of stack using Linked List
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
class Stack {
constructor() {
this.top = null;
this.size = 0;
}
push(data) {
const newNode = new Node(data);
if (!this.top) {
this.top = newNode;
} else {
newNode.next = this.top;
this.top = newNode;
}
this.size++;
return this.size;
}
pop() {
if (!this.top) {
return null; // Or return your expected empty value
}
const existingTop = this.top;
this.top = this.top.next;
this.size--;
return existingTop.data;
}
}
export default Stack;
// stack.ts
// Implementation of stack using Linked List
class Node<T> {
data: T;
next: Node<T> | null;
constructor(data: T) {
this.data = data;
this.next = null;
}
}
class Stack<T> {
public top: Node<T> | null;
public size: number;
constructor() {
this.top = null;
this.size = 0;
}
push(data: T): number {
const newNode = new Node(data);
if (!this.top) {
this.top = newNode;
} else {
newNode.next = this.top;
this.top = newNode;
}
this.size++;
return this.size;
}
pop(): T|null {
if (!this.top) {
return null; // Or return your expected empty value
}
const existingTop = this.top;
this.top = this.top.next;
this.size--;
return existingTop.data;
}
}
export default Stack;
Demo
Here is the demo code for using the implemented functionality of Stack-
// demo.js
import Stack from "./stack.js";
// Create a new Stack
let bigboxStack = new Stack();
console.log("\n\n----------- Stack Push example -----------\n");
// Push items
console.log('Push - "Big" | Result: ', bigboxStack.push("Big"));
console.log('Push - "Box" | Result: ', bigboxStack.push("Box"));
console.log('Push - "Code" | Result: ', bigboxStack.push("Code"));
console.log("\n\n----------- Stack Pop example -----------\n");
// Pop items
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
// demo.ts
import Stack from "./stack";
// Create a new Stack
let bigboxStack = new Stack<string>();
console.log("\n\n----------- Stack Push example -----------\n");
// Push items
console.log('Push - "Big" | Result: ', bigboxStack.push("Big"));
console.log('Push - "Box" | Result: ', bigboxStack.push("Box"));
console.log('Push - "Code" | Result: ', bigboxStack.push("Code"));
console.log("\n\n----------- Stack Pop example -----------\n");
// Pop items
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
Output:
Output of the demo code will look like below-
----------- Stack Push example -----------
Push - "Big" | Result: 1
Push - "Box" | Result: 2
Push - "Code" | Result: 3
----------- Stack Pop example -----------
Pop | Result: Code
Pop | Result: Box
Pop | Result: Big
Pop | Result: null
Tests
Let’s test the functionality using automated testing. Use the following code for testing.
// stack.test.js
import { describe, it, beforeEach, expect } from "vitest";
import Stack from "./stack";
describe("Stack using Linked List", () => {
describe("Push item to Stack", () => {
let stack;
beforeEach(() => {
stack = new Stack();
});
it("Should push items correctly", () => {
let length = stack.push("Big");
expect(length).toBe(1);
length = stack.push("Box");
expect(length).toBe(2);
length = stack.push("Code");
expect(length).toBe(3);
});
});
describe("Pop item from Stack", () => {
let stack;
beforeEach(() => {
stack = new Stack();
// Push some items first
stack.push("Big");
stack.push("Box");
stack.push("Code");
});
it("Should pop item correctly", () => {
let item = stack.pop();
expect(item).toBe("Code");
item = stack.pop();
expect(item).toBe("Box");
item = stack.pop();
expect(item).toBe("Big");
item = stack.pop();
expect(item).toBeNull();
});
});
});
// stack.test.ts
import { describe, it, beforeEach, expect } from "vitest";
import Stack from "./stack";
describe("Stack using Linked List", () => {
describe("Push item to Stack", () => {
let stack: Stack<string>;
beforeEach(() => {
stack = new Stack<string>();
});
it("Should push items correctly", () => {
let length = stack.push("Big");
expect(length).toBe(1);
length = stack.push("Box");
expect(length).toBe(2);
length = stack.push("Code");
expect(length).toBe(3);
});
});
describe("Pop item from Stack", () => {
let stack: Stack<string>;
beforeEach(() => {
stack = new Stack<string>();
// Push some items first
stack.push("Big");
stack.push("Box");
stack.push("Code");
});
it("Should pop item correctly", () => {
let item = stack.pop();
expect(item).toBe("Code");
item = stack.pop();
expect(item).toBe("Box");
item = stack.pop();
expect(item).toBe("Big");
item = stack.pop();
expect(item).toBeNull();
});
});
});
Time Complexity
The time complexity of operation on a Stack implementation using a linked list is as below-
Operation | Complexity |
---|---|
Push | O(1) |
Pop | O(1) |
Implementation #2: Stack using Array
Stack can be implemented using just array-
- Push to push item to stack
- Pop item from the stack
Step #1: Initialize
class Stack {
constructor() {
this.stackItems = [];
}
}
class Stack<T> {
private stackItems: T[];
constructor() {
this.stackItems = [];
}
}
Step #2: Push
- Declare method “push”.
- Use the push() method of the array – Array.prototype.push(), to add an item at the end of the array.
class Stack {
//....
push(data) {
this.stackItems.push(data);
return this.stackItems.length;
}
}
class Stack<T> {
//....
push(data: T): number {
this.stackItems.push(data);
return this.stackItems.length;
}
}
Step #3: Pop
- Use the pop() method to pop items from the front- Array.prototype.pop().
- This returns the last item from an array.
class Stack {
//...
pop() {
if (this.stackItems.length === 0) {
return null; // Or return your expected empty value
}
return this.stackItems.pop();
}
}
class Stack<T> {
//...
pop(): T | null {
if (this.stackItems.length === 0) {
return null; // Or return your expected empty value
}
return this.stackItems.pop()!;
}
}
Full Source Code
Here is the full source code of the implementation-
// stack.js
// Implementation of stack using array
class Stack {
constructor() {
this.stackItems = [];
}
push(data) {
this.stackItems.push(data);
return this.stackItems.length;
}
pop() {
if (this.stackItems.length === 0) {
return null; // Or return your expected empty value
}
return this.stackItems.pop();
}
}
export default Stack;
// stack.ts
class Stack<T> {
private stackItems: T[];
constructor() {
this.stackItems = [];
}
push(data: T): number {
this.stackItems.push(data);
return this.stackItems.length;
}
pop(): T | null {
if (this.stackItems.length === 0) {
return null; // Or return your expected empty value
}
return this.stackItems.pop()!;
}
}
export default Stack;
Demo
Use the following code check/demo the implementaiton-
// demo.js
import Stack from "./stack.js";
// Create a new Stack
let bigboxStack = new Stack();
console.log("\n\n----------- Stack Push example -----------\n");
// Push items
console.log('Push - "Big" | Result: ', bigboxStack.push("Big"));
console.log('Push - "Box" | Result: ', bigboxStack.push("Box"));
console.log('Push - "Code" | Result: ', bigboxStack.push("Code"));
console.log("\n\n----------- Stack Pop example -----------\n");
// Pop items
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
// demo.ts
import Stack from "./stack";
// Create a new Stack
let bigboxStack = new Stack<string>();
console.log("\n\n----------- Stack Push example -----------\n");
// Push items
console.log('Push - "Big" | Result: ', bigboxStack.push("Big"));
console.log('Push - "Box" | Result: ', bigboxStack.push("Box"));
console.log('Push - "Code" | Result: ', bigboxStack.push("Code"));
console.log("\n\n----------- Stack Pop example -----------\n");
// Pop items
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
console.log("Pop | Result: ", bigboxStack.pop());
Output:
----------- Stack Push example -----------
Push - "Big" | Result: 1
Push - "Box" | Result: 2
Push - "Code" | Result: 3
----------- Stack Pop example -----------
Pop | Result: Code
Pop | Result: Box
Pop | Result: Big
Pop | Result: null
Tests
Here are the tests to check the implementation-
// stack.test.js
import { describe, it, beforeEach, expect } from "vitest";
import Stack from "./stack";
describe("Stack using array", () => {
describe("Push item to Stack", () => {
let stack;
beforeEach(() => {
stack = new Stack();
});
it("Should push items correctly", () => {
let length = stack.push("Big");
expect(length).toBe(1);
length = stack.push("Box");
expect(length).toBe(2);
length = stack.push("Code");
expect(length).toBe(3);
});
});
describe("Pop item from Stack", () => {
let stack;
beforeEach(() => {
stack = new Stack();
// Push some items first
stack.push("Big");
stack.push("Box");
stack.push("Code");
});
it("Should pop item correctly", () => {
let item = stack.pop();
expect(item).toBe("Code");
item = stack.pop();
expect(item).toBe("Box");
item = stack.pop();
expect(item).toBe("Big");
item = stack.pop();
expect(item).toBeNull();
});
});
});
// stack.test.ts
import { describe, it, beforeEach, expect } from "vitest";
import Stack from "./stack";
describe("Stack using array", () => {
describe("Push item to Stack", () => {
let stack: Stack<string>;
beforeEach(() => {
stack = new Stack<string>();
});
it("Should push items correctly", () => {
let length = stack.push("Big");
expect(length).toBe(1);
length = stack.push("Box");
expect(length).toBe(2);
length = stack.push("Code");
expect(length).toBe(3);
});
});
describe("Pop item from Stack", () => {
let stack: Stack<string>;
beforeEach(() => {
stack = new Stack<string>();
// Push some items first
stack.push("Big");
stack.push("Box");
stack.push("Code");
});
it("Should pop item correctly", () => {
let item = stack.pop();
expect(item).toBe("Code");
item = stack.pop();
expect(item).toBe("Box");
item = stack.pop();
expect(item).toBe("Big");
item = stack.pop();
expect(item).toBeNull();
});
});
});
Source Code
Use the following links to get the source code used in this article-
Source Code of | Programming Language | Implementation Code | Demo Code | Test Code |
---|---|---|---|---|
Stack using Linked List | JavaScript Implementation | GitHub | GitHub | GitHub |
Stack using Linked List | TypeScript Implementation | GitHub | GitHub | GitHub |
Stack using Array | JavaScript Implementation | GitHub | GitHub | GitHub |
Stack using Array | TypeScript Implementation | GitHub | GitHub | GitHub |
Related Data Structures
Command | Details |
---|---|
Singly Linked List | Singly Linked List Detail |
Queue | Queue Details |
Other Code Implementations
Use the following links to check the Stack implementation in other programming languages-