Stack data structure
Stack data structure

Stack data structure

Hi dear friends! Today from this post I am bringing you another interesting topic. That is about stack data structure. I hope to write some post about data structures and algorithms. This will be series of posts. This is the fist post of it. I thought to start it with stacks. Stacks are easy and very interesting data structure to learn. From this post I am hoping to discuss about most of the theories about stacks. I am presenting these things in this post as much as visually and theoretically nicely. Let’s get started.

What is a stack data structure

Stack is a data structure we find in the programming. It contains several elements at a time. The stacks can perform several operations. There is an order which we can add and remove elements in the stack. By considering that order we call stacks as LIFO as well as. LIFO stands for Last In First Out. Which means when we removing elements from a stack it firstly remove the last element which was added to the stack.

What is LIFO

As I said earlier LIFO represent Last In First Out. According to that last element will return first. We will understand this with a real world example. Assume you are storing books in a locker. You palace books one on another. So when you take out the books. You firstly take out the book which you lastly put. This method is also implemented in the stack. In other word we can’t take out a element we like from a stack suddenly. If we want we have to take out the element at the reverse order we push them in.

Since now we have a basic idea about the stacks we will move forward. We will discuss now the stacks concepts like stack applications, stacks operations and implementing a stack.

Examples for stack applications

  • Compiler design
  • Mathematical expression evaluation
  • Balanced spell checker
  • Simple calculator

What are stack operations

There are several operations in the stacks. In order to implement a stack firstly we have to learn and have a idea about those. Therefore firstly we will look at them. These operations are like methods.

Clear() – Clear the elements in the stack

isEmpty() – Check if the stack is empty or not. Whether it contains any element or not.

Push(el) – Put element into the stack. Here parenthesis are not empty. The element we push inside the stack we write it there. As an example if we want to push 5. We will write the operation as push(5).

Pop() – This operation used to take out element from a stack. Here you can see parenthesis are empty. That is because we can’t take out the element we like from a stack. We can take out the element which was lastly inserted to the stack.

topEI() – From this operation we can return the value which is the top most value in the stack.

 

Tip

Top of the stack is consider as -1 when stack is created.

Before look at the full stack implementation. We will look at how to implement stack operations and constructors. Because we use them in the stack implementation.

Stack operations implementation

Constructor

public stackArray(parameter){The array = new object[default - capacity];

TOS = -1

}

isEmpty() method

public Boolean isEmpty(){return == -1

}

isFull() method

public Boolean isFull(){Return tos == stacksize – 1;

}

push() method

public void push(object x){If(isfull()){

Throw new stackexception(“stack is full”)

theArray[++tos] = x;

}

}

pop() method

public return type pop(){If(isEmpty()){

Throw new underflow(“stackpop”);

Tos--;

}

}

Stack implementation code

Let’s now look at the java code for stack implementation.

Class StackX{private int maxSize;

private double[] stackArray;

private int top;

public Stackx(int s){

maxSize = s;

stackArray = new double[maxSize];

top = -1;

}

public void push(double j){

stackArray[++top] = j;

}

public double pop(){

Return stackArray[--top];

}

public double peek(j){

Return stackArray[top];

}

public Boolean isEmpty(){

Return(top== -1);

}

public Boolean isFull(){

Return(top==maxSize-1);

}

}

The above class we have created is the template class. It has the constructors and methods for the main class. From the above class we can’t create any objects. If you see you can notice in the above clss there is no any main method. Therefore to create the objects and see the execution in cmd we need the main class. So for that now let’s create the main class.

class StackApp{

public static void main(String args[]){

StackX thestack = new StackX(10);

Thestack.push(5);

Thestack.push(10);

Thestack.push(15);

 

While(!thstack.isEmpty()){

double value = thestack.pop();

System.out.println(value);

System.out.println(“ ”);

}

}

}

Stack code explanation

Template class

As I said earlier firstly we have to create the template class. Which is the class contains all the constructors, methods and all.  By using that we can use the methods. So firstly in the StackX class  we create the variables and array we need for the methods. Stack operations managed using array. Therefore firstly we have to create an array. When we are creating an array we have to give stack size. That size is vary from time to time there for we create a variable maxSize. We do all the operations based on the logic in top. Top means top of the stack. I told you initially when a stack is created top equals to -1.  Therefore we have to initialize that variable as well as top.

Next we have the constructor for the class.  When we are creating objects we use the constructor to create the objects. We have the default constructor classname(). But here we have to enter stack size. Therefore we have to modified the default constructor.  int s represent the parameter list. when we create the objects we can give a number now. Because constructor now accepting a integer.  The stack size needs to be the array size. Because array represent the stack. Inside the constructor we assign s value to maxsize.  Based on that maxsize we create the array. stackArray = new double[maxsize] is the code for creating an array. We are assign tos variable to -1 as well.

Then after that we are creating methods. We gave a parameter inside push method. So when calling push method we can call it with a double value.  Array_name [location] = value is the way we assign a value to a location in an array. So the value we give as the parameter will assign as the first element for the stack. ++ is the pre increment operation. To assign value firstly we need give location. you already know top is -1 when we create a stack. Now we increment it by one. The value will be 0.  stackArray[++top] = j means stackArray[0] = j. Assign value j to location 0 in the stack.  When using pop method we just remove last inserted elementTherefore we bring tos one value down.

From peek  we return the tos value of the stack. If you know about java array learning stack would be easy. Because the whole implementation of the stack is based on array. Creating an array, assign elements to array locations, calling array location these things. In isEmpty we check whether the stack is empty. We can simply do that by checking whether tos equals to -1 or not. The opposite of isEmpty is isFull we can check it from opposite logic of isEmpty. If we create an array with size 4. The locations would be 0,1,2,3. The top value starts with value -1. When top increasing and the stack is full top value would be 3. Therefore when a stack is full top = maxsize -1. That logic logic used in isFull method to check whether stack is full or not.

Main class

Stackx thestack = new StackX(); we used to create the object. When we execute that code an array with 10 location will be created.  We execute methods with the objects. So firstly we have to put object name. Then put dot and write method name. Since we can assign value to push method we can give values. In while method we are going to print the elements in the stack. System.out.println is for printing a value. Since we want to print the value firstly we pop the value. Then assign it to a variable value.  So pop vale now will assign to the variable value. While method will work until the stack is empty. 

Conclusion

So we have come to a conclusion of stack data structure post. I hope this post would help you. I brought you stack theories as much as simple and nicely. If you like this post please comment and share this. You can tell your suggestions by commenting. Find the comment box below or from our contact us page. Please visit our Queue data structure post also if you are interested. So we will meet with another interesting topic. Till then goodbye!

Audy Ranathunga

Audy Ranathunga, Author of myexamnote is our most experienced author. She has been working as a blog post writer for 4 years. She joined with myexamnote before 1 year ago and she has contribute lots of valuable posts for readers.

Leave a Reply