Data Structure The Stack

Stack is a linear data structure which follows a particular order in which the operations are performed. I will try to explain Stack with these objectives:

  • What is the Stack?
  • What is the Definition?
  • What are the use cases for a stack in the real world?
  • How to Implement operations on a stack data structure?

Stack is data collection of data structure. It’s a data collection which relies on principles. I know you are starting to think about the meaning of “ ” The means the last element added to stack will be the first element removed for a List. Basically the terminology is ast n ut. The last thing to be added in will be the first thing to be removed. It is very important to remember this logic to understand stack well. There are many ways to implement Stack. I will implement the stack in an Array and Singly Linked List.

Let’s visualize a stack.

As we see our stack on diagram it will give us some idea how to remove items from a Linked List. According to diagram the number () is the last thing added on the Linked List. Based on Stack logic number() will be the first thing in the Linked List. If we keep removing items from the stack the second item will be number() then number() and on the end number() which is the first item in the Linked List will be removed.

We can use stack for managing function invocations as follows.

Removing items from List with a Stack on console.

As you see we are removing from the top on stack how our debugger animation show us on our console above.

We are also using stacks in the real world. Imagine when we take a picture then we are trying to do some edit for fixing the picture adjusting the light etc. If we edited wrong action and we want to take a picture with undo and revert it original. Whatever we are edited in picture or undo we are using stacks for those actions to be use in picture. We are adding(edit) something on the picture then we are removing(undo) something from the picture. We can say this is the best example of how to use a stack in the real world.

I mentioned at the beginning of the article that there are many ways to implement stack. But the easiest way to implement stack to use array. Some programming languages have their own stack data type but JavaScript does not have its own stack data type. But we can still build a stack in an array or Linked list. The most important part we have to implement on Stack with the Logic as the last item added will be the first item removed.

Implementation of Stack In Array

As you see it’s very easy to implement a stack in an array. Based on the example above. We created a Stack with an array . As you know The method adds new items to the end of an array. According to Stack logic we have to remove the last item from the array. In our example “Google” is the last item in the array. If I want to keep removing the sequence of the removed items should “Google”, ‘’ FaceBook”, ‘’Amazon ‘’. We also have a method for array to make the stack easier for us. As you know The method removes the last element from an array. If you implement it on your console you should see its works perfectly like in example. Actually When we use stack in arrays we don’t need indices or index numbers. We just need the last item added should be the first item to be removed. Array gives us more operations than what we need for to use a Stack. It is easy and fast to implement stack in arrays. But I will also implement stack on Linked List from scratch to make the logic clear.

We talked about whether we don’t need any indices or indexes when we need to create a stack. The only thing we need is the logic of the stack. Last Item added should be the first item to be removed. I will try to implement a stack in a Singly linked list to show you how do we implement Stack from scratch?

First of all we need two classes defined called Stack and Node to store data.

class Stack {   
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
}
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}

If you remember When we created Linked List we need two pointers which are called and . We also initialized the of the list. But When we created Stack instead of and we changed our pointer as

Also for the Node Class we have a for each node and the pointer in the stack

  • The function should accept value
  • Create a new node with that value
  • If there are no nodes in the stack, set the first and last property to be newly created node;
  • If there is at least one node, create a variable that stores a current first property on the stack;
  • Reset the first property on the node ti be previously created variable
  • Increment the size of the stack by 1

  • If there are no nodes in the stack, return null;
  • Create a temporary variable to store the first property on the stack
  • If there is only 1 node, set the first and last property to be null
  • If there is more Ethan one node, set the first property to be the next property on the current first
  • Decrement the size by 1
  • Return the value of the node removed;
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
class Stack {
constructor() {
this.first = null;
this.last = null;
this.size = 0;
}
push(val){
var newNode = new Node(val);
if(!this.first){
this.first = newNode;
this.last = newNode;
} else {
var temp = this.first;
this.first = newNode;
this.first.next = temp;
}
return ++this.size;
}
pop() {
if(!this.first) return null;
var temp = this.first;
if(this.first === this.last){
this.last = null;
}
this.first = this.first.next
this.size--;
return temp.value

}
}

I just want to talk about some important point in this code. As you know and has constant time. But for Singly Linked List is not a constant time. Because the is to iterate all items in the list from beginning and just stop one node before the end. If we want to make it constant time we should use shift and unshift but I just the name of and as and but they functionally are working ast(adding item the beginning) and (removing from the beginning). The function is working much faster and have a constant time like this.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Soner Mezgitci

Software Engineer | Ruby on Rails | JavaScript | HTML5 | CSS | PostgreSQL | React | Redux