- 浏览: 863400 次
- 性别:
- 来自: 上海
文章分类
最新评论
-
yukang1:
蚂蚁lovejing 写道我也出现与楼上相同的问题。查了一些资 ...
Spring中实现文件上传 -
史玉凤:
必须用ie浏览器
javascript获取客户端网卡MAC地址和IP地址和计算机名 -
蚂蚁lovejing:
我也出现与楼上相同的问题。查了一些资料,描述的跟楼主的博文差不 ...
Spring中实现文件上传 -
温柔一刀:
djlijian 写道最近也在研究redis,如何在项目中使用 ...
Redis 常见的性能问题和解决方法 -
djlijian:
最近也在研究redis,如何在项目中使用呢?感觉网上的资料太少 ...
Redis 常见的性能问题和解决方法
Stacks and queues are the first entities we have discussed that are not strictly built into Ruby. By this we mean that Ruby does not have Stack and Queue classes as it does Array and Hash classes (except for the Queue class in tHRead.rb, which we'll mention later).
And yet, in a way, they are built into Ruby after all. In fact, the Array class implements all the functionality we need to treat an array as a stack or a queue. We'll see this in detail shortly.
A stack is a last-in first-out (LIFO) data structure. The traditional everyday example is a stack of cafeteria trays on its spring-loaded platform; trays are added at the top and also taken away from the top.
A limited set of operations can be performed on a stack. These include push and pop (to add and remove items) at the very least; usually there is a way to test for an empty stack, and there may be a way to examine the top element without removing it. A stack implementation never provides a way to examine an item in the middle of the stack.
You might ask how an array can implement a stack since array elements may be accessed randomly, and stack elements may not. The answer is simple. A stack sits at a higher level of abstraction than an array; it is a stack only so long as you treat it as one. The moment you access an element illegally, it ceases to be a stack.
Of course, you can easily define a Stack class so that elements can only be accessed legally. We will show how this is done.
It is worth noting that many algorithms that use a stack also have elegant recursive solutions. The reason for this becomes clear with a moment's reflection. Function or method calls result in data being pushed onto the system stack, and these data are popped upon return. Thus a recursive algorithm simply trades an explicit user-defined stack for the implicit system-level stack. Which is better? That depends on how you value readability, efficiency, and other considerations.
A queue is a first-in first out (FIFO) data structure. It is analogous to a group of people standing in line at (for example) a movie theater. Newcomers go to the end of the line, while those who have waited the longest are the next served. In most areas of programming, queues are probably used less often than stacks.
Queues are useful in more real-time environments where entities are processed as they are presented to the system. They are useful in producer-consumer situations (especially where threads or multitasking are involved). A printer queue is a good example; print jobs are added to one end of the queue, and they "stand in line" until they are removed at the other end.
The two basic queue operations are usually called enqueue and dequeue in the literature. The corresponding instance methods in the Array class are called unpush and shift, respectively.
Note that unshift could serve as a companion for shift in implementing a stack, not a queue, because unshift adds to the same end from which shift removes. Various combinations of these methods could implement stacks and queues, but we will not concern ourselves with all the variations.
That ends our introductory discussion of stacks and queues. Now let's look at some examples.
9.2.1. Implementing a Stricter Stack
We promised earlier to show how a stack could be made "idiot-proof" against illegal access. We may as well do that now. Here is a simple class that has an internal array and manages access to that array. (There are other ways of doing thisby delegating, for examplebut what we show here is simple and works fine.)
class Stack def initialize @store = [] end def push(x) @store.push x end def pop @store.pop end def peek @store.last end def empty? @store.empty? end end
We have added one more operation that is not defined for arrays; peek simply examines the top of the stack and returns a result without disturbing the stack.
Some of the rest of our examples assume this class definition.
9.2.2. Detecting Unbalanced Punctuation in Expressions
Because of the nature of grouped expressions such as parentheses and brackets, their validity can be checked using a stack. For every level of nesting in the expression, the stack will grow one level higher; when we find closing symbols, we can pop the corresponding symbol off the stack. If the symbol does not correspond as expected, or if there are symbols left on the stack at the end, we know the expression is not well-formed.
def paren_match(str) stack = Stack.new lsym = "{[(<" rsym = "}])>" str.each_byte do |byte| sym = byte.chr if lsym.include? sym stack.push(sym) elsif rsym.include? sym top = stack.peek if lsym.index(top) != rsym.index(sym) return false else stack.pop end # Ignore non-grouped characters... end end # Ensure stack is empty... return stack.empty? end str1 = "(((a+b))*((c-d)-(e*f))" str2 = "[[(a-(b-c))], [[x,y]]]" paren_match str1 # false paren_match str2 # true
The nested nature of this problem makes it natural for a stack-oriented solution. A slightly more complex example would be the detection of unbalanced tags in HTML and XML. The tokens are multiple characters rather than single characters, but the structure and logic of the problem remain exactly the same. Some other common stack-oriented problems are conversion of infix expressions to postfix form (or vice versa), evaluation of a postfix expression (as is done in a Java VM or many other interpreters), and in general any problem that has a recursive solution. In the next section, we'll take a short look at the relationship between stacks and recursion.
9.2.3. Understanding Stacks and Recursion
As an example of the isomorphism between stack-oriented algorithms and recursive algorithms, we will take a look at the classic "Tower of Hanoi" problem.
According to legend, there is an ancient temple somewhere in the far east, where monks have the sole task of moving disks from one pole to another while obeying certain rules about the moves they can make. There were originally 64 disks on the first pole; when they finished, the world would come to an end.
As an aside, we like to dispel myths when we can. It seems that in reality, this puzzle originated with the French mathematician Edouard Lucas in 1883 and has no actual basis in eastern culture. What's more, Lucas himself named the puzzle the "Tower of Hanoi" (in the singular).
So if you were worried about the world ending . . . don't worry on that account. And anyway, 64 disks would take 264-1 moves. A few minutes with a calculator reveals that those monks would be busy for millions of years.
But on to the rules of the game. (We'll explain this even though every first-year computer science student in the world has already seen the puzzle.) We have a pole with a certain number of disks stacked on it; call this the source pole. We want to move all of these to the destination pole, using a third (auxiliary) pole as an intermediate resting place. The catch is that you can only move one disk at a time, and you cannot ever place a larger disk onto a smaller one.
The following example uses a stack to solve the problem. We use only 3 disks because 64 would occupy a computer for centuries.
def towers(list) while !list.empty? n, src, dst, aux = list.pop if n == 1 puts "Move disk from #{src} to #{dst}" else list.push [n-1, aux, dst, src] list.push [1, src, dst, aux] list.push [n-1, src, aux, dst] end end end list = [] list.push([3, "a", "c", "b"]) towers(list)
The output produced here is:
Move disk from a to c Move disk from a to b Move disk from c to b Move disk from a to c Move disk from b to a Move disk from b to c Move disk from a to c
Of course, the classic solution to this problem is recursive. And as we already pointed out, the close relationship between the two algorithms is no surprise because recursion implies the use of an invisible system-level stack.
def towers(n, src, dst, aux) if n==1 puts "Move disk from #{src} to #{dst}" else towers(n-1, src, aux, dst) towers(1, src, dst, aux) towers(n-1, aux, dst, src) end end towers(3, "a", "c", "b")
The output produced here is the same. And it may interest you to know that we tried commenting out the output statements and comparing the runtimes of these two methods. Don't tell anyone, but the recursive version is twice as fast.
9.2.4. Implementing a Stricter Queue
We define a queue here in much the same way we defined a stack earlier. If you want to protect yourself from accessing such a data structure in an illegal way, we recommend this practice.
class Queue def initialize @store = [] end def enqueue(x) @store << x end def dequeue @store.shift end def peek @store.first end def length @store.length end def empty? @store.empty? end end
We should mention that there is a Queue class in the thread library that works very well in threaded code. There is even a SizedQueue variant.
These queues use the method names enq and deq rather than the longer names shown in the preceding example. They also allow the names push and pop, which seems misleading to me. The data structure is FIFO, not LIFO; that is, it is a true queue and not a stack.
Of course, the Queue class in tHRead.rb is thread-safe, which is a good enough reason for it to exist. If you need a thread-safe Stack class, I recommend you take the Queue class as a starting point. This should be a quick and easy fix.
The first edition of this book had a lengthy example of queue usage here. Like some of the stack examples, it has been omitted from this edition to save space.
发表评论
-
Query
2008-01-31 17:39 48class System::FastQuery de ... -
Fast Query
2008-01-19 15:07 4037class System::FastQuery def s ... -
9.3. Working with Trees
2008-01-19 15:06 3830I think that I shall never se ... -
9.1. Working with Sets
2008-01-19 15:03 3387We've already seen how certain ... -
8.3. Enumerables in General
2008-01-19 14:26 3530What makes a collection enumera ... -
8.2. Working with Hashes
2008-01-19 14:25 3783Hashes are known in some circle ... -
计算两个字符串之间的Levenshtein距离
2008-01-09 23:32 5218Levenshtein距离 class String ... -
字符串的编码和解码
2008-01-09 23:11 3844rot13编码和解码 class String def r ... -
rails应用自动化部署——使用capistrano2.0
2007-10-10 18:59 6304昨天用capistrano2.0把应用部署搞的比较自动化了一点 ... -
selenium和ajax的测试问题
2007-08-13 15:51 6634Hi,all I am having doubts in se ... -
在selenium测试中使用ActiveRecord
2007-08-10 18:15 5146ActiveRecord是rails的框架,我们在seleni ... -
关于rails应用的验收测试
2007-08-08 18:26 4772ruby的测试运行的本来都慢,selenium的验收测试跑起来 ... -
Exception: Bad file descriptor - connect(2)
2007-08-07 15:59 5496Hi,all I am trying to test web ...
相关推荐
数据结构英文教学课件:chapter4 Stacks and Queues.ppt
2. Introduction to Stacks. 3. Queues. 4. Linked Stacked and Queues. 5. Recursion. 6. Lists and Strings. 7. Searching. 8. Sorting. 9. Tables and Information Retrieval. 10. Binary Trees. 11. ...
Java中的栈(Stack)和队列(Queue)是两种重要的数据结构,它们在程序设计中扮演着关键角色,尤其在处理对象的临时存储和管理数据流时。本篇内容主要探讨了栈和队列的不同实现方式,以及它们的应用场景。...
After an overview of preliminary concepts, this text introduces stacks and queues using arrays along with a discussion of array-based lists. This is followed by an introduction to linked lists and the...
标题和描述中提到的知识点主要涉及数据结构中的表、栈和队列,这些都是计算机科学中基本且重要的概念。下面将详细解释这些概念及其应用。 **表(List ADT)** 表是一种线性数据结构,允许在任何位置进行插入和删除...
How to manipulate and use stacks and queues How to use random numbers to program games, and simulations How to work with files, binary trees, and hash tables Sophisticated sorting methods such as ...
6.Stacks, Queues, and Deques 7.Ordered Lists and Sorted Lists 8.Hashing, Hash Tables, and Scatter Tables 9.Trees 10.Search Trees 11.Heaps and Priority Queues 12.Sets, Multisets, and Partitions 13....
From here, we introduce you to concepts such as arrays, linked lists, as well as abstract data types such as stacks and queues. Next, we’ll take you through the basics of functional programming ...
Linked Lists, Stacks, Queues,Trees, Priority Queue and Heaps, Disjoint Sets ADT, Graph Algorithms, Sorting, Searching, Selection Algorithms [Medians], Symbol Tables, Hashing, String Algorithms, ...
一. 实验目的 本次实验的主要目的是理解和掌握线性数据结构——双端队列(Double-Ended Queue,简称deque)的实现与应用。通过实际编程,加深对双端队列特性的理解,如其在头部和尾部进行插入和删除操作的灵活性。...
9.2. Python Scopes and Namespaces 91 9.2.1. Scopes and Namespaces Example 94 9.3. A First Look at Classes 95 9.3.1. Class Definition Syntax 95 9.3.2. Class Objects 96 9.3.3. Instance Objects 97 9.3.4....
在本章"Chapter4 Lists, Stacks, and Queues"中,我们将深入探讨三种基本的数据结构:列表、栈和队列。 首先,列表是一种有限的、有序的数据元素序列,每个元素都有其特定的数据类型。列表可以为空,其长度表示当前...
3.2 Stacks and Queues . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.3 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.4 Binary Search Trees . . . . . . . . . ....
The content covers an in-depth examination of implementing stacks and queues with practical programming challenges like using a stack to implement a queue, utilizing a queue to implement a stack, ...
Learn how to use the most used data structures such as array, stack, list, tree, and graphs with real-world examples Get a grasp on which one is best between searching and sorting algorithms and learn...
Java, Java, Java, Object-Oriented Problem Solving (3rd Edition) 3rd Edition by Ralph Morelli (Author), Ralph Walde (Author) 1291 pages (December 30, 2016...16. Data Structures: Lists, Stacks, and Queues.
Stacks Without frames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Commands for Examining the Stack . . . . . . . . . . . . . . . . . . . . . Backtraces . . . . . . . . . . . . . ...
数据结构--C语言描述 Chapter03-Stacks-and-Queues英文课件