1. Basic concepts of stack
The stack is a special linear table. The data elements of the stack and the logical relationship between the data elements are exactly the same as that of the linear table. The difference lies in that the linear table allows insertion and deletion of data elements at any position, while the stack only allows insertion and deletion of data elements at the fixed end. The end of the stack that allows insertion and deletion of data elements is called the top, and the other end is called the bottom. The current position of the top of the stack is dynamic, and the variable that identifies the current position of the top of the stack is called the top pointer. The operation of inserting data elements into a stack is usually called push or push, and the operation of removing data elements is called push or unstack. According to the definition of the stack, each data element on the stack is placed before the current top data element to become the new top of the stack, each data element on the stack is the current top of the stack, so that the last data element on the stack is always the first out of the stack, so the stack is also called last in first out linear table.
The abstract data type of the stack
2.1. Data set
Stack data set can be expressed as a0, a1, a2, ⋅ ⋅ ⋅, the an – 1 a_0, a_1 and a_2,…, a_ {}, n – 1 a0, a1, a2, ⋅ ⋅ ⋅, the an – 1, each data element data type for the DateType.
2.2 operation set
- Initialize StackInitiate(S) : Initialize stack S.
- Non-empty stack StackNotEmpty(S) : Checks whether stack S is empty. The function returns 0 if the stack is empty, 1 otherwise.
- StackPush(S,x) : Inserts data element X at the top of the current stack of S.
- StackPop(S,x) : Removes the top element of the current stack of S and is returned by x, returning 1 if the stack is removed successfully and 0 otherwise.
- StackTop(S, x) : StackTop(S, x) : StackTop(S, x) : StackTop(S, x) : StackTop(S, x) : StackTop(S, x) : StackTop(S, x) : StackTop(S, x)
3. Sequential representation and implementation of the stack
3.1 Storage structure of sequential stack
According to the previous analysis, we know that the data members of the sequential stack and the sequential table are the same. The difference is that the operation on and off the sequential stack can only be performed on the current top element. The storage structure of the sequential stack is shown in the figure below, where A0, A1, A2, A3, A4A_0,a_1, A_2, A_3, A_4A0, A1, A2, A3, A4 represents the data elements of the sequential stack, and stack represents the array of data elements stored in the sequential stack. MaxStackSize indicates the maximum number of storage units in the sequential stack data stack, and top indicates the current top position of the sequential stack data stack.
The structure of sequential stack is described in C language as follows:
typedef struct {
DataType stack[MaxStackSize];
int top;
} SeqStack;
Copy the code3.2 Operation realization of sequential stack
3.2.1. Initialization
Initialization of the sequential stack is as simple as setting the top of the stack to 0.
void StackInitiate(SeqStack *S) {
S->top = 0;
}
Copy the code3.2.2 Non-null judgment
A top position of a sequential stack of 0 indicates that the stack is empty.
int StackNotEmpty(SeqStack S) {
if (S.top <= 0) {
return 0;
}
return 1;
}
Copy the code3.2.3, into the stack
Place the data element X at the top of the sequential stack S, returning 1 on success and 0 on failure.
int StackPush(SeqStack *S, DataType x) {
if (S->top >= MaxStackSize) {
printf("Stack is full and cannot insert data.");
return 0;
} else {
S->stack[S->top] = x;
S->top++;
return 1; }}Copy the code3.2.4, out of the stack
Retrievals the top data element value of the sequential stack S, retrieved by parameter X, returning 1 on success and 0 on failure.
int StackPop(SeqStack *S, DataType *x) {
if (S->top <= 0) {
printf("Stack with no data elements");
return 0;
} else {
S->top --;
*x = S->stack[S->top];
return 1; }}Copy the code3.2.5 Fetch the top element of the stack
Retrievals the top data element value of the sequential stack S, retrieved by parameter X, returning 1 on success and 0 on failure.
int StackTop(SeqStack S, DataType *x) {
if (S.top <= 0) {
printf("Stack with no data elements");
return 0;
} else {
*x = S.stack[S.top - 1];
return 1; }}Copy the code3.3. Time complexity of sequential stack
As can be seen from the above analysis, there are no loop statements in the operations of the sequential stack, so the time complexity of all operations of the sequential stack is O(1).
4, stack chain representation and implementation
4.1 storage structure of chain stack
The storage structure of a chain stack is exactly the same as that of a single linked list. Each node has one or more pointer domains in addition to the data domain. Data fields are used to hold data elements, and pointer fields are used to construct relationships between data elements. A stack has two ends, the top of the stack where elements are inserted and removed, and the bottom of the stack at the other end. For chain stack, if the end of close to the head pointer is defined as the stack, the element to insert and delete elements do not need to traverse the entire chain, the time complexity is O (1), otherwise, if you put off one end of the head pointer is defined as a stack, every time the element to insert and delete elements need to traverse the entire chain, its time complexity is O (n). It makes more sense to design the chain stack to define the end near the head pointer as the top of the stack. The following diagram shows the chain stack of the lead node.
According to the above analysis, we can use C language to define the chain stack as follows:
typedef struct SNode {
DataType data;
struct SNode *next;
} LSNode;
Copy the code4.2 Chain stack operation and implementation
4.2.1 initialization
void StackInitiate(LSNode **head) {
*head = (LSNode *) malloc(sizeof(LSNode));
(*head)->next = NULL;
}
Copy the code4.2.2 Non-null judgment
A chained stack header pointer pointing to NULL indicates that the stack is empty and returns 0, otherwise returns 1.
int StackNotEmpty(LSNode *head) {
if (head->next == NULL) {
return 0;
}
return 1;
}
Copy the codeHoldings, into the stack
Insert the data element X to the top of the chained stack head as the new top.
void StackPush(LSNode *head, DataType x) {
LSNode *p = (LSNode *) malloc(sizeof(LSNode));
p->data = x;
p->next = head->next;
head->next = p;
}
Copy the code4.2.4, out of the stack
Retrievals the top of the stack by parameter X, returning 1 on success and 0 on failure.
int StadkPop(LSNode *head, DataType *x) {
LSNode *p = head->next;
if (p == NULL) {
printf(Stack empty);
return 0;
}
head->next = p->next;
*x = p->data;
free(p);
return 1;
}
Copy the code4.2.5 Fetch the top element of the stack
Retrievals the top of the stack by parameter X, returning 1 on success and 0 on failure.
int StackTop(LSNode *head, DataType *x) {
LSNode *p = head->next;
if (p == NULL) {
printf(Stack empty);
return 0;
}
*x = p->data;
return 1;
}
Copy the code4.2.6 Cancel the Dynamic Space application
Like a single linked list, the node space of a linked stack is dynamically allocated by the program, and the system is only responsible for automatically reclaiming the statically allocated memory space in the program, so you need to add an operation to undo the dynamically allocated memory space.
void Destory(LSNode *head) {
LSNode *p, *p1;
p = head;
while(p ! =NULL) {
p1 = p;
p = p->next;
free(p1); }}Copy the code4.3 time complexity of chain stack
As can be seen from the above analysis, there are no loop statements in the operations of the chain stack, so the time complexity of all operations of the chain stack is O(1).