Simple implementation of browser forward and backward functions

This is the fourth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

The author recently studied “The Beauty of Data Structures and Algorithms”, just take this opportunity to practice while recording their knowledge points. Just get right to it.

Let’s say we’ve visited pages A, B, C, and D. When we click the browser’s back button on page D, the browser returns to page C, and clicking the forward button takes us back to page D. This is the forward and backward functionality of the browser, which allows us to go back to the previous page and the next page at will. How does this work? So let’s click on the table and look at the stack data structure.

What is a stack

• Stacks are also linear data structures
• A stack is a linear table with limited operations, allowing data to be manipulated on only one end.
• The fact that you can only operate on one side of the stack also gives rise to the last-in, first-out nature of the stack, in which data added later is removed first. Like stacked plates in a restaurant, freshly washed dishes are placed on top of each other and taken from the top.

Two, the simple implementation of stack

There are two ways to implement a stack: a stack that uses arrays is called a sequential stack, and a stack that uses linked lists is called a chained stack. Operations that add data to a stack are called on the stack, and operations that remove data are called off the stack.

2.1 Sequential stack implementation ideas and code

Use arrays to implement the stack, because you can only operate on one end, so here we choose to operate on the back end of the array. Because the back-end adds and removes data without moving it, it’s better to keep the data in order in the array. Just push size++ and push size–. One might ask, well, the size of the array is fixed, what happens when the array is full and it’s being pushed? There are two simple handling methods, one is to use the dynamic expansion of the array, and the other is the array is full and a message indicating that the stack failed.

Ok, here is the concrete implementation code:

/ * * *@author xuls
 * @date2021/11/17 20:30 * Array implementation stack */
public class ArrayStack <T>{
	private Object[] dataArray;
	private int size;

	public ArrayStack(int capacity) {
		dataArray = new Object[capacity];
		size = 0;
	}

    / / into the stack
	public boolean push(T data){
		if (size == dataArray.length){
			// Array full, failed to push
			return false;
		}
		DataArray [size++] = data;
		dataArray[size] = data;
		size ++ ;
		return true;
	}

    / / out of the stack
	public T pop(a){
		if (isEmpty()){
			throw  new IndexOutOfBoundsException("stack is Empty");
		}
		DataArray [size--]
		Object result = dataArray[size - 1];
		size--;
		return (T) result;
	}

	public boolean isEmpty(a){
		return size == 0; }}Copy the code

2.2 Chain stack implementation ideas and codes

The stack idea of linked list implementation is also very simple, just need to insert new data into the head of the linked list, remove the head of the linked list, without considering the problem of expansion.

Here is the concrete implementation code:

/ * * *@author xuls
 * @date* List implementation stack */
public class LinkedListStack <T>{
	private Node<T> headNode;
	private int size;

	public LinkedListStack(a) {
		size = 0;
	}

    / / into the stack
	public void push(T data){
		Node<T> tNode = new Node<>(data, null);
		if(headNode ! =null){
			tNode.next = headNode;
		}
		this.headNode = tNode;
		size ++ ;
	}

    / / out of the stack
	public T pop(a){
		if (isEmpty()){
			throw new  IndexOutOfBoundsException("stack is empty");
		}
		T data = headNode.data;
		headNode = headNode.next;
		size--;
		return data;
	}

	public boolean isEmpty(a){
		return size == 0;
	}

	public void clear(a){
		headNode = null;
		size=0;
	}

	private static class Node<T>{
		private T data;
		private Node<T> next;

		public Node(T data, Node<T> next) {
			this.data = data;
			this.next = next; }}}Copy the code

Three, browser forward and backward simple implementation

Given the data structure of the stack, you’ve probably figured out how to implement a simple browser forward and backward function. Yes, we can use two stacks, one for forward and one for backward.

For example, visit pages A, B, C, and D in sequence.

When we go from page A to page B, we’re pushing back the url of page A, and when we go from page B to page C, we’re pushing back the url of page B. The same goes for page C to page D.

Ok, so if you go from page D to page C, all you have to do is push page D forward and back up and out to get the address of page C. If you go from page C to page D, the same thing happens when you push the url of page C back onto the stack, and then push it off the stack to get the url of page D.

However, if you return to page C and open a new page E, the forward operation cannot be carried out at this time, so you need to clear the data in the forward stack. This implements a simple forward and backward function.

The following is the specific code with the chain stack implementation:

/ * * *@author xuls
 * @date2021/11/17 as * /
public class CustomBrowser {
	private String currentUrl;
	private LinkedListStack<String> backStack;
	private LinkedListStack<String> forwardStack;

	public CustomBrowser(a) {
		backStack = new LinkedListStack<>();
		forwardStack = new LinkedListStack<>();
	}

	public void open(String url){
		if (this.currentUrl ! =null){
			backStack.push(this.currentUrl);
            // When opening a new page, you need to clear the contents of the forward stack
			forwardStack.clear();
		}
		this.currentUrl = url;
		System.out.println("open "+currentUrl);
	}

	public void back(a){
		if(! backStack.isEmpty()){ forwardStack.push(this.currentUrl);
			this.currentUrl = backStack.pop();
			System.out.println("back " + this.currentUrl); }}public void forward(a){
		if(! forwardStack.isEmpty()){ backStack.push(this.currentUrl);
			this.currentUrl = forwardStack.pop();
			System.out.println("forward "+ this.currentUrl); }}public String getCurrentUrl(a){
		return currentUrl;
	}

	public static void main(String[] args) {
		CustomBrowser browser = new CustomBrowser();
		browser.open("http://www.baidu1.com");
		browser.open("http://www.baidu2.com");
		browser.open("http://www.baidu3.com");
		browser.back();
		browser.back();
		browser.forward();
		browser.open("http://www.qq.com"); browser.forward(); browser.back(); browser.back(); browser.back(); browser.back(); browser.back(); browser.back(); System.out.println(browser.getCurrentUrl()); }}Copy the code

Four,

• A stack is a constrained linear data structure that can only be operated on one side, which also contributes to lifO (lifO).
• There are two types of stack, sequential stack and chain stack.
• Limitations do not mean that it is difficult to use, but rather that the stack can be used in special scenarios, such as bracket matching, expression evaluation, or maze problems in addition to browser forward and backward, which require us to be able to abstract out the characteristics of specific problems.

Portal:

How to implement singly linked list

How to dynamically expand the array

XDM, in addition to keeping warm, you should exercise more, move your hands and click “like” comment!