Data Structure Study Notes <2> Stacks

This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

I. Abstract Data Type Description of Stacks

Type name: Stack Data object set: A finite linear list with 0 or more elements Operation set: Stack S of maximum length MaxSize belongs to Stack, stack element item belongs to ElementType

1. Create an empty stack with maximum length MaxSize; Stack CreateStack(int MaxSize); 2. Check if stack S is full int IsFull(Stack S, int MaxSize); 3. Push element item onto the stack void Push(Stack S, ElementType item); 4. Check if stack S is empty int IsEmpty(Stack S); 5. Delete and return the top element ElementType Pop(Stack S);

II. Sequential Storage Implementation of Stacks

1. Definition

The sequential storage structure of a stack typically consists of a one-dimensional array and a variable recording the position of the top element.

#define MaxSize <储存数据元素的最大个数>
typedef struct SNode *Stack;//定义SNode的结构指针可以用Stack
struct SNode {
    ElementType Data[MaxSize];//一维数组
    int Top;//记录栈顶元素
};

Stack PtrS defines a structure pointer PtrS pointing to SNode.

2. Operations

(1) Push Operation

Increment Top by one, then store element item at the top.

void Push(Stack PtrS, ElementType item) {
    if (PtrS->Top == MaxSize-1) {//堆栈全部放满了
        printf("堆栈满");
        return;
    } else {    //堆栈未满，执行入栈操作
        PtrS->Data[++(PtrS->Top)] = item;//Top值先增加，然后存储
        return;
    }
}

(2) Pop Operation

Pop the element and decrement Top by one.

ElementType Pop(Stack PtrS) {
    if(PtrS->Top == -1) {//堆栈为空
        printf("堆栈空");
        return ERROR;//ERROR是ElementType的特殊值，表示错误。
    } else
        return (PtrS->Data[(PtrS->Top)--]) //先把栈顶元素返回，再将Top减一
}

III. Linked Storage Implementation of Stacks

1. Definition

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

typedef struct SNode *Stack;
struct SNode {
    ElementType Data;//当前数据
    struct SNode* Next;//指向下一个Snode的指针
};

2. Operations

(1) Stack Initialization (CreateStack)

Construct a header node for the stack and return the pointer.

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

(2) Check if Stack is Empty (IsEmpty)

Check if stack S is empty; returns 1 if empty, 0 otherwise.

int IsEmpty(Stack S) {
    return (S->Next == NULL);//若后面没节点，则为空
}

(3) Push Element item onto Stack (Push)

First create a new node structure pointer TmpCell, allocate space, then assign Data to item and Next pointer to S’s original Next pointer. Then point 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 to S’s Next pointer, then assign S’s Next pointer to the address of the next node, i.e., make S’s Next pointer point directly to the second node. Then extract the data from FirstCell, free the dynamically allocated memory, and return the data.

ElementType Pop(Stack S) {
    Stack FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)) {//若为空
        printf("堆栈空");
        return NULL;
    } else {
        FirstCell = S->Next;//先把指向下一个结点的指针存起来
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Data;
        free(FirstCell);
        return TopElem;
    }
}

IV. Stack Application (Expression Evaluation)

How to convert an infix expression to a postfix expression? Read each object of the infix expression from beginning to end, and handle different objects according to different rules:

1. Operands: Output directly

2. Left parenthesis: Push onto the stack

3. Right parenthesis: Pop and output operators from the stack top until a left parenthesis is encountered (pop it but don’t output it)

4. Operators: When priority is greater than the stack top operator, push it onto the stack; when priority is less than or equal to the stack top operator, pop and output the stack top operator, then compare with the new stack top operator, until the operator’s priority is greater than the stack top operator’s priority, then push the operator onto the stack

5. If all objects have been processed, output all remaining operators in the stack

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