A stack is Last-In-First-Out (LIFO) data structure in which only the top element can be accessed. The data is added by push and removed by pop on top. The operation of push, pop and peek all have O(1) complexity. Stack can be implemented with array, linked list. This post is stack implemented using linked list.

stack as linked list

you are here

Part 1 – Stack implementation using array
Part 2 – Stack implementation using linked list

Table of Content


Push

Using linked list, first we need to define a stack node. This class has variables of data and next. Next we define the stack class. It has two class variables: top and length. top is a pointer to the top node. length is to track the length of the list. To push an element in stack is to add a node with the data at the front of the list.

Java

Javascript

Python

Doodle

stack array


Pop

First we check whether the stack is empty. If it is empty, the method should return. In this implementation, to pop an element is to move the top pointer to the next node. The popped node is still in the list until the linked list is removed from the memory.

Java

Javascript

Python


Peek

Peek is to return the value of the top node. The same as pop, we should check whether the stack is empty. If it is not empty, return the value.

Java

Javascript

Python


Print

Print is to print all elements in stack. Starting from top, a while loop is used to iterate through each node in the list.

Java

Javascript

Python

Download Java, JavaScript and Python code
Data structures and Java collections

What it means that a stack is an abstract data type?

An abstract data type (ADT) refers a class that defines the behavior of a data structure without specifying its implementation. The underlying mechanism used to implement them is not visible to outside. 
A stack is an ADT because it can be implemented using either an array or a linked list.