Data Structure Study Notes <2> Stack

1. Abstract Data Type Description of Stack#

Type name: Stack
Data object set: a finite linear table with 0 or more elements
Operation set: a stack S with a length of MaxSize, stack element item with ElementType

1. Create an empty stack with a maximum length of MaxSize;
int IsFull(Stack S, int MaxSize);
3. Push the element item onto the stack;
4. Determine if stack S is empty;
5. Delete and return the top element of the stack.

2. Sequential Storage Implementation of Stack#

1. Definition#

The sequential storage structure of the stack usually consists of a one-dimensional array and a variable that records the position of the top element of the stack.

#define MaxSize <maximum number of stored data elements>
typedef struct SNode *Stack; // The structure pointer of SNode can be defined as Stack
struct SNode {
    ElementType Data[MaxSize]; // One-dimensional array
    int Top; // Record the top element of the stack
};

Stack PtrS defines a structure pointer PtrS pointing to SNode

2. Operations#

(1) Push operation#

Increase the value of Top by one and store the element item at the top of the stack.

void Push(Stack PtrS, ElementType item) {
    if (PtrS->Top == MaxSize-1) { // The stack is full
        printf("Stack is full");
        return;
    } else { // The stack is not full, perform the push operation
        PtrS->Data[++(PtrS->Top)] = item; // Increase the value of Top first, and then store it
        return;
    }
}

(2) Pop operation#

Pop out the element and decrease the value of Top.

ElementType Pop(Stack PtrS) {
    if(PtrS->Top == -1) { // The stack is empty
        printf("Stack is empty");
        return ERROR; // ERROR is a special value of ElementType, indicating an error.
    } else 
        return (PtrS->Data[(PtrS->Top)--]) // Return the top element of the stack first, and then decrease Top by one
}

3. Linked Storage Implementation of Stack#

1. Definition#

The linked storage structure of the stack is actually a singly linked list, called linked stack, and the insertion and deletion operations can only be performed at the top of the linked stack. The top pointer Top should be at the head of the linked list!

typedef struct SNode *Stack;
struct SNode {
    ElementType Data; // Current data
    struct SNode* Next; // Pointer to the next Snode
};

2. Operations#

(1) Stack initialization (CreateStack)#

Build a head node of the stack and return the pointer.

Stack CreateStack() {
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

(2) Determine if the stack is empty (IsEmpty)#

Determine if stack S is empty. If it is empty, the function returns 1; otherwise, it returns 0.

int IsEmpty(Stack S) {
    return (S->Next == NULL); // If there is no node behind, it is empty
}

(3) Push element item onto the stack (Push)#

First create a structure pointer TmpCell for a new node, allocate space, then assign the data as item, and assign the Next pointer as the original S's Next pointer. Then assign S's Next pointer to TmpCell.

void Push(ElementType item, Stack S) {
    Stack TmpCell;
    TmpCell = (Stack) malloc(sizeof(struct SNode));
    TmpCell->Data = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

(4) Delete and return the top element of stack S (Pop)#

First temporarily store the current node (S), assign FirstCell as S's Next pointer, then assign S's Next pointer as the address of the next node, so that S's Next pointer directly points to the second node. Then take out and release the data in FirstCell and return the data.

ElementType Pop(Stack S) {
    Stack FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)) { // If it is empty
        printf("Stack is empty");
        return NULL;
    } else {
        FirstCell = S->Next; // First store the pointer to the next node
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Data;
        free(FirstCell);
        return TopElem;
    }
}

4. Stack Application (Expression Evaluation)#

How to convert infix expressions to postfix expressions?
Read each object of the infix expression from beginning to end and handle different objects according to different situations

1. Operand: Output directly.#

2. Left parenthesis: Push onto the stack.#

3. Right parenthesis: Pop and output the top operator of the stack until a left parenthesis is encountered (pop, not output).#

4. Operator: If the priority is greater than the top operator of the stack, push it onto the stack; if the priority is less than or equal to the top operator of the stack, pop the top operator of the stack and output it, then compare the new top operator of the stack until the priority of the operator is greater than the top operator of the stack, and then push the operator onto the stack.#

5. If all objects are processed, output the remaining operators in the stack.#

Other applications of stacks: function calls and recursion implementation, depth-first search, backtracking algorithms, etc...