Computer Science Fundamentals

Stacks

In many areas of computer science, it is useful to store a bunch of data, and then access the data in the opposite order with which it was stored, i.e. "last-In, first-out", or LIFO.

For example, when writing a text document or drawing a picture (using your favorite text or picture editing software), it is useful to be able keep track of the last few commands you performed. That way you can back out of a mistake (or mistakes) and “undo” them.

For these types of applications, a stack provides a very useful mechanism for storing the data.

A stack is an abstract data type that places restrictions on where you can add and remove elements. A good analogy is to think of a stack as a stack 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 a linked list or an array. A stack has a variety of applications such as

  • reversing the order of elements
  • undo mechanisms (e.g. undoing the last few actions)
  • evaluating reverse polish notations.

Stacks

Stacks and Queues

                     

Stacks

When you have a stack, like a stack of books, the two obvious things you can do are to add a book to the top or remove a book and read it.

In computer terms, these two functions are called “push” for “pushing” elements onto a stack and “pop” for popping an element off the stack.

A computer stack is similar to a stack of books in that it is simply a set of data that is in memory. You can add an element to the top of the stack using the push commands, and access the top element using the pop command (which also removes the top element from the stack).

If you push beyond the allocated space for the stack you get a “stack overflow” error, and if you pop when the stack is empty, you get a “stack underflow” error. The latter is less common since you usually would check whether there is anything on the stack before you try to pop anything off of it.

Stacks

Stacks and Queues

                     

Stacks

Let's define the operations “pop” and “push”:

  • push(n)--adds the number n to the top of a stack
  • pop()--pops the top element off a stack and returns the value of the element.

If you start with an empty stack, what will the stack look like after the following operations have been applied?

1
2
3
4
5
6
 push(7)
 push(8)
 pop()
 push(pop()*3)
 push(40)
 push(pop()/2)  

Stacks

Stacks and Queues

                     

Stacks

What will be the result of this series of operations applied to an empty stack?

1
2
3
4
5
push(1)
push(pop()*2)
push(pop()+1)
pop()
pop() 

Stacks

Stacks and Queues

                     

Stacks

At any particular time, it is useful to find out how many elements are in a stack. As we saw in the previous example, if you try to pop something off an empty stack, you get the rather unfortunate “stack underflow error.” With a count, you can know if there are enough elements to complete an operation or set of operations.

The size command helps us out here. It tells us the size of the stack, that is, the number of elements it contains.

Stacks

Stacks and Queues

                     

Stacks

Currently, with just the pop() and push() commands, we can access the element on the top of the stack and store it in the variable “Value” by saying

Value = pop().

However, this command pops the data off of the stack. But what if we don’t want to pop it off of the stack?

Then we would need to add the command

push(Value).

However, it is awkward to do both of these commands just to take a look at the top value. For this reason the “peek” command is added to our arsenal of commands for working with stacks.

Peek returns the value of the top element of the stack without changing the stack.

Stacks

Stacks and Queues

                     

Stacks

What will be the output of the following?

1
2
3
4
5
6
push(7)
push(8)
push(pop()*3)
push(9)
pop()
peek() 

Stacks

Stacks and Queues

                     

Stacks

Let's assume that we have a standard implementation of a stack in Python, so that

  • s.push(i) pushes i onto the top of the stack;
  • s.pop() pops the top element of the stack and returns that element.

Here is a piece of code using this stack implementation:

1
2
3
4
5
6
7
8
s = Stack()
s.push('Hello')
s.push('there,')
s.push('how')
s.push('are')
s.push('you?')
print(s.pop())
print(s.pop())

What will it print out?

A)

1
2
3
4
5
Hello
there,
how 
are 
you?

B)

1
2
you?
are

C)

1
2
are 
you?

D)

1
2
Hello 
there,

Stacks

Stacks and Queues

                     

Stacks

In a stack \(s\), TIM is equivalent to s.push(s.pop() * s.pop()) and SUM is equivalent to s.push(s.pop() + s.pop()). What will the following stack machine evaluate the operations as?

1
2
3
4
5
6
7
8
9
PUSH 1   
PUSH 2   
PUSH 3   
PUSH 4   
PUSH 5   
SUM   
TIM   
SUM   
TIM   

Stacks

Stacks and Queues

                     

Stacks

A chef wants to fix his pancakes so that they are all burnt side down. To do so, he can only use the flip operation on his stack of pancakes, i.e., he inserts his spatula at some point in between the stack of the pancakes and flips the ones above the spatula, like this:

The chef, being cunning, will make sure that he'll fix any stack of pancakes in the least number of flips he can.

For which one of these three stacks of pancakes would he require the most number of flips?

Stacks

Stacks and Queues

                     

Stacks

Suppose Walt Disney decides to model a line at Disneyland as a stack. He would like the top of the stack to represent the end of the line, and the bottom of the stack to represent the front of the line.

So, if someone new stands in line, he adds them to the top of the stack. When someone gets on the ride, he will need to somehow remove them from the bottom of the stack rather than the top.

If he has 500 people waiting in line, how many operations on the stack will be required in order to model the line's first inhabitant getting on the ride?

Stacks

Stacks and Queues

                     
×

Problem Loading...

Note Loading...

Set Loading...