What is a stack?

Baidu Encyclopedia, stack is defined as:

• Stack, also known as stack, is a linear table with limited operations. Limit linear tables that insert and delete operations only at the end of the table. This end is called the top of the stack, and the other end is called the bottom of the stack. Inserting new elements into a stack is also called stacking, stacking or stacking. It puts new elements on top of the stack and makes them become new top elements. Deleting elements from a stack is also called out-of-stack or out-of-stack. It deletes top elements from the stack and makes adjacent elements become new top elements.

A little bit about the key terms:

• Limited Operations: That is, you can't delete and insert the table casually. It can only be inserted and deleted according to its rules. For example, stacks can only be inserted and deleted at one end. Similarly, queues are computationally constrained and can only operate in two days.
• Linear table: Stack is also a kind of linear table. The linear table, which expresses a logical relationship of data, has been introduced in detail before. That is to say, each element in the stack is adjacent. Of course, in the specific implementation, they are also implemented in groups and linked lists. Their physical storage structure is different. But the logical structure is the same.
• Top of the stack and bottom of the stack: This description is biased toward logical content, because you know that it is easier to insert and delete arrays at the end, while single linked lists are usually easier to insert and delete arrays at the head. So arrays can be used as the top of the stack at the end, while lists can be used as the top of the stack at the head.

Application of stack:

• Stack is widely used, such as your program execution view call stack, add and subtract operation, even in search algorithm dfs, substitution recursion and so on. So stack is also a data structure that must be mastered. Many of the specifications are stacks, such as the book in the picture above.

Design and Introduction

Here we introduce the stack of array implementation and the stack of linked list implementation.

Array implementation

Structural Design

• For arrays, the process of simulating the stack is very simple, because the stack is last in first out, we can easily insert and delete at the end of the array. So we chose the end as the top of the stack. So the basic elements needed for a stack are a data array and a top(int) representing the top of the stack.
• Then the initial code and the constructed function code are:

private T data[];
private int top;
public seqStack() {
	data=(T[]) new Object[10];
	top=-1;
}
public seqStack(int maxsize)
{
	data=(T[]) new Object[maxsize];
	top=-1;
}

push insertion

One of the core operations of the stack is push: the stacking operation.

• If top < array length - 1. On the stack. top++;a[top]=value;
• If top== array length - 1; stack full.
  

pop pops up and returns to first place

• If top > = 0, the stack is not empty, it can pop up. return data[top--];
• As shown below, the original stack is 1, 2, 3, 4 (the top of the stack), performing pop operations. Top becomes 3 and returns 4.
  

Other operations

• Others, such as peek operations, do not pop up when returning to the top of the stack. So you just need to return data[top] when you satisfy the question.

Link List Implementation

With array implementations, linked lists can also be implemented. For stack operation. It can be roughly divided into two ideas:

• Insert deletions at the tail like arrays. Everyone knows that the inefficiency of linked list is in query. The efficiency of query to the tail is very low. And we use the tail pointer to solve the tail insertion efficiency. However, there is still no solution to the deletion efficiency (deletion needs to find the front node). There is also a two-way linked list. Although the previous two-way linked list has been described in detail, but this is too complex!
• So we use the single linked list with the head node to insert and delete the top of the stack in the head, which is much more refined. Insertion is inserted directly after the header node. And deletion also directly deletes the first element after the header node.

Structural Design

To make a long story short, not a short one. You can understand it directly from the code.
The nodes of the linked list:

static class node<T>
{
	T data;
	node next;
	public node() {    
	}
	public node(T value)
	{
		this.data=value;
	}
}

Basic structure:

public class lisStack <T>{
	int length;
    node<T> head;//Header node
    public lisStack() {
		head=new node<>();
		length=0;
	}
	//Other methods
}

push insertion

Consistent with single-link header insertion, if you don't know much about it, please refer to my team's linear table first.

There is a difference from stacks formed by arrays. In theory, the stack has no size limitation (not breaking through the memory system limitation). There is no need to consider whether to cross the border.

• team node stacking
• Empty list in stack head.next=team;
• Non-empty stack team.next=head.next;head.next=team;
  

pop ejection

Consistent with single list header deletion, if you don't know much about it, please read the introduction of my team's linear table first.

As with arrays, it is also necessary to determine whether they are empty.

• team node out of the stack
• Head points to the back-drive node of the team. There is no need to consider whether the linked list is a node. If it is a node, team.next=null. Executes head.next=null. Make it empty and satisfy the conditions.
  

Other operations

• Others, such as peek operation, do not pop up when returning to the top of the stack. So you just need to return head.next.data when the blank is satisfied. Length allows you to traverse the list to return the length, or you can dynamically set it (in this article) to follow the change in stack length. Other operations are directly viewed by the api.

Implementation code

Array implementation

package Team stack;

public class seqStack<T> {
	
	private T data[];
	private int top;
	public seqStack() {
		data=(T[]) new Object[10];
		top=-1;
	}
	public seqStack(int maxsize)
	{
		data=(T[]) new Object[maxsize];
		top=-1;
	}
	boolean isEmpty()
	{
		return top==-1;
	}
	int length()
	{
		return top+1;
	}
	
	boolean push(T value) throws Exception//Press into the stack
	{
		if(top+1>data.length-1)
		{
			throw new Exception("The stack is full");
		}
		else {
			data[++top]=value;
			return true;
		}
	}
	T peek() throws Exception//Return the top element of the stack without removing it
	{
		if(!isEmpty())
		{
			return data[top];
		}
		else {
			throw new Exception("The stack is empty");
		}
	}
	T pop() throws Exception
	{
		if(isEmpty())
		{
			throw new Exception("The stack is empty");
		}
		else {
		   return data[top--];
		}
	}
	public String toString()
	{
		if(top==-1)
		{
			return "";
		}
		else {
			String va="";
			for(int i=top;i>=0;i--)
			{
				va+=data[i]+"  ";
			}
			return va;
		}
	}
}

Link List Implementation

package Team stack;

public class lisStack <T>{
	static class node<T>
	{
		T data;
		node next;
		public node() {    
		}
		public node(T value)
		{
			this.data=value;
		}
	}
	int length;
    node<T> head;//Header node
    public lisStack() {
		head=new node<>();
		length=0;
	}
    boolean isEmpty()
	{
		return head.next==null;
	}
	int length()
	{
		return length;
	}
    public void push(T value) {//Near stack
       node<T> team=new node<T>(value);
       if(length==0)
       {
    	   head.next=team;
       }
       else {
		team.next=head.next;
		head.next=team;}
       length++;
    }
    public T peek() throws Exception {
        if(length==0) {throw new Exception("The list is empty");}
        else {//delete
			return (T) head.next.data;
		}
  }
    public T pop() throws Exception {//Stack out
          if(length==0) {throw new Exception("The list is empty");}
          else {//delete
        	T value=(T) head.next.data;
			head.next=head.next.next;//va.next
			length--;
			return value;
			
			
		}
    }
    public String toString(){
    	if(length==0) {return "";}
    	else {
			String va="";
		    node team=head.next;
		    while(team!=null)
		    {
		    	va+=team.data+" ";
		    	team=team.next;
		    }
		    return va;
		}
       
    }
}

test

summary

• The logic of the stack is relatively simple. It's easy to understand and relatively easy to implement. But pay attention to the boundaries of the array case.
• Queues will be introduced later, which are richer than stacks. It's a little more difficult.
• If there is a bad need for improvement, please also point out!
• Finally, if you like, you can pay attention to the public number: bigsai continues to share (reply to the data structure to get a carefully prepared document! )