首页 > 编程语言 >数据结构之栈(Java,C语言的实现)以及相关习题巩固

数据结构之栈(Java,C语言的实现)以及相关习题巩固

时间：2024-05-30 13:44:15浏览次数：35  
标签：return int top 之栈 base printf Java 习题 public

目录

栈

概念以及代码实现

栈是仅限于在表尾进行插入和删除的线性表,它遵循先进后出,后进先出原则

  • 所以可以在递归,判断回文,反转链表.......

image-20240530132703003

代码实现部分java

public interface Stack_i <T>{
    //入栈
    void push(T e);
    //出栈
    T pop();
    //获取栈顶元素
    T peek();
    //获取栈的元素个数
    int size();
    //栈是否为空
    boolean isEmpty();
}

import java.util.Random;
public class MyArr<T> {

    private int capacity = 0;
    private int size = 0;
    private T[] arr;

    public MyArr(int capacity) {
        if (capacity < 0) this.capacity = 10; //if no right input, we will initial capacity 10
        this.capacity = capacity;
        this.arr = (T[]) new Object[capacity];
    }

    public int getCapacity() {
        return capacity;
    }

    public int getSize() {
        return size;
    }

    public T[] setCapacity(int capacity) {
        if (capacity < 0) {
            throw new RuntimeException("扩大小异常");
        }
        this.capacity = capacity;
        T[] newNum = (T[]) new Object[capacity];
        for (int i = 0; i < this.size; ++i) {
            newNum[i] = this.arr[i];
        }
        return newNum;
    }

    //增加元素
    public void add(T val) {
        if (this.size >= this.capacity) {
            this.arr = setCapacity(2 * this.capacity);
        }
        this.arr[this.size++] = val;
    }
    //数组末尾增加元素
    public void addLst(T val){
        this.add(val);
    }

    //删除元素
    public  T removeByIndex(int index) {
        if (index < 0 || index > this.capacity) {
            throw new RuntimeException("数组越界");
        }
        for (int i = index; i < size - 1; ++i) {
            arr[i] = arr[i + 1];
        }
        size--;
        if (size < this.capacity / 4 && this.capacity > 4) {
            arr = setCapacity(this.capacity / 4);
        }
        return this.arr[index];
    }
    //删除数组末尾元素
    public T removeLast(){
        return this.removeByIndex(this.size-1);
    }
    //修改位置元素
    public void modify(int index, T val) {
        if (index < 0 || index > size - 1) {
            throw new RuntimeException("数组越界");
        }
        arr[index] = val;
    }

    //获取某元素位置
    public int locateVal(T val) {
        for (int i = 0; i < size; ++i) {
            if (arr[i] == val) {
                return i;//return index
            }
        }
        // if no find return -1
        return -1;
    }
    //获取尾元素
    public T getLast(){
        return this.arr[this.size-1];
    }
    //打印元素


    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append('[');
        for (int i = 0; i < this.size - 1; ++i) {
            stringBuffer.append(arr[i] + ",");
        }
        if(size>0) stringBuffer.append(arr[size - 1]);
        stringBuffer.append(']');
        return stringBuffer.toString();
    }

}


public class StackImplement<T> implements Stack_i<T>{

    private MyArr<T> data;
    private int size=0;
    @Override
    public void push(T e) {
        this.size++;
        this.data.addLst(e);
    }

    public StackImplement() {
        data = new MyArr<>(10);
    }

    @Override
    public T pop() {
        if(this.isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return this.data.removeLast();
    }

    @Override
    public T peek() {
        return this.data.getLast();
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        if(size==0)return true;
        return false;
    }
    public int getCapacity(){
        return this.data.getCapacity();
    }
}

c语言实现(顺序栈)

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define MAXSIZE 10
typedef int Status;
typedef int Element;

//声明栈的顺序结构定义
typedef struct {
	Element* base;
	Element* top;
	int stackSize;
}SqStack;
//栈的功能
Status InitStack(SqStack* S);//初始化栈
Status Push(SqStack* S, Element e);//入栈操作
Status Pop(SqStack* S, Element* e);//出栈操作,并返回出去的值
Status IsEmpty(SqStack S);//判断栈是否为空
void PrintStack(SqStack S);//打印栈
Status OperateMenu();//用户界面选择
Element GetTop(SqStack S);//获取头元素
void DestroyStack(SqStack* S);//销毁链表
Status ClearStack(SqStack* S);//清理栈中元素
int StackLen(SqStack S);//获取栈长度

int main() {
	SqStack S;
	/*
	赋值为NULL，确保变量具有一个初始状态，避免出现潜在问题,如果没有初始化，
	系统会分配一个随机地址，在后面对指针修改访问时可能会程序崩溃
	*/
	S.base = NULL;
	S.top = NULL;
	S.stackSize = 0;
	int choice;//记录用户选择
	Element e;//元素类型
	int temp = 0;//接受函数返回值
	int len;//获取栈长度
	while (OK) {
		choice = OperateMenu();
		switch (choice)
		{
		case 1:
			InitStack(&S);
			printf("初始化栈\n");
			break;
		case 2:
			printf("请输入要入栈的元素\n");
			scanf("%d", &e);
			temp = Push(&S, e);
			if(temp==-1){
				printf("此栈未被初始化！\n");
				break;
			}
			printf("入栈成功!\n");
			PrintStack(S);//打印元素
			break;

		case 3:
			temp = Pop(&S, &e);
			if(temp==-1){
				printf("此栈未被初始化！\n");
				break;
			}
			if (temp == ERROR) {
				printf("栈空!\n");
				break;
			}
			printf("出栈的元素为:%d\n", e);
			PrintStack(S);
			break;

		case 4:
			temp = IsEmpty(S);
			if(temp==-1){
				printf("此栈未被初始化！\n");
				break;
			}
			if (temp == ERROR) {
				printf("不为空栈!\n");
				PrintStack(S);
				break;
			}
			printf("为空栈\n");
			break;
		case 5:
			PrintStack(S);
			break;
		case 6:
			e = GetTop(S);
			if(e==-2){
				printf("此栈未被初始化！\n");
				break;
			}
			if (e == -1) {
				printf("为空栈\n");
				break;
			}
			printf("栈顶元素为: %d\n", e);
			PrintStack(S);
			break;
		case 7:
			temp = ClearStack(&S);
			if(temp==-1){
				printf("此栈未被初始化！\n");
				break;
			}
			printf("清理成功!\n");
			break;
		case 8:
			len = StackLen(S);
			if(len == -1){
				printf("此栈未被初始化！\n");
				break;
			}
			printf("链表长度为:%d\n", len);
			PrintStack(S);
			break;
		case 9:
			DestroyStack(&S);
			printf("销毁成功\n");
			break;
		default:
			exit(OVERFLOW);
		}

	}
	return 0;
}
Status InitStack(SqStack* S) {
	S->base = (Element*)malloc(sizeof(Element) * MAXSIZE);
	if (S->base == NULL) {
		exit(OVERFLOW);//申请失败,异常结束程序
	}
	S->top = S->base;
	S->stackSize = MAXSIZE;
	//申请成功
	return OK;
}
Status Push(SqStack* S,Element e) {
	//判断栈是否初始化
	if(S->top==NULL||S->base==NULL){
		printf("此栈未被初始化！\n");
		return -1;
	}
	//判断栈是否满
	if (S->top - S->base == S->stackSize) {
		S->base = (Element*)realloc(S->base, sizeof(Element) * MAXSIZE);
		S->stackSize += MAXSIZE;
		S->top = S->base + MAXSIZE;
	}
	*(S->top) = e;
	S->top++;
	//插入完毕
	return OK;
}
Status Pop(SqStack* S, Element* e) {
	if(S->top==NULL||S->base==NULL)return -1;//此栈未被初始化
	if (S->top == S->base)return ERROR;//此时为空栈
	*e = *(--S->top);
	//出栈成功
	return OK;
}
Status IsEmpty(SqStack S) {
	if(S.top==NULL||S.base==NULL)return -1;//此栈未被初始化
	if (S.base == S.top)return OK;//判断空栈
	else return ERROR;
}
void PrintStack(SqStack S) {
	if(S.top==NULL||S.base==NULL){
		printf("此栈未被初始化\n");
		return;//此栈未被初始化
	}
	if (S.base == S.top) {
		printf("此栈为空栈\n");
		return;
	}
	
	Element* ptr = --S.top;
	while (ptr!=S.base) {
		printf("%d\t", *ptr);
		--ptr;
	}
	//打印栈底元素
	printf("%d", *S.base);
	printf("\n");
	return;
}
Status OperateMenu() {
	int choice = 0;//记录用户选择
	printf("----------------欢迎使用栈----------------\n");
	printf("----------------1.初始化栈----------------\n");
	printf("----------------2.入栈操作----------------\n");
	printf("----------------3.出栈操作----------------\n");
	printf("----------------4.判断栈是否为空----------\n");
	printf("----------------5.打印栈------------------\n");
	printf("----------------6.获取头元素--------------\n");
	printf("----------------7.清空列表元素------------\n");
	printf("----------------8.获取栈的长度------------\n");
	printf("----------------9.销毁栈------------------\n");
	printf("----------------10.退出--------------------\n");
	printf("----------------请输入选项----------------\n");
	scanf("%d", &choice);
	return choice;

}
Element GetTop(SqStack S) {
	if(S.top==NULL||S.base==NULL)return -2;//此栈未被初始化
	if (S.base == S.top) return -1;	
	return *(--S.top);
}
void DestroyStack(SqStack* S) {
	S->base = NULL;
	S->top = NULL;
	S->stackSize = 0;
}
Status ClearStack(SqStack* S) {
	if(S->top==NULL||S->base==NULL)return -1;//此栈未被初始化
	if (S->top == S->base)return ERROR;//空表
	S->top = S->base;
	return OK;
}
int StackLen(SqStack S) {
	if(S.top==NULL||S.base==NULL)return -1;//此栈未被初始化
	return S.top - S.base;
}

例题

232. 用栈实现队列

1614. 括号的最大嵌套深度

给定 有效括号字符串 s，返回 s 的 嵌套深度。嵌套深度是嵌套括号的 最大 数量。

示例 1：

输入：s = "(1+(2*3)+((8)/4))+1"

输出：3

解释：数字 8 在嵌套的 3 层括号中。

示例 2：

输入：s = "(1)+((2))+(((3)))"

输出：3

解释：数字 3 在嵌套的 3 层括号中。

示例 3：

输入：s = "()(())((()()))"

输出：3

提示：

  • 1 <= s.length <= 100
  • s 由数字 0-9 和字符 '+'、'-'、'*'、'/'、'('、')' 组成
  • 题目数据保证括号字符串 s 是 有效的括号字符串
java
    
class Solution {
    public int maxDepth(String s) {
        // 使用top表示栈顶指针
        int top = 0;
        // 记录括号数量
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            // 如果碰见左括号说明 括号深度增加 即入栈
            if (s.charAt(i) == '(') {
                ++top;
                // 记录最大深度
                if (top > res) {
                    res = top;
                }
                // 碰到右括号出栈 深度就减少
            } else if (s.charAt(i) == ')') {
                --top;
            }
        }
        return res;
    }
}

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

示例 1：

img

输入：head = [1,2,2,1]
输出：true

示例 2：

img

输入：head = [1,2]
输出：false

提示：

  • 链表中节点数目在范围[1, 105] 内
  • 0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
     public boolean isPalindrome(ListNode head) {
        // 利用栈的先进后出原则 
        /*
        可以把链表节点都入栈 然后逐一出栈 栈底指针与栈顶指针对比元素即可
         */
        int[] stack = new int[100001];
        int base = 0;
        int top = 0;
        ListNode p = head;
        while (p != null) {
            stack[top++] = p.val;
            p = p.next;
        }
        --top;
        while(base<=top){
            if(stack[base]!=stack[top])return false;
            base = base+1;
            top = top-1;
        }
        return true;
    }
}

1614. 括号的最大嵌套深度

LCR 123. 图书整理 I

206. 反转链表

402. 移掉 K 位数字

844. 比较含退格的字符串

LCR 036. 逆波兰表达式求值

[面试题 03.01. 三合一](

标签：return,int,top,之栈,base,printf,Java,习题,public
From： https://www.cnblogs.com/cwyYYDS/p/18222182

相关文章

  • 数据结构 顺序表(C语言 与 Java实现)以及部分练习题
    目录数据结构数组(顺序表)特点使用Java实现更高级的数组C语言实现总结优点缺点例题26.删除有序数组中的重复项1.两数之和27.移除元素153.寻找旋转排序数组中的最小值485.最大连续1的个数414.第三大的数2656.K个元素的最大和LCP06.拿硬币2057.值相等的最小索引26.删......
  • 基于Java+Vue的园区智能化管理系统：综合管控，推进数字化转型（代码分享）
    前言：智慧园区管理平台是一个集成了多种功能的综合性系统，旨在通过信息化、智能化手段提升园区的管理效率和服务质量。以下是针对系统的各个功能模块的简要描述：一、楼栋管理会务管理：管理园区内的会议预约、会议室使用等。园区信息：展示园区的基本信息，如位置、面积、规划等。楼......
  • Java中Comparable接口和Comparator接口的区别（如果想知道Java中Comparable接口和Compar
        前言：在Java中，Comparable接口和Comparator接口都用于对象之间的比较和排序，但它们在使用和设计上存在一些关键的区别。✨✨✨这里是秋刀鱼不做梦的BLOG✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客        本篇文章主要讲解的是J......
  • JavaSE 面向对象程序设计 文件File 介绍练习加千行代码详解
    介绍在Java中，File类是用于表示文件和目录路径的抽象。它提供了一组方法来创建、删除、重命名、检查文件/目录的存在性、以及查询文件/目录的属性等功能。File类可以用于执行文件系统操作，如创建新文件、删除文件、检查文件是否存在等。目的是把字符串先表示为路径然后转化......
  • Java 五种内部类演示及底层原理详解
    内部类什么是内部类在A类的内部定义B类，B类就被称为内部类发动机类单独存在没有意义发动机为独立个体可以在外部其他类里创建内部类的对象去调用方法类的五大成员属性方法构造方法代码块内部类内部类的访问特点内部类可以直接访问外部类的成员，包括私有外部类要......
  • java+sql企业固定资产管理系统
    摘要：本文主要介绍的是固定资产管理系统的整个设计过程。第1章的绪论包括选题的背景，目的和意义，国内外现状；第2章平台简介包括JBuilder2005和SQLServer数据库的介绍；第3章系统分析，需求分析，数据流与数据字典，功能需求；第4章系统设计部分包括系统总体设计，功能模块设计，数据库设计；第5章......
  • 使用Java API 操作MongoDB
    除了通过启动mongo进程进入Shell环境访问数据库外，MongoDB还提供了其他基于编程语言的数据库访问方法。MongoDB官方提供了编程语言的驱动包，利用这些驱动包可以使用编程方法连接并操作MongoDB数据库。想要使用 Java程序操作 MongoDB，需要确保您的电脑上已经安装了Mong......
  • 为何Java抽象类是代码架构的基石？
    效率工具推荐一个程序员的常用工具网站，效率加倍嘎嘎好用：程序员常用工具云服务器云服务器限时免费领：轻量服务器2核4G腾讯云：2核2G4M云服务器新老同享99元/年，续费同价阿里云：2核2G3M的ECS服务器只需99元/年，续费同价为何Java抽象类是代码架构的基石？Java抽象类是面向对象编......
  • Java毕业设计-基于springboot开发的旅游网站-毕业论文（附毕设源代码）
    文章目录前言一、毕设成果演示（源代码在文末）二、毕设摘要展示1、开发说明2、需求/流程分析3、系统功能结构三、系统实现展示1、用户信息管理2、旅游动态管理3、景点信息管理4、公告信息管理四、毕设内容和源代码获取总结Java毕业设计-基于springboot开发的旅游网站-......
  • Java开发工具|推荐收藏
    Java是一种广泛使用的编程语言，拥有多种开发工具，包括集成开发环境（IDE）和代码编辑器。以下是几种常见的Java开发工具以及它们的比较：Eclipse是一款流行的开源IDE，广泛用于Java开发。它具有强大的代码编辑、调试和性能分析功能，支持插件扩展，可以满足不同开发需求。Eclipse......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99