Shulou(Shulou.com)06/03 Report--

1. Definition and implementation of stack

Definition of stack

  stack is a special linear table, which can only operate on one end of the linear table.

Top of the    stack (Top): allows one end of the operation

Bottom of    stack (Bottom): one end where operations are not allowed

Nature of the stack: last-in, first-out (LIFO)

Some common operations of stack

  create Stack

  destroy Stack

  empties the stack

  stack

  out of stack

  gets the top elements of the stack

  gets the size of the stack

Storage implementation of stack

Sequential storage implementation

Chained storage implementation

Summary

  stack is a special linear table.

The   stack only allows one end of the online table to operate.

There are usually two ways to implement   stack

   sequential structure implementation, 01_SeqStatic folder in the attachment

   chain structure implementation, attached to the 02_ListStatic folder

2. Typical application of stack-[character matching]

Some symbols of   appear in pairs in C language, and the ability of matching compiler parentheses can be achieved by using stack.

The idea of the algorithm:

  starts scanning from the first character   ignores when encounters an ordinary character, pushes the stack when the left symbol is encountered,   pops the top symbol   from the stack when meeting the right symbol to match    success: continue to read the next character    match failed: stop immediately and error   end:    success: all characters are scanned and the stack is empty    failed: failed to match or all characters have been scanned but the stack is not empty

Algorithm framework

Summary

  can use the "last-in-first-out" feature of the stack when it needs to detect things that appear in pairs but are not adjacent to each other.

The   stack is very suitable for situations where "nearest matching" is needed.

  code implementation, attached in the 02_ListStatic folder

2. Typical application of stack 2 [implementation of small calculator]

  in mathematical calculation, human beings are used to infix expressions such as "9 + (3-1) * 5", that is, numbers are on both sides of operation symbols, but for computers, it is more suitable to deal with suffix expressions, that is, forms like "9 31-5 * +". Therefore, there must be a process from infix expressions to suffix expressions, and the computer uses suffix expressions to calculate. All of this can be achieved through the stack.

The idea of converting infix expression to suffix expression

  traverses numbers and symbols in infix expressions    for numbers: direct output    for symbols:    left parentheses: stack    symbols: priority comparison with stack top symbols     stack top symbols low priority: stack     stack top symbols priority is not low: the stack top symbols pop up and output, then enter the stack    right parentheses: pop up the stack top symbols and output Until the matching left parenthesis   traversal ends: all symbols in the stack are popped and output

Algorithm framework

Thoughts on the calculation of suffix expressions

  traverses numbers and symbols in suffix expressions    for numbers:    for symbols:     pops right operands from stack     pops left operands     performs operations according to symbols     pushes the results into the stack   traversal ends: the only number in the stack is the result of the calculation

Algorithm framework

Summary

  infix expression is a habitual expression.

  suffix expression is a favorite expression for computers.

  can easily transform infix form into suffix form through stack.

The evaluation process of   infix expression is similar to the process of compiling and running a program.

  code implementation, attached in the 02_ListStatic folder

Implementation of the algorithm: attachment

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.