Stack programming in java

Data structures 101: How to use stacks and queues in Java

Mastering data structures is non-negotiable. Efficient data structures help execute effective programs. Today, many programming roles require great knowledge of data structures. They are also a fundamental part of coding interviews.

Stacks and queues are linear data structures that follow a particular order to add or remove entities. In this article, you will be introduced to stacks and queues. We will highlight their uses, functionalities, and show you how to implement these data structures in Java.

Today, we will cover:

Master data structures for coding interviews with hands-on practice

Learn data structures with practical, real-world problems from coding interviews.

Data Structures for Coding Interviews in Java

What is a Stack?

In programming, a stack is an abstract, linear data type with a predefined capacity (or boundary). It follows a particular order for adding or removing elements. Linear data structures organize their components in a straight line, so if we add or remove an element, they will grow or shrink respectively.

Let us conceptualize stacks using a stack of plates placed in a box. The first plate placed in the stack (the plate at the bottom of the stack) will be the last one to be removed, and the plate added last would be the first to be removed.

This is called the Last In First Out (LIFO) or First In Last Out (FILO) ordering.

Stacks are used in a variety of ways when we code. We use stacks to implement functions, parsers, expression evaluation, and some algorithms. Stacks are great for processing nested structures, so they are important for understanding recursion.

A simple real-world application of a stack is reversing a string letter by letter. Another good example of a data stack is the undo and redo function on a computer or text editor. Undo removes your most recent change, and redo builds upon already existing changes.

How do Stacks work?

The implementation of stacks is relatively easy. The functionality depends on the pop and push method, as you can see from the illustration above. The pop method removes or deletes elements from the stack, while the push method adds items to the stack.

When an element is inserted into a stack, it takes the top position and the variable storing this position points to the number below it. The top variable should be updated anytime an element is inserted or removed from it.

Note: What’s important to remember is that insertion and deletion happen on the same end of a Stack.

Later in this article, we will learn how to manually implementing the Stack data structure in Java.

What is a Queue?

A queue is a lot like a stack. A Queue is also a linear structure that follows a First In First Out (FIFO) order, but they differ in how elements are removed. Queues are open from both ends: one end for inserting data ( enqueue ), and the other end for removing data ( dequeue ). A stack is only open from one end.

Simplied: for a stack we remove the most recently added element, but for a queue, we remove the “oldest” element.

Источник

Stack Program in Java

In this article, we will write a Stack program in Java. We will learn about the stack class in Java, how to create a stack, different methods of a stack in Java, and how to iterate over a stack in Java. So, let’s get started.

What is Stack Data structure?

The Stack data structure is a linear data structure based on the FILO (First in Last out) or LIFO (Last in First out) principle. The word stack can be easily imagined as a pile of objects, one above the another. For instance, in a stack of books, the book kept at the top was the last element to enter the stack and if we want to empty the stack by removing the elements one by one, the book at the top of the stack will be the first element we will choose to remove from the stack as it is the most convenient one to be removed.

So, a “stack” of real-world objects in general also follows the Last in First out (LIFO) principle. A stack data structure is shown below.

So, the above image shows an empty stack.

Push Operation in Stack:

To put an element inside a stack is generally referred to as a push operation. For instance, when we push 10 in the stack, the stack will now contain 10.

So, let us push some more elements in the stack as shown below.

So, we can see that the element that is pushed last into the stack is at the top of the stack. This is the general behavior of the stack data structure.

Pop Operation in Stack:

Now, let us try to remove some elements from the stack. Removing an element from the stack is referred to as a pop operation.

So, we can see that when we pop from the stack, the topmost element of the stack gets removed. The stack after popping once is shown below.

So, 40 is now the top of the stack. If we pop once again, then 40 will be removed from the stack as shown below.

So, this is what stack data structure is and the push and pop are the 2 main operations on a stack.

Peek Operation in Stack

Let us also understand the third very main operation called the top or peek of the stack. The top or peek simply means giving the topmost element of the stack. For instance, the top/peek of the stack is shown below for different stacks.

So, at any moment, the element that is the topmost element of the stack is called the peek of the stack.

Let us now also understand the working of push, pop, and top operations in a stack.

Stack Program in Java – Working of Push, Pop, and Peek Operations

So, we have studied and understood the different operations of a Stack data structure. However, let us now understand how these operations work. Consider an empty stack shown below.

A stack data structure can be created using an array or a list when it comes to its implementation. An empty stack is a stack whose top = -1. Since the top pointer points to the topmost element of the stack and -1 is an invalid index, we can say that the stack is empty.

What happens when we push an element into the stack? This is shown below.

So, when we push an element into the stack, the top pointer first increments its value and brings it to the position where the upcoming element (i.e. upcoming top) would be inserted.Then, at that position in the array or the list, we insert the element. This is shown both diagramatically and with the help of pseudo-code in the image above.

Now, let us learn how the pop operation works. Consider the stack filled with some values as shown below.

Now, let us pop an element from this stack.

So, the image above shows what happens when we pop an element from the stack both diagrammatically and by pseudo-code. The element at which the top pointer is pointing is first removed from the underlying array or list and then the value of the top pointer is decremented.

What happens when we perform the operation peek()? Well, we simply return the element at the top i.e. we return the element to which the top pointer is pointing.

Now, just one more question left. We have seen what happens when the stack is empty. However, is a stack ever full? What happens if a stack is full?

So, if we implement a stack using an array, we know when it will be full i.e. when top = array.length as the array has a fixed size i.e. we are restricting the number of elements that can be pushed into the stack.

However, if we are using a list to implement a stack, we can’t say when it will be full. We can just say that if the memory limit exceeds, the stack will be full.

Now that we have understood all the operations of a stack, let us create our own stack class and write a stack program in Java.

Stack Program in Java – Implementing our own Stack

class MyStack < private int arr[]; private int top; private int capacity; // Creating a stack MyStack(int size) < arr = new int[size]; capacity = size; top = -1; >public void push(int x) < if (isFull()) < System.out.println("Stack OverFlow"); System.exit(1); >System.out.println("Inserting " + x); arr[++top] = x; > public int pop() < if (isEmpty()) < System.out.println("STACK EMPTY"); System.exit(1); >return arr[top--]; > public int getSize() < return top + 1; >public Boolean isEmpty() < return top == -1; >public Boolean isFull() < return top == capacity - 1; >public void printStack() < for (int i = 0; i > > public class Main < public static void main(String[] args) < MyStack stack = new MyStack(5); stack.push(1); stack.push(2); stack.push(3); System.out.print("Stack: "); stack.printStack(); stack.pop(); System.out.println("\nAfter popping out"); stack.printStack(); >>

Time and Space Complexities

Push: The time complexity of push is O(1) as we are just adding an element to the end of the array/list. The auxiliary space is also O(1) as we are using any extra space.

Pop: The time complexity of pop is also O(1) as we are just removing the last element from the array/list. The auxiliary space is also O(1) as we are not using any extra space.

Peek(): The time complexity of peek is also O(1) as we are just getting the last element from the array/list. The auxiliary space is also O(1) as we are not using any extra space.

So, we have seen how to create our own stack class in Java. However, every time we need a stack, we need not do this because Java provides us with its own Stack class that we can use. So, let’s have a look at the Stack class provided by Java.

Stack Class in Java

Stack class is a part of the Java Collections Framework. It extends the Vector class and implements List, Collection, Iterable, Serializable, and Cloneable interfaces. It is a part of java.util package. Just like we create our own stack, we have predefined methods in the Stack class to push, pop, peek an element from the stack and methods to check whether the stack is empty or not, to iterate the stack, etc. The Stack program in Java using the Java Stack class is shown below.

Stack Program in Java – Using Java’s Stack Class

import java.util.*; public class Main < public static void main(String[] args) < Stackstk = new Stack<>(); System.out.println("Pushing some elements in the stack"); //pushing an element into the stack -> push() stk.push(10); stk.push(20); stk.push(30); stk.push(40); stk.push(50); //display the stack System.out.println("Stack: " + stk); //pop() -> removes the element int x = stk.pop(); System.out.println(x); //top of the stack -> peek() System.out.println("The element at the top of the stack is: " + stk.peek()); //size of the stack -> number of elements System.out.println("Number of elements in the stack: " + stk.size()); //empty() -> return true if the stack is empty, false otherwise System.out.println("Is the stack empty: " + stk.empty()); //Iterating the stack using iterator Iterator it = stk.iterator(); while(it.hasNext()) < Object value = it.next(); System.out.println(value); >> >

Explanation: We have created an Integer stack in Java. We can create other stacks also like Character stack, String stack, etc. The push() function is used to push the element passed as a parameter inside the stack. The pop method removes the topmost element from the stack and also returns its value. The peek() method just returns the topmost value of the stack. The size() methods returns the number of elements in the stack. The empty() method returns a boolean value. It returns true if the stack is empty and false otherwise. Finally, we have created an iterator and have traversed the stack using it.

So, this is how we can write a stack program in Java using the Java’s stack class i.e. Java’s inbuilt stack. We hope that you liked the discussion and have understood the concepts taught in this article. We hope to see you again soon at PrepBytes.

Other Java Programs

Источник

Stack programming in java

Learn Latest Tutorials

Preparation

Trending Technologies

B.Tech / MCA

Javatpoint Services

JavaTpoint offers too many high quality services. Mail us on h[email protected], to get more information about given services.

• Website Designing
• Website Development
• Java Development
• PHP Development
• WordPress
• Graphic Designing
• Logo
• Digital Marketing
• On Page and Off Page SEO
• PPC
• Content Development
• Corporate Training
• Classroom and Online Training
• Data Entry

Training For College Campus

JavaTpoint offers college campus training on Core Java, Advance Java, .Net, Android, Hadoop, PHP, Web Technology and Python. Please mail your requirement at [email protected].
Duration: 1 week to 2 week

Like/Subscribe us for latest updates or newsletter

Источник