Stack of linear tables

The stack structure

Last come out first, first come out lastThis is the typical stack structure. A stack is an “operation-constrained” linear table that allows data to be inserted and deleted at only one end.

To implement the stack

Array implementation of the sequential stack

// Array-based sequential stack
public class ArrayStack {
  private String[] items;  / / array
  private int count;       // The number of elements in the stack
  private int n;           // Stack size

  // Initialize the array and apply for an array space of size N
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // Push operation
  public boolean push(String item) {
    // Array space is running out, return false, push failed.
    if (count == n) return false;
    // Place item at subscript count and count plus one
    items[count] = item;
    ++count;
    return true;
  }
  
  // Unstack
  public String pop(a) {
    // If the stack is empty, null is returned
    if (count == 0) return null;
    // Return an array element with subscript count-1, and the number of elements in the stack count minus one
    String tmp = items[count-1];
    --count;
    returntmp; }}Copy the code

The storage space of the array is necessary, and the space and time complexity O(1) of loading and unloading the array cannot be eliminated.

Linked list implementation of the chain stack

Supports sequential stacks for dynamic expansion

If you want to implement a stack that supports dynamic scaling, you only need to rely on an array that supports dynamic scaling at the bottom. When the stack is full, a larger array is applied and the original data is moved into the new array.The unstack time is still O(1). When pushing, when there is free space in the stack, the time complexity of the push operation is O(1). However, when there is not enough space, it is necessary to reallocate memory and move data, so the time complexity becomes O(n).

Improvement: if the current stack size is K and is full, when new data is to be pushed, it needs to apply twice the size of memory, and do K data move operation, and then push the stack again. However, we do not need to reapply memory or move data for the next K-1 push operation, so all the k-1 push operation only needs a simple-push operation.Because in most cases, the time complexity O of the push operation is O(1) and only degenerates to O(n) at certain moments, the average time of the time-consuming push operation is close to O(1) if the time of the time-consuming push operation is evenly spread over other push operations.

Stack application

Function call

int main(a) {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3.5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}
Copy the code

In an expression

One holds the stack of operands, and the other holds the stack of operators. We iterate through the expression from left to right, and when we encounter a number, we push it directly onto the operand stack; When an operator is encountered, it is compared with the top element of the operator stack.

If the priority is higher than the top element of the operator stack, the current operator is pushed onto the stack; If the priority is lower or the same as that of the top element of the operand stack, the top operator is taken from the stack, the two operands are taken from the top of the operand stack, and the calculation is performed. The result of the calculation is pushed onto the operand stack and the comparison continues.

When parentheses match

We use a stack to hold unmatched open parentheses, scanning the string from left to right. When an open parenthesis is scanned, it is pushed onto the stack; When the close parenthesis is scanned, an open parenthesis is fetched from the top of the stack. If you can match, such as “(” and”) “match,” [” and “] “match,” {” and “} “match, continues to scan the rest of the string. If an unpaired close bracket or no data in the stack is encountered during the scan, the format is invalid. After all parentheses are scanned, if the stack is empty, the string is in a valid format. Otherwise, it indicates that there is an unmatched open bracket, which is invalid.

Implement browser back, forward

We use two stacks, X and Y. We push the first page into stack X, and when the back button is clicked, we push the page out of stack X, and put the data out of stack into stack Y. When we click the forward button, we take data from stack Y in turn and put it into stack X. When there is no data in stack X, there are no pages to go back to. When there is no data in stack Y, there are no pages to browse by clicking the forward button.

• Example:

1. Open pages A, B, and C

2. C goes to page A3. Go to page B

thinking

When we talk about the application of stack, we talked about the use of function call stack to store temporary variables, why function call “stack” to store temporary variables? Can’t we use other data structures?

• This is because the order of function calls is last-come-first-out. For example, the life cycle of a local variable in a function is defined long before defined short; The same is true for a function called within a function. A function that starts execution first cannot finish execution until all other functions called within the function have finished execution. Because of these characteristics of function calls, the stack structure is preferred, based on the principle that data structures are abstractions for specific application scenarios.

source

Time.geekbang.org/column/arti…