Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.

Stack ADT(abstract data type)

Introduction of Stack

Normally, mathematics is written using what we call in-fix notation:

[(3+4)\times 5-6 ]

Any operator is placed between two operands. The advantage is that it’s intuitive enough for human, the disadvantage is obvious. When the mathematics formula is too long, it’s full of parentheses and is difficult to find where to start calculation, both for people and computers.

Alternatively, we can place the operands first, followed by the operator.

[3\ \ 4\ \ +\ 5\ \ \times\ 6\ \ – ]

Parsing reads left-to-right and performs any operands on the last two operands.

[\begin{aligned} 3\ \ 4\ \ +\ 5\ \ \times\ 6&\ \ -\ 7\ \ \ \ \ \ \ \ \ \ 5\ \ \times\ 6&\ \ -\ 35\ \ \ \ 6&\ \ -\ 29& \end{aligned}]

This is called Reverse-Polish notation after the mathematician Jan Łukasiewicz.

Its advantage is that no ambiguity and no brackets are needed. And it’s the same process used by a computer to perform computations:

operands must be loaded into register before operations can be performed on them

The easiest way to parse reverse-Polish notation is to use an operand stack. So what is a stack?

What is a stack?

Stack is a last-in-first-out(LIFO) data structure. It’s like a pile of plates. Every time you take the plate, you take the top. After washing the plate, you also put the plate on the top.

Deal with Reverse-Polish Notation

Operands are proceeded by pushing them onto the stack.

When processing an operator:

  1. pop the last two items off the operand stack
  2. perform the operation, and
  3. push the result back onto the stack

Example: how do we evaluate 1 2 3 + 4 5 6 × - 7 × + - 8 9 × - using a stack:

Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.

The equivalent in-fix notation is: $$((1-((2+3)+((4-(5\times 6))\times 7)))+(8\times 9))$$ reduce the parentheses using order-of-operations: $$1-(2+3+(4-5\times 6)\times 7)+8\times 9$$

Implementation of Stack

We have 5 main operation of stack, they are:

  • Push: insert an object onto the top of stack
  • Pop: erase the object on the top of the stack
  • IsEmpty: determine if the stack is empty
  • IsFull: determine if a stack is full
  • CreateStack: generate an empty stack

We expect the optimal asymptotic run time of above operations is (\Theta(1)), which means that the run time of this algorithm is independent of the number of objects being stored in the container.

Operations at the front of a single linked list are all (\Theta(1)).

Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.

The desired behavior of an Abstract Stack may be reproduced by performing all operations at the front.

push_front(int)

void List::push_front(int n){
    list_head = new Node(n, list_head)
}

pop_front()

int List::pop_front(){
    if( empty() ){
        throw underflow();
    }
    int e = front();
    Node *ptr = list_head;
    list_head = list_head->next();
    delete ptr;
    return e;
}

Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.

Array Implementation

For one-ended arrays, all operations at the back are (\Theta(1)). But the insert at the front or pop at front takes (\Theta(n)) to move all element one place backwards.

top()

If there are (n) objects in the stack, the last is located at index (n-1).

template
T Stack::top() const{
    if( empty() ){
        throw underflow();
    }
    return array[stack_size-1];
}

pop()

Remove an object simply involves reducing the size. After decreasing the size, the previous top of the stack is now at the location stack_size.

template
T Stack::pop() const{
    if( empty() ){
        throw underflow();
    }
    stack_size--;
    return array[stack_size];
}

push(obj)

Pushing an object can only be performed if the array is not full

template
void Stack::push(T const &obj) const{
    if( stack_size == array_capacity ){
        throw overflow();
    }
    array[stack_size] = obj;
    stack_size++;
}

Array Capacity

When the array is full, how to increase the array capacity?

So the question is:

How must space will be increased? By a constant or a multiple?

First, let see how an increase works.

Firstly, require a call to new memory: new T[N] where N is the new capacity.

Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.
Next, copy old data to new space:
Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.
The memory for original array must be deallocated:
Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.
Finally, the pointer should point to new memory address:
Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.

Now, back to the original question: How much do we change the capacity?

We recognize that any time we push onto a full stack, this requires (n) copies and the run time is (\Theta(n)). Therefore, push is usually (\Theta(1)) except when new memory is required.

To state the average run time, we introduce the concept of amortized time:

If n operations requires (\Theta(f(n))), we will say that an individual operation has an amortized run time of (\Theta(f(n)/n)).

Using this concept, if inserting n objects requires:

  • (\Theta(n^2)) copies, the amortized time is (\Theta(n))
  • (\Theta(n)) copies, the amortized time is (\Theta(1)), that is what we expect.
Capacity increase 1 analysis

If we increase the capacity by 1 each time the array is full. With each insertion when the array is full, its requires all entries to be copied.

Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.

Suppose we insert $k$ objects – The pushing of the $k^{\text{th}}$ object on the stack requires $k-1$ copies – The total number of copies is: $$\sum_{k=1}^{n}(k-1)=\left(\sum_{k=1}^{n} k\right)-n=\frac{n(n+1)}{2}-n=\frac{n(n-1)}{2}=\Theta\left(n^{2}\right)$$ – So the amortized number of copies is: $$\Theta\left(\frac{n^2}{n}\right)=\Theta(n)$$ – Therefore each push run in $\Theta(n)$ time – The wasted space, however is $\Theta(1)$

Capacity become double size analysis

Suppose we double the number of entries each time the array is full.

Now the copy time become significantly fewer.

Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.
  • Increase $n$ objects would require 1, 2, 4, 8, …, all the way up to the largest $2^k Increase Method Copies per Insertion Unused Memory Increase by 1
    (n-1)

0 Increase by
(m)(n/m)(m-1)

Increase by a factor of 2 1
(n)

Increase by a factor of
(r>1)

1/
((r-1))((r-1)n)

Example Applications

Most parsing uses stacks.

Examples includes:

  • Matching tags in XHTML
  • In C++, matching parentheses (\textbf{(…)}), brackets (\textbf{[…]}) and braces (\textbf{{…}})

Resources: ShanghaiTech 2020Fall CS101 Algorithm and Data Structure.

Original: https://www.cnblogs.com/liuzhch1/p/16246520.html
Author: liuzhch1
Title: Stack栈详解 图解 引入到LinkedList和Array实现、均摊时间分析| Stack ADT details, intro to implementation and amortized time analysis with figures.

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/607034/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

  • Linux的信号(转)

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月24日
    0231
  • Linux部署springboot项目,两种方式

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月26日
    0223
  • redis持久化存储

    redis持久化存储 redis多被用于缓存和消息中间件,当被用作缓存时,数据的读写都是在内存中进行的,而内存一旦在主机断电或者主机重启时里面的数据将被清空,为保证数据不被丢失,r…

    Linux 2023年6月7日
    075
  • Linux服务器性能分析与调优

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月13日
    0293
  • git比较两个分支之间的区别

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月30日
    0248
  • 创建 SysV 风格的 linux daemon 程序

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月9日
    0309
  • Java 集合框架

    一、 Collection集合 1.1 集合概述 集合:集合是java中提供的一种容器,可以用来存储多个数据。 数组的长度是固定的。集合的长度是可变的。 数组中存储的是同一类型的元…

    Linux 2023年6月7日
    054
  • 随便侃侃博客挖坑的事

    很多都没有写博客了,说实在的,Markdown的语法都忘的差不多了。 今年看着停留在提醒上的写博客计划,然后又想了想要写的东西,太多了,都需要花点时间去总结,感觉静不下心来,真的无…

    Linux 2023年6月6日
    069
  • centos7 + maven + git + gitee 通过jenkins实现持续集成

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月30日
    0273
  • 排序起步!Insertion Sort&Bubble Sort: 插排和冒牌排序、冒泡排序优化

    Introduction to Sorting Sorting is the process of Taking a list of objects which could be …

    Linux 2023年6月13日
    059
  • WEB自动化-12-Cypress 调试

    12 调试 Cypress的测试代码和被测试程序在同一生命周期中的浏览器中,也就是意味着,可以使用浏览器的开发者工具直接参与调试。Cypress提供了几种调试方法,分别为: deb…

    Linux 2023年6月7日
    060
  • SpringBoot + Vue + ElementUI 实现后台管理系统模板 — 后端篇(四): 整合阿里云 短信服务、整合 JWT 单点登录

    (1) 相关博文地址: SpringBoot + Vue + ElementUI 实现后台管理系统模板 — 前端篇(一):搭建基本环境:https://www.cnblogs.c…

    Linux 2023年6月11日
    065
  • springBoot 获取注解参数的原理

    判断每个参数带有注解是哪个,是否存在相应的解析器 寻找合适的处理适配器 DispatcherServlet中的 doDispatch方法 // Determine handler …

    Linux 2023年6月7日
    067
  • Linux三剑客命令—sed

    一、概念说明 官方概念说明: stream editor for filtering and transforming text字符流过滤器编辑和文本字符流转换工具 [En] Ch…

    Linux 2023年5月27日
    094
  • CMD如何快速打开当前文件夹窗口

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年8月30日
    0230
  • 为知笔记迁移到印象笔记-从入门到放弃

    注入产生的原理: 数据库设置为GBK编码: 宽字节注入源于程序员设置MySQL连接时错误配置为:set character_set_client=gbk,这样配置会引发编码转换从而…

    Linux 2022年11月7日
    0178
亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球