The stack

define

A stack is a special type of linear table that restricts inserts and deletions to one end of the table (usually the bottom). (Also known as LIFO linear list, or LIFO structure).

A stack is a linear table that is wiped and deleted only at the end of the table. The end of the table is called the top of the stack To (an end) p; The header is called the Base (A1 end) of the stack.

The operation of inserting an element to the top of the stack (bottom of the table) is called pushing. The operation of removing the last element from the top (bottom) of the stack is called pop.

Storage structure

As a linear table, stacks can be stored in either sequential or linked stacks. But sequential stacks are more common. The difference between a stack and a regular linear table is that the algorithm is different because the algorithm is that you can only perform operations at the top of the stack, last in, first out. Our first task is to write the push and push functions.

The classic application of stack

Hexadecimal conversion

N is one base we input (let’s say 10), we convert it to another base (8), we divide it by 8, we keep the remainder on the stack, we keep the result in N and divide it by 8 until N / 8 == 0, and then we take it out of the stack. Because the result is from low to high record, first all the results into the stack and then all out of the stack, just use the rules of the stack, advanced after the characteristics

Parentheses matching

When writing code, you often use two types of parentheses: the parentheses “()” and the curly braces “{}”. No matter what kind of parentheses are used, one of the most important factors in program compilation is whether or not the parentheses used match. You can use the stack to determine if the parentheses match. During input, an open parenthesis is detected and pushed, and the close parenthesis is compared with the open parenthesis. If (ch == ‘}’) then you can change ch to ‘{‘ or ‘(‘ and compare it with the stack element. If a match is entered, the next comparison is performed. If not, the next comparison is performed. Otherwise, there is no need to compare again. ”

• When one of the closing parentheses is encountered, the stack is empty, indicating that the closing parentheses are currently more than the opening parentheses
• The type of parentheses popped from the stack is different from the type of parentheses currently checked, indicating that the parentheses are crossed and invalid
• The arithmetic expression is entered, but there is no matching open parenthesis in the stack, indicating that the open parenthesis has more parentheses

Expression evaluation

The operands here are postfix expressions (all operators appear after the operands) and include:

• Operands: constants, variables
• Operators: arithmetic operators, relational operators and logical operators
• Delimiter: parenthesis and expression terminator (expression terminator ‘#’, and imaginary expression start ‘#’)

To implement expression evaluation, you need two stacks. One operator stack is OPTR, which is used to store operators. The other is the operand stack OPND, which is used to store operands and results. The process of evaluation is to scan each character of the expression from left to right. When an operand is scanned, OPND is pushed. When yes is detected, if this operator has a higher priority than the operator at the top of the OPTR stack, OPTR is pushed and the processing continues backwards. If the operator has a lower priority than the OPTR top-stack operator, two operands are ejected from the OPND stack, the top-stack operator is ejected from the stack OPTR for the operation, and the result of the operation is pushed into the OPND. Continue processing until the terminator is encountered.

You can also use 嫞 stack to convert normally used expressions into postfix expressions.

The realization of the stack

Type definitions for stack abstract data types:

InitStack(&S);// Construct an empty stack
DestroyStack(&S);// Initial condition: stack S already exists Result: stack S destroyed
StackEmpty(S);// Initial condition: stack b exists Result: Return true if stack is empty otherwise false
StackLength(S);Operation result: Return the number of elements of S, i.e. the stack length
GetTop(S,&e);// Stack S exists and is not empty result: return the top element of stack S with e
ClearStack(&S);// Initial condition: stack S already exists
Push(&S,e);// Initial condition: stack S already exists result: insert element e as the new top element of the stack
Pop(&S,e);Delete the top element of stack S, an, and return its value with e
Copy the code

The stack is also divided into sequential stack and chain stack. The sequential stack has the same sequential storage structure as the general linear table [a group of continuous storage units are used to store the data elements from the bottom of the stack to the top of the stack, generally the bottom of the stack is at the lower address], with top pointer, indicating the position of the top element in the sequential stack (for easy operation, In general, the top pointer indicates the subscript address above the true top element of the stack, and the base pointer indicates the position of the bottom element in the sequential stack.

Sequential stack implementation

Structure:

typedef struct{
    StackElemType *base;// Bottom of stack pointer
    StackElemType *top;// Top of stack pointer
    int stacksize;// Maximum stack size
}SqStack;

Copy the code

Sequence stack initialization:

Status InitStack(SqStack &S){// Construct an empty stack
    //S.base = new StackElemType[MAXSIZE]; //c++
    S.base = (StackElemType*) malloc(sizeof(StackElemType) * MAXSIZE);// refers to the first element, the bottom of the stack
    if(! S.base) exit(0);// Storage allocation failed
    S.top = S.base;// The bottom pointer equals the top pointer
    S.stacksize = MAXSIZE;
    return true;
}
Copy the code

Check whether the stack is empty

// Initial condition: stack b exists Result: Return true if stack is empty otherwise false
bool StackEmpty(SqStack S){
    if(S.top == S.base)
        return true;
    else
        return false;
}
Copy the code

Get the number of stack elements (length) :

Operation result: Return the number of elements of S, i.e. the stack length
int StackLength(SqStack S){
    if(! S.base)return false;
    return S.top - S.base;
}

Copy the code

Get the top element of the stack:

// Stack S exists and is not empty result: return the top element of stack S with e
Status GetTop(SqStack S,StackElemType &e){
    if (S.base)// Whether the stack exists
        return false;
    if (StackEmpty(S))
        return false;// Whether the stack is empty
    //e = S.base[S.top - S.base];
    e = *(S.top - 1);
    return true;
}
Copy the code

Into the stack:

// Initial condition: stack S already exists result: insert element e as the new top element of the stack
/* * 2. Element e is pushed onto the stack * 3. Top pointer +1 */
Status Push(SqStack &S,StackElemType e){
    if(S.top - S.base == S.stacksize)// Stack full, the space in the middle of the stack when the head and tail Pointers are subtracted
        return false;
    // Memory can also be increased
    *S.top = e;
    S.top++;
    //*S.top++ = e;
    return true;
}
Copy the code

The stack:

Delete the top element of stack S, an, and return its value with e
/* * 1. Check whether the stack is empty, if it is empty, error (overflow * 2. Top pointer -1 */
Status Pop(SqStack &S,StackElemType e){
    if(StackEmpty(S))//if(S.top == S.base)
        return false;// Whether the stack is empty
    S.top--;
    e = *S.top;
    //e = *--S.top;
}
Copy the code

Through:

void Travel(SqStack S){
    StackElemType *temp;// Top of stack pointer
    temp = S.base;
    while(temp ! = S.top) cout << *temp++ <<"";
    cout << endl;
}
Copy the code

The realization of chain stack

A stack is a limited single linked list that operates only at the top of the list. So the structure is the same as the single-linked list. The structure of a stack is the same as that of a single linked list:

/ / structure
typedef  struct StackNode{
    StackElemType data;/ / data domain
    struct StackNode *next;
}StackNodeta,*LinkStack;
Copy the code

The head pointer of the linked list is the top of the stack, and the top of the stack does not need the head node and will not be full. An empty stack is equivalent to the head pointer pointing to empty. Initialization:

bool InitStack(LinkStack &S){
    S = NULL;
    return true;
}
Copy the code

Sentenced to empty:

Status StackEmpty(LinkStack S){
    if(S == NULL)
        return true;
    else
        return false;
}

Copy the code

Into the stack:

/ stack StatusPUSH(LinkStack &S,StackElemType e){
    LinkStack p = (LinkStack) malloc(sizeof(StackNode);
    //LinkStack p = new StackNode; // generate a new node p
    p->data = e;// Set the data field of the new node to e
    p->next = S;// Insert the new node at the top of the stack
    S = p;// Change the top of the stack pointer
    return true;
}
Copy the code

The stack:

/ / out of the stack
Status Pop(LinkStack &S,StackElemType &e){
    if (S == NULL)
        return false;
    e = S->data;// The element to be deleted exists in e
    LinkStack p = S;
    S = S->next;
    free(p);
    //delete p;
    return true;
}
Copy the code

Fetch the top element of the stack:

// fetch the top element of the stack
StackElemType Gettop(LinkStack S){
    if(S ! = NULL)return S->data;
}
Copy the code

Through:

void Travel(LinkStack &S){
    LinkStack p = S;
    while(p) {
        cout << p->data << "";
        p = p->next;
    }
    cout << endl;
}
Copy the code

This is the basic knowledge of the stack.