Article directory
- Overview of stack chain(Illustration)
- Basic operations of chain stack
-
- 1. Initialization
- 2. Push to the stack
- 3. Pop from the stack
- 4. Get the top of the stack
- 9. Complete code
- Summary
The following is the text of this article,The following case Available for reference.
Stack chain overview(Illustration)
The stack can be stored sequentially,or chained,called sequential stack and chain respectively Stack.
The sequential stack allocates a continuous space,It requires two pointers,base points to the bottom of the stack,top points to the top of the stack.
The address of each node in the chain stack is discontinuous, only one stack top pointer is needed.
From the figure, you can It can be seen that each node of the chain stack contains two fields:data domain and pointer domain font>.
Basic operations of the chain stack
The chain stack can be regarded as a singly linked list without a head node,But it can only be inserted at the head Operations such as , deletion, and value retrieval cannot be performed in the middle or at the end. Therefore, the nodes of the chain stack can be defined in the singly linked list method.
First define a structure. xff08;The inner class), contains a data field and a pointer field.
c++The code is as follows( ;Example):
typedef struct SNode{int data;//Data fieldSNode *next;//Pointer field
} *LinkStack;
Java code is as follows(Example):
public class SNode{int data;SNode next;
}
1. Initialization
Initializing an empty link stack does not require a head node – so you only need to make the top pointer of the stack empty.
c++The code is as follows(Example):
void Init(LinkStack &S){S = NULL;
}
The java code is as follows(Example):
F(){//Initialized directly with the constructor, Tired,Destroy its = null;
}
2. Push into the stack
Pushing is to push the new element node onto the top of the stack. Because the first node in the chain stack is the top of the stack, insert the new element in front of the first node, and then modify the top pointer of the stack to point to the new node.
c++The code is as follows(Example):
void Push(LinkStack &S,int e){LinkStack p = new SNode;p->data = e;p->next = S;//The next address of the new element is the top of the old stackS = p;//Move the top of the stack
}
The java code is as follows( Example):
public void push(int e){SNode p = new SNode();p.data = e;p.next = s;s = p;
}
3 .Pop from the stack
Pop from the stack is to delete the top element of the stack , let the top pointer point to the next node, and then release the node space(c++ ;).
c++The code is as follows(Example):
bool Pop(LinkStack &S,int &e){if (S == NULL ){//Stack is emptyreturn false; }LinkStack p = S;// Temporary nodeS = p->next ;//Move the top of the stack downe = p->data;//Record elements that are popped out of the stackdelete p;//Release spacereturn true;
}
The java code is as follows(Example):
public int pop (){if(s == null){return -1;} SNode p = s;s = s.next;return p.data;
}
4. Get the top of the stack
Getting the top of the stack is different from popping the stack.
Getting the top element of the stack just makes a copy of the top element of the stack – the pointer on the top of the stack has not moved – and the number of elements in the stack has not changed.
c++The code is as follows(Example):
int GetTop(LinkStack S){if(S == NULL){return -1;}return S->data;
}
java code is as follows(example):
public int getTop(){if(s == null){return -1; }return s.data;
}
9. Complete code
c++The code is as follows(Example):
#include
using namespace std ;typedef struct SNode{int data;SNode *next;
}*LinkStack;void Init(LinkStack &S){S = NULL;
}void Push (LinkStack &S,int e){LinkStack p = new SNode;p- >data = e;p-> next = S;S = ; p;
}bool Pop(LinkStack &S,int &e){if(S == NULL){return SNode next;}F(){ s = null; }public void push(int e){SNode p = new SNode( );p.data = e;p.next = s;s = p;}public int pop (){if(s == null){return -1;}SNode p = s;s = s.next ;return p.data;}public int getTop(){if(s == null){return -1;}return s.data;}public static void main(String[] args) {F f = new F();System.out.println("chain Stack initialization successful!");f .push(5);f.push (4);f.push(3);f.push(2 span>);f.push(1);System.out.println("Created successfully ");System.out.println("Elements are popped off the stack in sequence");while(f.s!=null){System.out.print(f.getTop()+ " ");f.pop() ;}System.out.println ();}
}
Summary
- The basic operations of the sequential stack and the chain stack only require constant time,so they are almost the same in terms of time efficiency.
- In terms of space efficiency, the sequential stack needs to allocate a fixed length of space in advance, which may cause space waste or overflow.
- The chain stack only allocates one at a time. Node ‘doesn’t overflow unless there is no memory’ but each node requires a pointer field which adds structural overhead.
Therefore ,If the number of elements changes greatly,You can use chain stack;On the contrary,You can use sequential stack.
In practical applications, the sequential stack is more widely used than the chain stack.
Next Issue Preview: Circular Queue
=”token punctuation”>(3);f.push(2);f.push(1);System.out.println(“Created successfully”);System.out.println (“Elements are popped off the stack in sequence”);while(f. s!=null){System.out.print(f.getTop()+” “) ;f.pop();}System.out.println(); }
}
Summary
- The basic operations of the sequential stack and the chain stack only require constant time,So they are indistinguishable in terms of time efficiency.
- In terms of space efficiency, the sequential stack needs to allocate a fixed length of space in advance, which may cause space waste or overflow.
- The chain stack only allocates one at a time. Node ‘doesn’t overflow unless there is no memory’ but each node requires a pointer field which adds structural overhead.
Therefore ,If the number of elements changes greatly,You can use chain stack;On the contrary,You can use sequential stack.
In practical applications, the sequential stack is more widely used than the chain stack.
Next Issue Preview: Circular Queue