年代tacks

A堆栈is anabstract data typethat places restrictions on where you can add and remove elements. A good analogy is to think of a stack as a堆栈of books; you can remove only the top book, and you can only add a new book on the top. As with any abstract data type, a stack can be implemented with a variety of data structures, such as alinked listor anarray. A stack has a variety of applications such as in reversing the order of elements, evaluating polish strings, etc.

The distinguishing characteristic of a stack is that the addition or removal of items takes place at the same end. This end is commonly referred to as the "top." The end opposite to it is known as the "bottom". The principle by which a stack is ordered is calledLIFO(shorthand forlast-in first-out). In our stack of books, the last book we add to the pilemustbe the one that comes off when we remove a book.

年代ometimes, a stack is implemented to have a maximum capacity. In those cases, if the allocated space for a stack is completely used, then no more elements can be pushed, any attempt to do so will result in an堆栈overflowerror. This is one of the most common errors encountered in the programming world, so much that it inspired the name of the Q&A website堆栈overflow.com. The opposite can also happen, when a pop is attempted when the stack is empty: this results in a堆栈underflowerror.

There are two basic operations related to the stack.

Function Name*	Provided Functionality
push(i)	Insert elementiat the top of the stack.
pop()	Remove the element at the top of the stack.

年代tacks are often implemented with the following functions.

Function Name*	Provided Functionality
size()	returns the current size of the stack.
peek()	returns the element at the top of the stackwithout changing the stack

*Exact names are not required. In fact, some functionality may be provided by a given language directly via special syntax.

年代tack Questions

Consider a stack of boxes numbered from zero to ten, arranged in ascending order one above the other such that the number ten is on top.

1. 我们如何把盒子11到这个堆栈?

2. How do we pop a box from this stack?

3. If the room has height only enough for exactly eleven boxes, what happens when we try pushing a twelfth one?

4. What happens if we pop all of the boxes from the stack and then try to pop a box from the stack?

A1. The box 11 is placed above box 10.

A2. The topmost box (box 10) is removed.

A3. Since there is no more space, this is similar to a stack overflow error.

A4. Since we have no boxes left in the stack, this is similar to stack underflow error.

A stack and its operations are usually visualized as a stack of cards or books. Consider the empty stack below.

Pushessentially stacks a given item with a specific value on top of the stack. For example if the block below was run,

1 2 3

push(6) push(789) push(0)

the resulting stack would look like the following:

pop通过反向工作,踢出element of the stack. For our stack above, executing the block of operations would make it look like

1 2 3

pop() pop() pop()

What will an empty stack look like after the block of operations below is executed?

1 2 3

push(6)push(5)push(pop()*2)

---

The answer isD. The last line just takes out the last element, doubles it and puts it back in. \(_\square\)

What will an empty stack look like after the block of operations below is executed on it?

1 2 3 4 5

push(5)push(3)push(7)push(pop()+1)peek()

---

The stack will look like the following:

1 2 3 4

(5) (5,3) (5,3,7) (5,3,8)

Thus \(8\) will be outputted. \(_\square\)

To implement a stack data structure we usually need:

• an area of memory to store the data items
• a pointer to the top of the stack
• a set of well defined operations :push,pop,peekandsize

In this implementation, the top of the stack is on the right of the array.

Note: Stacks are already implemented for you in Python, as you can seebelow. This is a re-implementation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

class年代tack:self.array=[]self.size=0def__init__(self,array=None):ifarray!=None:self.array=arrayself.size=len(array)else:self.array=[]self.size=0defpush(self,item):self.array.append(item)defpop(self):deleted=self.array[-1]self.array=self.array[0:-1]returndeleteddefpeek(self):returnself.array[-1]defsize(self):returnself.size

Now that we have fully described the behavior of the stack ADT, we can implement it easily, as shown above. Even though there are several ways of implementing the stack ADT, here we will use an array based implementation. Because we will use python, we do not have to re-size our lists because they are dynamically re-sizable. Our implementation will be straightforward and new items will be added and deleted to the end of the list.

Write a method that reverses the contents of a stack

年代olution

If the method is not instance method of the stack ADT we can writereverseas

1 2 3 4 5

defreverse(堆栈):new_stack=年代tack()while堆栈.size()!=0:new_stack.push(堆栈.pop())returnnew_stack

Lists in Python already have theappendandpopmethods which let them be used as stacks.

Using a list as stack

1	>>>mystack=[]

Right now the stack is empty let's fill it up with some elements.

1 2 3 4 5 6

>>>myStack.append(1)>>>myStack.append(2)>>>myStack.append(3)>>>myStack[1,2,3]

Now let's do the second important operation with it, that is to get an element out of it.

1 2 3 4 5

>>>myStack.pop()3>>>myStack.pop()2

As expected its behaving like a stack and that's all we need from this data-type. You might be discouraged at how limited things it can do but you will thrilled at its power when you try to solve more sophisticated problems. You might be impressed how using stack can simplify things.

Let's have little more fun.

1 2 3 4 5 6 7

>>>myStack.append(7)>>>myStack.append(8)>>>myStack[1,7,8]>>>myStack.pop()8

The time complexity of stacks depends on the type of the data structure you are using and the specific implementation you build. Below is a description of how linked lists and arrays are not that different when it comes to complexity:

A stack, unlike aqueue, only performs an operation atone end of the list. This invariant makes the process much easier. In our book pile, adding a book was very easy since we already knew where the top was. Likewise, removing the topmost book is equally easy since we know where it is. No need to go through the rest of the pile because all of our operations happen at one point.