1024programmer Java [Data structure] stack (stack) stack chain (animated diagram, c++, java)

[Data structure] stack (stack) stack chain (animated diagram, c++, java)

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.
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&#xff08 ;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.

Push

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+&#43 ;).

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 &#61 ; 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

  1. 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.
  2. 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.
  3. 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

  1. The basic operations of the sequential stack and the chain stack only require constant time,So they are indistinguishable in terms of time efficiency.
  2. 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.
  3. 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

This article is from the internet and does not represent1024programmerPosition, please indicate the source when reprinting:https://www.1024programmer.com/data-structure-stack-stack-stack-chain-animated-diagram-c-java-2/

author: admin

Previous article
Next article

Leave a Reply

Your email address will not be published. Required fields are marked *

Contact Us

Contact us

181-3619-1160

Online consultation: QQ交谈

E-mail: 34331943@QQ.com

Working hours: Monday to Friday, 9:00-17:30, holidays off

Follow wechat
Scan wechat and follow us

Scan wechat and follow us

Follow Weibo
Back to top
首页
微信
电话
搜索