精华内容
下载资源
问答
  • * 文件描述:使用堆栈存储模型(后进先出)来挂载链表数据 * 头部插入链表方式相当于堆栈模型的存储模式 * 编辑人:王廷云 * 编辑日期:2017-11-12 * 修改日期:2018-2-1 *********************...
    /***************************************************
     * 文件名:ListStack
     * 文件描述:使用堆栈存储模型(后进先出)来挂载链表数据
     *         头部插入链表方式相当于堆栈模型的存储模式
     * 编辑人:王廷云
     * 编辑日期:2017-11-12
     * 修改日期:2018-2-1
    ***************************************************/
    
    #include <stdio.h>
    #include <stdlib.h> 
    
    /* 数据节点封装 */
    struct node
    {
    	char data;
    	struct node *next;
    } stackHead = {.next = NULL};
    
    /* 栈模型函数 */
    void push(char data);               // 压栈
    int pop(void);                      // 出栈
    int top(void);                      // 栈顶
    int isEmptyStack(void);             // 栈空
    int isFullStack(void);              // 栈满
    
    /* 括号匹配检查函数 */
    void check(char left, char right);  
    
    int main(void)
    {
    	char buff[1024];
    	int i = 0;
    
    	printf("\n=====输入带有括号的字符串=====\n");
    	scanf("%s", buff);
    	
    	/* 循环检查直到检查完毕 */
    	while (buff[i])
    	{
    		switch (buff[i])
    		{
    			/* 左括号入栈 */
    			case '(':  /* no break */
    			case '[':	
    			case '{':
    			case '<': push(buff[i]);	   break;
    			
    			/* 右括号出栈检查 */
    			case ')': check('(', buff[i]); break;
    			case ']': check('[', buff[i]); break;
    			case '}': check('{', buff[i]); break;
    			case '>': check('<', buff[i]); break;
    		}
    		i++;
    	}
    	
    	/* 检查完所有右括号字符后还有左括号说明不匹配 */
    	while (!isEmptyStack())
    	{
    		printf("\'%c\'是多余的括号!\n", pop());
    	}
    
    	return 0;
    }
    
    /**
     * 函数名:push
     * 函数功能:数据节点入栈
     * 参数:data:入栈的数据
     * 返回值:void
    */
    void push(char data)
    {
    	struct node *newOne;
    
    	/* 分配新节点数据空间 */
    	newOne = malloc(sizeof(newOne));
    	if (NULL == newOne)
    	{
    		printf("Push data error! Maybe stack of memry is full!\n");
    		exit(1);
    	}
    	
    	/* 给新节点赋值数据 */
    	newOne->data = data;
    	
    	/* 链表头插入节点方式模拟入栈 */	
    	newOne->next = stackHead.next;
    	stackHead.next = newOne;
    }
    
    /**
     * 函数名:pop
     * 函数功能:数据节点出栈
     * 参数:void
     * 返回值:栈顶数据
    */
    int pop(void)
    {
    	struct node *topNode;
    	char topData; 
    
    	topNode = stackHead.next;			// 先保存栈顶数据地址
    	topData = stackHead.next->data;		// 取栈顶数据
    	
    	stackHead.next = topNode->next;	// 摘掉栈顶节点
    	free(topNode);
    
    	return topData;						// 返回栈顶数据
    }
    
    /**
     * 函数名:top
     * 函数功能:获取栈顶数据
     * 参数:void
     * 返回值:栈顶数据
    */
    int top(void)
    {
    	return stackHead.next->data;
    }
    
    /**
     * 函数名:isEmptyStack
     * 函数功能:判断栈是否为空
     * 参数:void
     * 返回值:栈为空返回1,不为空返回0
    */
    int isEmptyStack(void)
    {
    	return stackHead.next == NULL;
    }
    
    /**
     * 函数名:isFullStack
     * 函数功能:判断栈是否已满
     * 参数:void
     * 返回值:0-链表不存在满的情况
    */
    int isFullStack(void)
    {
    	return 0;
    }
    
    /**
     * 函数名:check
     * 函数功能:通过检查括号是否匹配
     * 参数:left: 左括号  right: 右括号 
     * 返回值:void
    */
    void check(char left, char right)
    {
    	char temp;
    
    	if (isEmptyStack())
    	{
    		printf("%c 是多余的括号\n", right);
    		exit(1);
    	}
    	
    	temp = pop();
    	if (temp != left)
    	{
    		printf("\'%c\' 和 \'%c\' 不匹配\n",left,right);
    		exit(1);
    	}
    }
    
    展开全文
  • 使用链表进行模拟栈比用数组好用,考虑的要素也少还方便。 链表结构 private class Node{//链表结构 Item item; Node next; } 迭代器 private class Iterator implements java.util.Iterator<Item>{//迭代...

    使用链表进行模拟栈比用数组好用,考虑的要素也少还方便。

    链表结构

    private class Node{//链表结构
                Item item;
                Node next;
            }
    

    迭代器

    private class Iterator implements java.util.Iterator<Item>{//迭代器
    
                private Node p=first;
                @Override
                public boolean hasNext() {
                    return p!=null;
                }
    
                @Override
                public Item next() {
                    Item item=p.item;
                    p=p.next;
                    return item;
                }
    
                @Override
                public void remove() {
    
                }
            }
    

    完整源代码

     static class stack<Item>{
            private Node first;
            private int N;
            private class Node{//链表结构
                Item item;
                Node next;
            }
            private int size(){
                return N;
            }
            private boolean isEmpty(){
                return first==null;
            }
            private void push(Item item){//入栈
                Node oldfirest=first;
                first=new Node();
                first.item=item;
                first.next=oldfirest;
                N++;
            }
            private Item pop(){//出栈
                Item item=first.item;
                first=first.next;
                N--;
                return item;
            }
            private Iterator iterator(){
                return new Iterator();
            }
            private class Iterator implements java.util.Iterator<Item>{//迭代器
    
                private Node p=first;
                @Override
                public boolean hasNext() {
                    return p!=null;
                }
    
                @Override
                public Item next() {
                    Item item=p.item;
                    p=p.next;
                    return item;
                }
    
                @Override
                public void remove() {
    
                }
            }
    
        }
    

    简单的使用

    static public void main(String[] args) {
            stack<String> stack = new stack<String>();
            System.out.println("入栈中... ...");
            stack.push("hello world!");
            stack.push("hello Java!");
            stack.push("hello stack");
            System.out.println("--------出栈---------");
            String pop = stack.pop();
            System.out.println(pop);
            System.out.println("--------迭代--------");
            ListStack.stack<String>.Iterator iterator = stack.iterator();
            while(iterator.hasNext()){
                System.out.println(iterator.next());
            }
    

    在这里插入图片描述

    展开全文
  • 具体而言,栈的数据结点必须后进先出。 宏观上来看,与数组或链表相比,栈的操作更为受限,那为什么我们要用这种受限的栈呢?其实,单纯从功能上讲,数组或者链表可以替代栈。然而问题是,数组或者链表的操作过于...

    1、栈是什么

    首先线性表是使用非常广泛的一类数据结构,它对数据的顺序非常敏感,而且它对数据的增删操作非常灵活。
    是一种特殊的线性表。栈与线性表的不同,体现在增和删的操作。具体而言,栈的数据结点必须后进先出

    宏观上来看,与数组或链表相比,栈的操作更为受限,那为什么我们要用这种受限的栈呢?其实,单纯从功能上讲,数组或者链表可以替代栈。然而问题是,数组或者链表的操作过于灵活,这意味着,它们过多暴露了可操作的接口。这些没有意义的接口过多,当数据量很大的时候就会出现一些隐藏的风险。一旦发生代码 bug 或者受到攻击,就会给系统带来不可预知的风险。虽然栈限定降低了操作的灵活性,但这也使得栈在处理只涉及一端新增和删除数据的问题时效率更高。

    举个实际的例子,浏览器都有页面前进和后退功能,这就是个很典型的后进先出的场景。假设你先后访问了五个页面,分别标记为 1、2、3、4、5。当前你在页面 5,如果执行两次后退,则退回到了页面 3,如果再执行一次前进,则到了页面 4。处理这里的页面链接存储问题,栈就应该是我们首选的数据结构。

    栈既然是线性表,那么它也包含了表头表尾。不过在栈结构中,由于其操作的特殊性,会对表头和表尾的名字进行改造。表尾用来输入数据,通常也叫作栈顶(top);相应地,表头就是栈底(bottom)。栈顶和栈底是用来表示这个栈的两个指针。跟线性表一样,栈也有顺序表示和链式表示,分别称作顺序栈和链栈。

    2、栈的基本操作

    栈对于数据有增、删、查处理。对于栈的新增操作,通常也叫作 push 或压栈。对于栈的删除操作,通常也叫作 pop 或出栈。栈分为顺序栈和链栈。
    线性栈:
    栈的顺序存储可以借助数组来实现。一般来说,会把数组的首元素存在栈底,最后一个元素放在栈顶。然后定义一个 top 指针来指示栈顶元素在数组中的位置。假设栈中只有一个数据元素,则 top = 0。一般以 top 是否为 -1 来判定是否为空栈。当定义了栈的最大容量为 StackSize 时,则栈顶 top 必须小于 StackSize。

    当需要新增数据元素,即入栈操作时,就需要将新插入元素放在栈顶,并将栈顶指针增加 1。如下图所示:
    在这里插入图片描述
    删除数据元素,即出栈操作,只需要 top - 1 就可以了。

    对于查找操作,栈没有额外的改变,跟线性表一样,它也需要遍历整个栈来完成基于某些条件的数值查找。

    链栈:
    关于链式栈,就是用链表的方式对栈的表示。通常,可以把栈顶放在单链表的头部,如下图所示。由于链栈的后进先出,原来的头指针就显得毫无作用了。因此,对于链栈来说,是不需要头指针的。相反,它需要增加指向栈顶的 top 指针,这是压栈和出栈操作的重要支持。
    在这里插入图片描述
    对于链栈,新增数据的压栈操作,与链表最后插入的新数据基本相同。需要额外处理的,就是栈的 top 指针。如下图所示,插入新的数据,则需要让新的结点指向原栈顶,即 top 指针指向的对象,再让 top 指针指向新的结点。
    在这里插入图片描述
    在链式栈中进行删除操作时,只能在栈顶进行操作。因此,将栈顶的 top 指针指向栈顶元素的 next 指针即可完成删除。对于链式栈来说,新增删除数据元素没有任何循环操作,其时间复杂度均为 O(1)。

    对于查找操作,相对链表而言,链栈没有额外的改变,它也需要遍历整个栈来完成基于某些条件的数值查找。

    展开全文
  • 计算机中很多场景会遇到“后存入的元素被调用”(LIFO)的情况,例如编辑器的撤销操作、系统的递归调用操作。数组(Array)作为一种线性表,它可以在任意位置插入元素和取出元素,如果将数组限制为只能在尾部插入...

    设计背景

    计算机中很多场景会遇到“后存入的元素先被调用”(LIFO)的情况,例如编辑器的撤销操作、系统的递归调用操作。数组(Array)作为一种线性表,它可以在任意位置插入元素和取出元素,如果将数组限制为只能在尾部插入和取出元素,那么就实现了这种需求。这种数据结构被称之为栈(Stack)。
    在这里插入图片描述


    结构分析

    【结构类型】线性结构
    【底层实现】动态数组(ArrayList) / 链表(LinkedList)
    【核心方法】
    public void push(E e); //入栈
    public void pop(); //出栈
    public E peek(); //获取栈顶的元素
    【差异分析】动态数组(ArrayList)和链表(LinkedList)都可以作为栈(Stack)的底层结构。在数值量不大的情况下,ArrayListStack的速度可能稍慢于LinkedListStack,因为ArrayList会面临频繁的扩容和缩容操作;但在数值量较大的情况下,LinkedListStack可能会耗用更长的时间,这是因为LinkedList虽不受容量约束,但其不断进行着new节点的操作;这些差异还将将取决于JVM等客观因素。


    代码实现

    1. 利用ArrayList实现

    public class ArrayStack<E> implements Stack<E> {
        /**
         * 实例域:动态数组
         */
        private ArrayList<E> array;
    
        /**
         * 带参构造器:对实例域进行初始化
         * @param capacity 数组容量
         */
        public ArrayStack(int capacity) {
            array = new ArrayList<>(capacity);
        }
    
        /**
         * 无参构造器:对实例域进行初始化
         */
        public ArrayStack() {
            array = new ArrayList<>();
        }
    
        @Override
        public void push(E e) {
            array.addLast(e);
        }
    
        @Override
        public E pop() {
            return array.removeLast();
        }
    
        @Override
        public E peek() {
            return array.get(getSize() - 1);
        }
    
        @Override
        public boolean isEmpty() {
            return false;
        }
    
        @Override
        public int getSize() {
            return array.getSize();
        }
    
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Stack: ");
            res.append('[');
            for (int i = 0; i < array.getSize(); i++) {
                res.append(array.get(i));
                if (i != array.getSize() - 1) {
                    res.append(", ");
                }
            }
            res.append("] top");
            return res.toString();
        }
    
    }
    

    2. 利用LinkedList实现

    public class LinkedListStack<E> implements Stack<E> {
    
        /**
         * 实例域:链表
         */
        LinkedList<E> linkedList;
    
        /**
         * 无参构造器:利用默认值初始化实例域
         */
        public LinkedListStack() {
             linkedList = new LinkedList<>();
        }
    
        @Override
        public void push(E e) {
            linkedList.addFirst(e);
        }
    
        @Override
        public E pop() {
            return linkedList.removeFirst();
        }
    
        @Override
        public E peek() {
            return linkedList.getFirst();
        }
    
        @Override
        public boolean isEmpty() {
            return linkedList.isEmpty();
        }
    
        @Override
        public int getSize() {
            return linkedList.getSize();
        }
    
        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            res.append("Stack: ");
            res.append("top [");
            res.append(linkedList);
            res.append("]");
            return res.toString();
        }
    
    }
    
    展开全文
  • 出栈:指数据的删除操作(数据也在栈顶)。 栈的实现:一般可以用数组或者链表,但是用数组实现更优一点,因为数组在尾插尾删上的代价较小。 下面,我们来实现支持动态增长的栈: typedef int STData...
  • 数据结构-栈结构栈结构链表...总结:后进先出 链表实现 // ConsoleApplication3.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" struct Student { int grade; struct Stude...
  • 链表

    2017-08-27 23:06:05
    《算法》—链表 ...栈:又叫下压栈,是一种基于后进先出(LIFO)策略的集合类型。 链表定义:链表是一种递归的数据结构,它或者为空(null),或者指向一个结点的引用,该结点包含一个元素和一个指向另一条链表
  • 堆栈(Strack)是指这样一段内存,它可以理解为一个筒结构,先放进筒中的数据被后放进筒中的数据“压住”,只有后放进筒中的数据都取出后,先放进去的数据才能被取出,称为“后进先出”。堆栈的长度可随意增加。堆栈...
  • 翻转链表

    2018-11-17 00:44:21
    因为链表翻转是将最后一个元素放到第一个,第一个放到最后,遍历时由只能从前向后,这符合栈后进先出的特点,考虑的使用栈会增加空间的开销,因为可以使用具有后进先出特性的递归。 class Solution{ public ...
  • 反转链表

    2019-07-15 20:51:36
    返回一个反序的链表,这就是经典的“后进先出”,我们可以使用栈实现这种顺序。每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,给一个新的链表结构,这样链表就...
  • 逆向输出链表

    千次阅读 2015-10-16 20:34:16
    在不改变链表结构的前提下,使用一个后进先出的数据结构(栈)存储正向遍历链表的结果,根据后进先出的特点:最后一个进入的数据最先被弹出,可以逆向打印出链表。我们也可以根据递归来逆向输出链表。#include #...
  • 链表反转

    2017-07-16 10:56:42
    题目要求从尾到头打印链表的节点值,可以联想到栈的特性:后进先出。由此入手解决问题。 三、代码实现 // 输入一个链表,从尾到头打印链表每个节点的值 import java.util.Stack; import java.util.ArrayList; ...
  • 返回一个反序的链表,这就是经典的“后进先出”,我们可以使用栈实现这种顺序。每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,给一个新的链表结构,这样链表就...
  • 返回一个反序的链表,这就是经典的“后进先出”,我们可以使用栈实现这种顺序。每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,给一个新的链表结构,这样链表就...
  • LeetCode 206. 反转链表

    2020-05-12 10:11:39
    LeetCode 206. 反转链表前言题目答案 ...我使用的是栈来实现,利用栈后进先出的特点 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { va
  • 打印链表

    2016-09-03 19:34:59
    题目描述 输入一个链表,从尾到头打印链表每个节点的值。...方法一:借助堆栈的“后进先出”实现 /** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val =
  • 剑指Offer(三):从尾到头打印链表 ...返回一个反序的链表,这就是经典的“后进先出”,我们可以使用栈实现这种顺序。每经过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结...
  • 思路:跟之前的那题,反转打印链表有点类似想法就是,将链表中的数据全部读取到一个栈里面,因为反转就是后进先出,再把栈里的数据全部重新建一个新的链表。遇到的问题是:分不清NULL 和nullptr 卡了很久 /* struct ...
  • 借助 stack 后进先出的特点,放进去的时候是 1,2 。拿出来的时候就是 2,1 两个节点了。 再把这两个节点串联起来,重复这个逻辑遍历完整个链表,就可以做到两两反转的效果了。 虽然用到了 stack,但因为只存了两个...
  • 链表题目一道

    2020-07-10 11:11:40
    要将链表翻转,很容易想到借助栈的后进先出的性质来改变链表的顺序。 将链表节点顺序压入栈中,链表节点全部进栈以后,取栈顶元素作为新链表的头节点,然后将元素不断出栈,每出栈一个元素就连接到新链表的末尾。 ...
  • 链表面试题

    2017-07-12 20:15:15
    1.简单链表 给出如下链表,有以下要求: ...解题思路:利用栈的后进先出特性来解决 代码如下: void R_print(Node* Head)//逆序打印链表 { if(Head==NULL) return ; stack s1; Node* cur=Head; while(cur)
  • 文章目录题目描述分析代码(python...标椎做法:后进先出 利用 栈 数据结构。 简易做法:利用 python list 数据结构求逆。 代码(python list) # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x):...
  • 关注上方“深度学习技术前沿”,选择“星标公众号”,资源干货,第一时间送达!剑指Offer(三):从尾到头打印链表...返回一个反序的链表,这就是经典的“后进先出”,我们可以使用栈实现这种顺序。每经过一个结点的时...
  • 邻接链表

    2016-05-29 20:26:07
     邻接表特殊之处在于,其存图如栈一般,是LIFO(后进先出), 即:当以某一点(s)做为起始点时,如果之后再发现有点跟 其(s)有相连关系,则是将点加入到原先已经存完点链表的前面, 即:出现的点是往前插入的; */...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,592
精华内容 636
关键字:

后进先出链表