Queue with stacks 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.

Источник

How to Implement Stacks and Queues in Java

In one of our previous articles (which you can find here) we looked at how to implement Linked Lists in Java. This time, we’re delving into the fundamental data structures that are stacks, and queues. You’ll find these data structures highly used in Computer Science to implement functionality and logic.

So how can you implement these? As usual, we’ve got you covered with this tech tutorial. We’ll go through some of the theory behind stacks and queues, and then dive straight into Java code and see how we can implement them from scratch. Our take? Knowing how to implement data structures from scratch and performing operations with them will not only enhance your skills as an engineer but also makes you more attractive to potential employers.

What are Stacks and Queues?

Stacks are linear data structures that follow the LIFO principle, that is, last in first out. This simply means that insertion of a new node and removal of a node takes place from the end. This is referred to as the top in stack terminology. The operations are referred to as push and pop for insertion and deletion respectively.

Stacks are extremely useful data structures used very widely in computer science for recursive function calls. They are also used when control passes from one point of a program to another to store the return addresses.

Queues, on the other hand, follow the FIFO principle, which is first in first out. They represent an actual queue in real-life where people who enter first are serviced first and so on. Insertion operation is known as enqueue and deletion is known as dequeue. Queues are also extremely popular in networking as well as system design. They are widely used for controlling access to resources. A good example is an office printer. You might have used a network printer to print documents and this uses a queue internally so that multiple people can request at the same time, but will be processed sequentially.

Stack Operations – Push and Pop

First up, we have stacks. Implementing them in Java is pretty straightforward, so you’ll enjoy trying this. Firstly, create a class and name it Stack. We have three variables that determine the stack size, the elements themselves, and the top element.

We have a constructor that is used to initialise the stack with the max size value. After this, an array of that size is created and top is initialised to -1. You might be thinking about why top is initialised to -1. Remember Java uses zero-based indexing which means that the first element would be at index 0, the second one would be at index 1, and so on.

Now, let’s take a look at the insertion and deletion operations, more popularly known as pushing and popping.

We’ll start by looking into pushing. The function accepts an integer value that is to be pushed onto the stack. At this point, check if the top is pointing to maxSize – 1, which means that the stack would be full and we cannot insert. If it’s not full, we increment the top value and insert the item at that index in the array.

Popping is a much easier operation. We first check if top is equal to -1, which is the initial condition of the stack being empty. If that’s the case, we cannot pop anything out of it. If not, we print out the element that is currently at the top and decrement it. The peek function is simply a utility function that allows us to view which element is at the top currently.

Check out the driver code above to create a stack of size 3. We insert 3 elements into it after which no insertion is possible. On the last line, we pop off the top element. The below diagram is a helpful visualisation of the entire process. Once top is equal to 2 (which is maxSize – 1), we cannot insert elements further. When we call the pop function, the topmost element is deleted and the value of top is decremented by 1.

Queue Operations – Enqueue and Dequeue

The queue is very similar to the stack class that we saw earlier. Instead of top, we have front and rear. This is because, in a queue, insertion happens at the rear and deletion happens from the front. Then we have an array for the queue itself, the maximum size, and also a count of the number of items. We have four utility functions as shown below:

They are pretty self-explanatory. Peeking is used to view the current item at the rear and front. Check empty and check full is used to check whether the queue has any items or not. Now let’s get into the actual implementation of the enqueue and dequeue operations.

The enqueue function takes the element to be inserted and checks whether the queue is full, before inserting it to the rear. This is done by incrementing the rear pointer and appending it to that index. We also increment the number of items by 1.

The dequeue function, which checks if the queue is empty using the utility function that we saw earlier and if not, displays the element currently at the front and decrements it by one. Like before, we also decrement the number of items in the queue by 1.

Just like we did earlier, check out the driver code above to create a queue of size 3. We will insert 3 elements into it, after which the queue becomes full. We will then remove one element as well. The visualisation below will help you understand the process better.

Wrapping Up

That brings us to the end of this tech tutorial. We hope you learned something but more importantly had fun doing it! As you can see, when you get into it — implementing stacks and queues is really quite easy. If you’d like to do more or improve: try doing more complex operations with stacks and queues, or try using objects instead of primitive types and see if you can use them in a project to implement a particular functionality.

This is the second article in our series of data structure implementations using Java and we will soon be adding more. Like what you’ve read or want more like this? Let us know! Email us here or DM us: Twitter, LinkedIn, Facebook, we’d love to hear from you.

hackajob Staff

Источник

Implement Queue using Two Stacks – Java Code & Algorithm

How to implement a queue using two stacks. In this tutorial, I am going to discuss how to implement a first in first out (FIFO) queue using only two stacks.

In this problem, we are going to implement following methods of QueueUsingStack class:

void push(int x) – Insert an element x.
int pop() – Removes the element (In FIFO order).
int peek() – Returns the element which is present at the front of the queue.
boolean empty() – Returns true if no element is present else false.

Before solving this problem let’s first understand the difference between queue and stack data structure.

Queue is a First-In, First-Out (FIFO) data structure. The element which we enqueued first is the first element to be dequeued.

In queue, inserting an element is called as enqueue and deleting an element is called as dequeue. Insertion happens at one end called rear and deletion happens at other end called front.

Stack is a Last-In, First-Out (LIFO) data structure. The element which we pushed at last is the first element to be popped out.

Inserting an element in a stack is called as push and deleting an element is called as pop.

Implement Queue using Two Stacks – Java Code

Let’s discuss how we can impelement a queue using two stacks and write it’s java code.

The idea here is to push the element in a first stack. When the pop operation is called pop the element from second stack. If second stack is empty and first stack is not empty then pop all the elements from first stack and push them in a second stack.

It ensures that whenever we pop from the second stack, we get the element which is inserted first (FIFO order).

Источник