正文
链式栈实现java代码 链栈的实现和运算
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Java 栈 如何实现括号匹配
java栈实现括号匹配，主要是使用栈队列算法，如下代码：
import java.util.Scanner;
import java.util.Stack;
/**
* @author Owner
*
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();//3条测试数据数据
StackCharacter stack = null;
while(n!=0){
//从控制台读入一个测试字符串[]() [(])
String str = sc.next();
//如果该输入字符串为奇数，说明不匹配
if(str.length() % 2 == 1){
System.out.println("No");
}else{
//说明字符是偶数
stack = new StackCharacter();
//遍历第一条测试字符串[]() [(])
for(int i=0;istr.length();i++){
if(stack.isEmpty()){
//如果栈是空的
stack.push(str.charAt(i));
}else if(stack.peek() == '[' str.charAt(i) == ']' || stack.peek() == '(' str.charAt(i) == ')'){
//说明此时栈中字符不是空的,并且符合，
stack.pop();
}else{
stack.push(str.charAt(i));
}
}
if(stack.isEmpty()){
//如果栈是空的，说明括号匹配
System.out.println("Yes");
}else{
//说明栈不为空，括号不匹配
System.out.println("No");
}
}
n--;
}
}
}
相关问答
Q1: .如果栈的最大长度难以估计，则最好使用
如果栈的最大长度难以估计，最好使用链栈。
链式栈可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。
扩展资料
链栈的实现思路同顺序栈类似，顺序栈是将数顺序表（数组）的一端作为栈底，另一端为栈顶；链栈也如此，通常我们将链表的头部作为栈顶，尾部作为栈底。
链表的头部作为栈顶，意味着：在实现数据“入栈”操作时，需要将数据从链表的头部插入；在实现数据“出栈”操作时，需要删除链表头部的首元节点。因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。
Q2: 分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。
顺序存储结构
#includeiostream
typedef char ElemType;
#define MaxSize 100
using namespace std;
typedef struct
{
ElemType data[MaxSize];
int top;
}sqStack;
void InitStack(sqStack *s);//初始化栈
void ClearStack(sqStack *s);//摧毁栈
int StackLength(sqStack *s);//返回栈的长度
bool StackEmpty(sqStack *s);//判断栈是否为空
int Push(sqStack *s,ElemType e);//进栈
int Pop(sqStack *s,ElemType e);//出栈
int GetTop(sqStack *s,ElemType e);//取栈顶元素
void DispStack(sqStack *s);//显示栈中元素值
int main()
{
return 0;
}
void InitStack(sqStack *s)//初始化栈
{
s=new sqStack;
s-top=-1;
}
void ClearStack(sqStack *s)//摧毁栈
{
delete s;
}
int StackLength(sqStack *s)//返回栈的长度
{
return (s-top+1);
}
bool StackEmpty(sqStack *s)//判断栈是否为空
{
return (s-top==-1);
}
int Push(sqStack *s,ElemType e)//进栈
{
if(s-top==MaxSize-1)
return 0;
s-top++;
s-data[s-top]=e;
return 1;
}
int Pop(sqStack *s,ElemType e)//出栈
{
if(s-top==-1)
return 0;
e=s-data[s-top];
s-top--;
return 1;
}
int GetTop(sqStack *s,ElemType e)//取栈顶元素
{
if(s-top==-1)
return 0;
e=s-data[s-top];
return 1;
}
void DispStack(sqStack *s)//显示栈中元素值
{
for(int i=s-top;i=0;i--)
couts-data[i]" ";
coutendl;
}
链式存储结构
typedef char ElemType;
typedef struct linknode
{
ElemType data;
struct linknode *next;
}LiStack;
void InitStack(LiStack *s);//初始化栈
void ClearStack(LiStack *s);//摧毁栈
int StackLength(LiStack *s);//返回栈的长度
bool StackEmpty(LiStack *s);//判断栈是否为空
void Push(LiStack *s,ElemType e);//进栈
int Pop(LiStack *s,ElemType e);//出栈
int GetTop(LiStack *s,ElemType e);//取栈顶元素
void DispStack(LiStack *s);//显示栈中元素值
int main()
{
return 0;
}
void InitStack(LiStack *s)//初始化栈
{
s=new LiStack;
s-next=NULL;
}
void ClearStack(LiStack *s)//摧毁栈
{
for(LiStack *p=s-next;p;p=p-next)
{
delete s;
s=p;
p=p-next;
}
delete s;
}
int StackLength(LiStack *s)//返回栈的长度
{
int i=0;
for(LiStack *p=s-next;p;p=p-next)
i++;
return i;
}
bool StackEmpty(LiStack *s)//判断栈是否为空
{
return (s-next==NULL);
}
void Push(LiStack *s,ElemType e)//进栈
{
LiStack *p=new LiStack;
p-data=e;
p-next=s-next;
s-next=p;
}
int Pop(LiStack *s,ElemType e)//出栈
{
LiStack *p;
if(s-next==NULL)
return 0;
p=s-next;
e=p-data;
s-next=p-next;
delete p;
return 1;
}
int GetTop(LiStack *s,ElemType e)//取栈顶元素
{
if(s-next==NULL)
return 0;
e=s-next-data;
return 1;
}
void DispStack(LiStack *s)//显示栈中元素值
{
LiStack *p=s-next;
for(;p;p=p-next)
coutp-data" ";
coutendl;
}
Q3: 某带链的队列初始状态为front=rear=null。经过一系列正常的入队与退队操作后，front=rear=10
带链链式栈实现java代码的队列链式栈实现java代码，
带链队列为空时，front = rear= NULL
插入第1个元素时，rear+1 =1，front+1 = 1
插入第2个元素时，rear+1 =2，front不变
删除第2个元素时，front+1 = 2，rear=2，即 front = rear= 2
而带链队列中还剩有1个元素 。
拓展资料
链式栈是一种数据存储结构，可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，但是需要为每个栈元素分配额外的指针空间用来存放指针域。
介绍
栈是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底（push），最后的数据在栈顶（top），需要读数据的时候从栈顶开始弹出数据（top）最后一个数据被第一个读出来。链式栈中的元素以Node的形式存储，节点Node中存有此节点存于栈中的元素以及指向下个节点的指针。链式栈的数据成员只用保存指向栈顶节点的指针 *top_node。
顺序栈的实现在于使用了数组这个基本数据结构，数组中的元素在内存中的存储位置是连续的，且编译器要求我们在编译期就要确定数组的大小，这样对内存的使用效率并不高，一来无法避免因数组空间用光而引起的溢出问题，二在系统将内存分配给数组后，则这些内存对于其他任务就不可用；而对于链栈而言，使用了链表来实现栈，链表中的元素存储在不连续的地址，由于是动态申请内存，所以我们可以以非常小的内存空间开始，另外当某个项不使用时也可将内存返还给系统。
资料来源：百度百科：链式栈
Q4: 依次将元素A B C D E插入一个初始状态为空的栈顶指针为TOP的链式堆栈中,画出插入完成后的链式堆栈
E
D
C
B
A
1链式栈实现java代码的位置代表TOP栈顶链式栈实现java代码，栈简单来说就是先加入链式栈实现java代码的元素在最下面链式栈实现java代码，所以出栈时最后出来链式栈实现java代码，
也就是先进后出
Q5: (java)有一个100000个节点的树形结构，求所有节点数大于L=3小于R=5的路径的组合，有什么效率高的方法吗？
如果采用非递归算法实现二叉树的前序遍历，需要借助于栈结构。其步骤如下：
如果根节点rt为空，则返回；否则，首先将根节点压入栈中，然后迭代执行以下步骤：
1. 弹出栈顶存放的节点n，访问该节点；
2. 依次将n的右子节点和左子节点压入栈中；
3. 如果栈不为空，则返回步骤1继续执行，否则结束迭代。
其中步骤1为节点访问操作；步骤2中先将右子节点压入栈中然后再将左子节点压入，这是因为在栈的弹出操作服从先入后出的准则，根节点访问结束后需要先访问的是左子节点，所以左子节点在右子节点之后压栈；步骤3是遍历过程终止的条件。
根据上述迭代步骤，图中二叉树的遍历步骤可以分解为如下步骤，对应如图所示。
1． 将n14压栈；
2． 弹出栈顶节点，此时为n14，访问节点n14；
3． 将n14的右子节点n13和左子节点n8依次压入栈中；
4． 弹出栈顶节点，此时为n8，访问节点n8；
5． 将n8的右子节点n7和左子节点n4依次压入栈中；
6． 弹出栈顶节点，此时为n4，访问节点n4；
7． 将n4的右子节点n3和左子节点n2依次压入栈中；
8． 弹出栈顶节点，此时为n2，访问节点n2；
9． n2的右子节点为空，则将n2的左子节点n1压入栈中；
10．弹出栈顶节点，此时为n1，访问节点n1；
11．n1的左子节点为空，则将n1的右子节点n0压入栈中；
12．弹出栈顶节点，此时为n0，访问节点n0；
13．n0为叶节点，则无子节点压栈；
14．弹出栈顶节点，此时为n3，访问节点n3；
15．n3为叶节点，则无子节点压栈；
16．弹出栈顶节点，此时为n7，访问节点n7；
17．将n7的右子节点n6和左子节点n5依次压栈；
18．弹出栈顶节点，此时为n5，访问节点n5；
19．n5为叶节点，无子节点压栈；
20．弹出栈顶节点，此时为n6，访问节点n6；
21．n6为叶节点，无子节点压栈；
22．弹出栈顶节点，此时为n13，访问节点n13；
23．将n13的右子节点n11和左子节点n12依次压栈；
24．弹出栈顶节点，此时为n12，访问节点n12；
25．n12为叶节点，无子节点压栈；
26．弹出栈顶节点，此时为n11，访问节点n11；
27．将n11的右子节点n10和左子节点n9依次压入栈中；
28．弹出栈顶节点，此时为n9，访问节点n9；
29．n9为叶节点，则无子节点压栈；
30．弹出栈顶节点，此时为n10，访问节点n10；
31．n10为叶节点，则无子节点压栈；
32．栈空，遍历过程结束。
图 二叉树前序遍历算法栈结构动态过程
迭代过称中利用了栈结构，图示的栈结构中栈的大小是固定的，事实上在实现时预先设定好栈的大小并不容易，所以在具体实现时，采用第XX章中讨论的链式栈，动态调整栈的大小。
中序遍历
第二种遍历算法称为中序遍历算法。与前序遍历算法相比，中序遍历算法首先访问节点的左子树，然后访问节点自身，最后访问节点的右子树。可见，节点自身是在访问左右子树中间访问的，顾称之为中序。图中的二叉树的中序遍历结果为：
关于链式栈实现java代码和链栈的实现和运算的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
