The stack
Before learning about data structures, the word stack was the most common name I heard of data structures (followed by linked lists), and most technical posts start with the word “tech stack” and list the various technologies used in the post.
So what is the real stack? And what problems are they trying to solve? This chapter gives me the answer.
The definition of the stack
A stack is essentially a linear table, but it has a lifO feature and is limited to insert and delete operations at the end of the table. A stack is like digging a hole in the ground, where data is dumped, first at the bottom of the stack and last at the top. Operations on data in the stack are divided into loading and unloading, and these operations only apply to the current top of the stack.
The abstract data type of the stack
Each element of the stack, the data type is the same (because the stack is essentially a linear table), and its deletion and insertion operations are the most special.
InitStack(*S); // Initialize an empty stack
DestoryStack(*S);// Destroy a stack
ClearStack(*S);// Clear a stack, restore the original empty stack
StackEmpty(S);// Return True if the stack is empty
GetTop(S,*e);If the stack is not empty, use e to return the top element of the stack
Push(*S,e);// Insert a new element e to the top of the stack
Pop(*S,*e);// Remove an element at the top of the stack and return the data to e
StackLength(S);// Return the number of elements in the stack
Copy the codeSequential storage of stacks
Linear tables have two storage concepts, one is sequential storage, one is chain storage, stack is no exception.
The stack structure for sequential storage is an array and a top tag.
typedef struct{
int data[MAXSIZE];// An array with a maximum length of MAXSIZE, which also limits how much data the stack can store
int top;
}SqStack;
Copy the codeIf top is -1, then the stack is empty. When top is MAXSIZE-1, the stack is full.
Sequential storage of stacks
The Push operation is called Push.
Status Push(SqStack *S,int e){
if(S->top == MAXSIZE- 1) {// Check if the stack is full
return ERROR;
}
S->top++; // Update the top of stack
S->data[S->top] = e;
return OK;
}
Copy the codeThe algorithm for pushing:
- Check whether the stack is full, and return an error if the stack is full.
- Before inserting data, update the top indicator to the empty space above the original top of the stack;
- The insert is completed by assigning the data to the empty space that the top of the stack indicator now points to.
It looks simple enough.
Sequentially store the unstack
The push operation is called Pop.
Status Pop(SqStack *S,int *e){
if(S->top == - 1) {// Check whether the stack is empty
return ERROR;
}
S->data[S->top] = *e;// The element to be pushed is returned to e
S->top--;
return OK;
}
Copy the codeStack out algorithm:
- First check whether the stack is empty, empty stack is unable to exit the stack, return an error;
- The data to be pushed is saved to E before deletion
- When you move the top indicator down on the stack, you’re not actually deleting it. After all, this is an array, and you just insert the new value.
The action of pushing out of the stack is interesting, except that the top indicator is moved, and the data that is pushed out of the stack is actually still in the array.
The two stacks share space
The sequential stack is a very simple and efficient stack type, but it also has a disadvantage, which is also a common problem of linear table sequential storage, that is, to determine the size of the array. A preset space that is larger than required is a waste of resources, and a small space is even worse. To solve this problem, the concept of two stacks sharing space was developed.
The two stacks share the same array space, which can greatly improve resource utilization. The structure is as follows:
typedef struct{
int data[MAXSIZE];
int top1; // The top indicator of stack 1
int top2; // Top indicator of stack 2
}SqDoubleStack;
Copy the codeThe operation of the two-stack shared structure is more complicated, mainly because there are more parameters of the stack number, which function is to tell the program which stack to operate on the shared stack.
The algorithm for pushing:
- First check whether the stack is full, that is, whether the next bit of top1 is the same as top2
- Determine which stack to push from the stack number parameter.
- Do a simple push operation.
Status Push(SqDoubleStack *S, int e, int StackNumber){
if(S->top1+1 == S->top2) return ERROR; // Check whether the stack is full
if(StackNumber == 1) {// The operation object is stack 1
S->top1++; // Update the top indicator of stack 1
S->data[top1] = e; // Insert the new element into stack 1
}
else if(StackNumber == 2) {// The operation object is stack 2
S->top2--; // Update the top indicator of stack 2
S->data[top2] = e; // Insert the new element into stack 2
}
return OK;
}
Copy the codeStack out algorithm:
- First check whether the stack is full, that is, whether the next bit of top1 is the same as top2
- Determine which stack to push from the stack number parameter.
- Do a simple push operation.
Status Push(SqDoubleStack *S, int *e, int StackNumber){
if (StackNumber == 1) {if(S->top1 == - 1) return ERROR; // Check whether stack 1 is empty
*e = data[S->top1];
S->top1--;
}
else if(StackNumber == 2) {if (S->top2 == MAXSIZE) retunr ERROR; // Check whether stack 2 is empty
*e = data[S->top2];
S->top2--;
}
return OK;
}
Copy the codeChain storage of stacks
The length of the sequential storage stack is limited at the moment of stack creation. Since stacks are essentially linear tables, there must be a corresponding chained storage structure, that is, a chain stack.
Each node has a pointer field that points to the first node below it, and the chain of nodes itself has a pointer that acts as a top indicator.
typedef struct StackNode{ // Stack node
int data;
struct StackNode *next; // A pointer to a successor
}StackNode;
typedef struct StackNode * LinkStackPtr; // A pointer to a stack node
typedef struct{ // The entire stack structure
LinkStackPtr top;// The top indicator of the stack
int count;// The current stack length
}LinkStack;
Copy the codeDifferent from sequential storage, linked stack can store any and dynamic amount of data. The most typical is that when we browse the web page, as we click the link to load more pages, the web page that records our browsing is linked stack. When we click back, we can go back to the original home page.
The loading of a stack
Because of the chain structure, pushing creates new memory space.
Stack algorithm:
- Create a node size memory space.
- Store data into the newly created node and set its successor to the current top of the stack
- Update the top of the stack so that the top indicator points to the newly created node.
- Finally, don’t forget to update the stack length
Status Push(LinkStack *S, int e){
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
s->data = e;
s->next = S->top;
S->top = s;
S->count++;
return OK;
}
Copy the codeOut of a stack
Because it is a chain structure, it involves the management of memory, and the block of memory that is pushed out of the stack should be released in time.
Stack out algorithm:
- First check if the current stack is empty and declare a temporary node pointer.
- The data to be pushed is stored in variables
- The temporary node pointer stores the address of the node to be pushed
- Update the top of stack indicator to the next node of the node to be pushed
- Free removes the node at the address stored by the temporary node pointer
- Finally, don’t forget to update the stack length
Status Pop(LinkStack *S, int *e){
LinkStackPtr p;
if (StackEmpty(*S)) return ERROR; // Check if the stack is empty
*e = S->top->data; // Store the data to be pushed
p = S->top; // Store the address at the top of the stack
S->top = S->top->next;// Update the top of stack indicator
free(p);// Release the top node of the stack
S->count--;// Update the stack length
return OK;
}
Copy the codesummary
Learn the front of the linear table, stack concept is easy to understand, behind the queue, is a hard bone, come on!