1, stack
1.1. What is a stack
The structure of the stack is similar to that of the cartridge clip of a gun. The first bullet placed in the cartridge clip is the last one to be hit, while the last bullet placed in the cartridge clip is the first one to be hit, which is called the data structure of "first-in-last-out".
In reality, the application of stack is very widespread and common. For example, when using browser to surf the Internet, no matter what browser has a "back" button, it can load the browsed web pages in reverse order after clicking. For example, in the editing software of documents or images such as office, photoshop, there are undo operations, which are also implemented by using stack.
The definition of stack: stack is a linear structure that restricts insertion and deletion only at the end of a table.
We usually call one end that can be inserted and deleted as the top of the stack, just as one end of the cartridge can be placed on the top of the cartridge, the other end is called the bottom of the stack, and the stack without any data elements is called the empty stack.
First, it is a linear table, that is to say, the stack elements have a linear relationship, that is, the precursor-successor relationship. It's just that the stack is a special linear table. The special feature of the stack is that it restricts the insertion and deletion of the linear table, which is always carried out only at the top of the stack. This also makes: the bottom of the stack is fixed, the most advanced stack can only be at the bottom of the stack.
The insertion operation of stack is called stacking, also called stacking and stacking.
Deleting a stack is called making a stack, or a pop stack.
Does this element of the most advanced stack have to end up on the stack?
The answer is not necessarily, the stack only restricts the insertion and deletion of linear tables, and does not restrict the time of elements entering and leaving. That is to say, when all elements do not enter the stack completely, the elements of the advanced stack can also go out of the stack first, as long as the top element of the stack is guaranteed to go out of the stack. It's like we have five bullets to shoot. First we put three bullets, then two bullets, then one bullet, then two bullets, and then one bullet. Finally we shoot the bullet out of this lesson. At this time, the bullet in the stack is finally shot out.
1.2. Basic Functions of Stack
InitStack: Initialize the operation and create an empty stack.
Destroy Stack: If the stack exists, destroy the stack.
ClearStack: Clear stack elements.
StackEmpty: Determine if the stack is empty.
GetTop: If the stack exists and is not empty, return the top element of the stack.
Push: Place the new element on the top of the stack.
Pop: Bullet stack, return the top element of the stack and delete the top element of the stack.
StackLength: Number of elements returned to the stack.
2. Implementation of stack array structure
All operations of the stack depend on the top pointer of the stack. The function of the stack is more to operate the top pointer of the stack.
2.1. Stack-in operation
int Push(Stack *s, DataType element)
{
if (s->top >= MAXSIZE-1) return 0; //If the stack is full, an error is returned
s->top++; //Stack top pointer moves up to empty space
s->data[s->top] = element; //Assign new elements to the top of the stack
return 1;
}2.2. Out-of-stack operation
DataType Pop(Stack *s)
{
if (s->top <= -1) return 0; //If the stack is empty, an error is returned
DataType element = 0; //Initialize a return value
element = s->data[s->top]; //Assign the top element of the stack to the return value
s->top--; //The top pointer of the stack moves down
return element;
}Neither of the two most important functions involves any loops, so the time complexity is O(1).
The implementation of stack array structure is still very simple, because it only quasi-stack top-in and out elements, so there is no need to move a large number of elements when inserting and deleting linear tables. However, the stack's array structure still has a big drawback, that is, the storage space of the array must be determined beforehand. In case it is not enough, it needs programming to expand the capacity of the array, which is very troublesome.
3. Implementation of Link List Structure of Stack
The chain structure of the stack is called chain stack. The stack only operates with the top of the stack. The single list has the head pointer and the top pointer is also necessary. So they can be combined into one: the head pointer of the head node is the top pointer of the stack, and the data of the head node is used to record the number of elements of the stack.
For chain stack, there is no full stack, so there is no need to consider.
3.1. Stack-in operation
int Push(LinkStackTop *s, DataType element)
{
LinkStackNode *node = new LinkStackNode;
node->data = element; //New elements are assigned to new nodes
node->next = s->top; //The successor node of the new node is the current top node of the stack
s->top = node; //The new node becomes the top node of the stack
s->length++; //Number of stack elements plus one
return 1;
} 3.2. Out-of-stack operation
DataType Pop(LinkStackTop *s)
{
if (StackEmpty(s) == 0) return 0;//If the stack is empty, an error is returned
DataType element = 0; //Initialize a return value
LinkStackNode *node = s->top; //Get the top node of the stack
element = node->data; //Assign the top element of the stack to the return value
s->top = node->next; //Delete the top node of the stack
s->length--; //Reduce the number of stack elements by one
free(node);
return element;
}The time complexity of the two most important functions in the linked list structure is O(1), but emptying the stack is a little troublesome.
4. Comparing stacks of two structures
The linked list structure of the stack is slightly more complex than the array structure of the stack, but the time complexity is basically the same. In contrast, the advantages of the list structure of stack are that it is not full, unrestricted and flexible. Therefore, the list structure of stack is more recommended.
Appendix 1: Array structure of stack realizes all basic functions
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXSIZE=10;
typedef int DataType; //Data element type of stack
typedef struct {
DataType data[MAXSIZE]; //Stack array
int top; //top of stack
}Stack;
Stack* InitStack()
{
Stack *s = new Stack;
s->top = -1;
return s;
}
int StackEmpty(Stack *s)
{
if (s->top <= -1) return 0;
else return 1;
}
int Push(Stack *s, DataType element)
{
if (s->top >= MAXSIZE-1) return 0; //If the stack is full, an error is returned
s->top++; //Stack top pointer moves up to empty space
s->data[s->top] = element; //Assign new elements to the top of the stack
return 1;
}
DataType Pop(Stack *s)
{
if (StackEmpty(s) == 0) return 0;//If the stack is empty, an error is returned
DataType element = 0; //Initialize a return value
element = s->data[s->top]; //Assign the top element of the stack to the return value
s->top--; //The top pointer of the stack moves down
return element;
}
DataType GetTop(Stack *s)
{
if (StackEmpty(s) == 0) return 0;//If the stack is empty, an error is returned
DataType element = 0; //Initialize a return value
element = s->data[s->top]; //Assign the top element of the stack to the return value
//There is no need to delete the top element, and the top pointer does not need to be moved down.
return element;
}
void ClearStack(Stack *s)
{
s->top=-1;
}
int StackLength(Stack *s)
{
return s->top+1;
}
void DestroyStack(Stack *s)
{
free(s);
}
int main()
{
Stack *s =InitStack();
return 0;
}Appendix 2: Chain list structure of stack realizes all basic functions
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef int DataType; //Data element type of stack
typedef struct StackNode{
DataType data; //Stack data
StackNode *next; //Successor pointer
}LinkStackNode;
typedef struct {
int length; //Number of stack elements
StackNode *top; //top of stack
}LinkStackTop;
LinkStackTop* InitStack()
{
LinkStackTop *s = new LinkStackTop;
s->length = 0;
s->top = NULL;
return s;
}
int StackEmpty(LinkStackTop *s)
{
if (s->top == NULL) return 0;
else return 1;
}
int Push(LinkStackTop *s, DataType element)
{
LinkStackNode *node = new LinkStackNode;
node->data = element; //New elements are assigned to new nodes
node->next = s->top; //The successor node of the new node is the current top node of the stack
s->top = node; //The new node becomes the top node of the stack
s->length++; //Number of stack elements plus one
return 1;
}
DataType Pop(LinkStackTop *s)
{
if (StackEmpty(s) == 0) return 0;//If the stack is empty, an error is returned
DataType element = 0; //Initialize a return value
LinkStackNode *node = s->top; //Get the top node of the stack
element = node->data; //Assign the top element of the stack to the return value
s->top = node->next; //Delete the top node of the stack
s->length--; //Reduce the number of stack elements by one
free(node);
return element;
}
DataType GetTop(LinkStackTop *s)
{
if (StackEmpty(s) == 0) return 0;//If the stack is empty, an error is returned
DataType element = 0; //Initialize a return value
LinkStackNode *node = s->top; //Get the top node of the stack
element = node->data; //Assign the top element of the stack to the return value
return element;
}
void ClearStack(LinkStackTop *s)
{
while (s->top != NULL)
{
LinkStackNode *node = new LinkStackNode;
node = s->top;
s->top=node->next;
free(node);
}
s->top = NULL;
s->length = 0;
}
int StackLength(LinkStackTop *s)
{
return s->length;
}
void DestroyStack(LinkStackTop *s)
{
if (s->top != NULL) ClearStack(s);
free(s);
}
int main()
{
LinkStackTop *s = InitStack();
return 0;
}