Hello, everyone.
Today we are going to learn Chapter 3,
Stack and Queue. Let's start with stack.
Stack is a restricted data structure that
its operations are limited to one side. And there is another restricted data structure, called Queue.
Its insert operation is limited to one side, and delete operation is limited to the other side. Let's talk about it in the next video.
In theory, stack is
a Last In First Out (LIFO) data structure.
Its main operations are push and pop.
Stack is applied widely in many problems, such as
expression evaluation, function calling in compilation,
and dealing with recursion.
Also for more complex data structures, such as
Tree and Graph, we can use stack to implement Depth-first Search.
The ADT of stack consists of
the two operations mentioned above, insert and delete,
and another operation, top (reading the top element).
Let's look at an example of Railway Station.
There are n trains, labeled 1 to n, arriving at the station (a stack) in order.
Then, what are the legal orders in which they depart? Obviously, the order 1-2-3-4-5 is, so is 5-4-3-2-1.
Let's consider, is the order 3-4-1-2 legal?
We may use the method of formulation.
If 3 needs to be popped firstly,
1 and 2 should be pushed in advance.
Then we push 4 and pop it.
Now we are trying to pop 1,
but 1 is under 2 in the stack. We cannot pop 1 before 2 in such a LIFO structure.
So, 3-4-1-2 is an illegal order.
Think about a question. If the arriving order is 1-2-3-4, what can the departing order be?
Actually, through considering this question,
you can summarize the rule of pop order.
If we push 1 to n in order,
the pop order is a permutation, p1 to pn.
As we know, an arbitrary permutation may be illegal.
Then, we consider that there are subscript i, j and k,
so that i is less than j and j is less than k.
Under this assumption, is it possible that pj is less than pk and pk is less than pi?
For example, the push order is 1-2-3,
can the pop order be 3-1-2? (i = 1, j = 2, k = 3, pi = 3, pj = 1, pk = 2)
OK. Let's see the implementation of the stack. Obviously, there are two types of stack,
sequential stack and linked stack. For sequential stack, we shall notice the problems of overflow and underflow.
Let's see the definition of sequential stack.
In a sequential stack, we use an array to store the elements of the stack.
In addition, there is a pointer pointing to the top of stack.
A sequential stack needs a preallocation of memory, so there is a integer to indicate the maximal memory size of the stack.
Now I am showing a sequential stack.
The top of the stack changes with the elements. If we add elements,
the top of stack goes up, while the bottom of stack remains.
We have talked about overflow and underflow of sequential stack before.
For some operations, such as push and pop,
we should pay attention to the problems of overflow and underflow.
For example, before we execute a operation of push, we should judge whether the stack is full.
If it is full, an stack overflow comes out. Otherwise, we add the new element to the stack and update the top-pointer.
When we execute an operation of pop, we should judge whether underflow occurs.
If not, we read the element in the top of stack,
and update the top-pointer.
For linked stack, we usually apply single linked list.
We start to build the single linked list with the top of stack linking downwards. Notice the form of linking.
It is convenient to execute operations. When push, we link the new element to the top.
When pop, we delete the element in the top and update the top-pointer.
Look at this.
The definition of linked stack, in practise, the process of constitution.
When we begin, it is linked stack with empty top end its size is 0.
The value of size may be useful for some application
which need to know how many elements in the stack. Otherwise, it is corresponding to sequential stack.
We mainly understand this is valid value of element in stack.
Look at this, for linked stack, its push operation.
Because we call a new link, namely creating a new node,
such an operation. When creating the new node, the item
stores this value. Then the top position stores the previous top element. We can see
this link itself makes the new node's
nextV point to the top we passed in.
This is parameter, so it is linked. Then, the size of stack adds one.
Top is updated.
To pop an element from linked stack, we
read the top element and store it in an temporary variable,
then let top pointer point to the second element.
In other words, we have popped the top element.
Sequential and linked stack are both
efficient in time. It costs constant time for the operations of them.
They are low-level functions that support many high-level operations, so they must be efficient in time.
For space efficiency, because the size of linked stack is changeable,
it causes more structural expenses when maintain pointers.
For sequential stack, its size is determinate,
because it is implemented by array. So in practise,
we use sequential stack in most time.
Note that, in general, stack only has restricted operations,
such as inserting and deleting.
But sometimes you need to read element, we can only read the top element.
Note that, don't read elements other than the top element, because of encapsulation.
Think about stack implementation in STL, we can see
two functions, top and pop.
Why are they separated? We usually read the top element
and pop it at the same time.
Why don't we define a ptop function that realises reading and popping?
The stack is used
for its feature of FILO (First In Last Out).
With the same concern, we usually use it to
handle recursive-structured data. It is used widely in depth-first search.
In addition, as we mentioned, in the field of compile, for subprogram to solve functions. We will talk about expression evaluation in this section, especially postfix expression.
We'll talk about replacing recursion with stack.
This infix expression is frequently used when we calculate an expression's value.
The four operations. Postfix expressions put operators in the end.
When we meet one operator,
we choose the previous two operands to calculate.
The result takes the place of these operands and operator and continue calculating.
The infix expression is the arithmetic
that we learnt in primary school.
It use brackets to change the priority of calculations.
When it refers to binary trees which we will learn later,
an infix expression is the same as an inorder traversal. When we want to make priorities,
we should use brackets. We won't investigate it here.
To define the prefix expression by Backus Normal Form (BNF),
it's a recursion in essence.
We can express it by graphical representation. It's the expanded recursion
which is composed of terms and factors.
Postfix expressions' operators
are behind the operands.
So we can calculate the results by scanning only once
and without brackets.
Hence, it's very convenient.
Actually, Suffix expression is a postorder traversal
of expression binary tree.
Furthermore, we needn't think about brackets.
Grammar diagram and grammar formula set
of expression binary tree are in the chart we saw just now.
What about calculation of expression? Let's look about postfix expression.
What are the calculation features of it? Then, what are the differences among them? The occurrence order of operation numbers are the same.
The main difference is the occurrence order of operators.
Let's deal with such an expression.
When we meet an operation number, we push it directly.
When meet operator, we pop two numbers to calculate.
We repeat such a process, until
the final value of the expression is worked out.
The process of evaluating postfix expression,
we can conclude, actually, the algorithm idea is like that, we have introduced above.
When meet operation number, push it. When meet operator, pop two numbers to calculate and push the result.
Repeat that until the value of expression is worked out.
Let us see,
the postfix expression, if we design a counter for it,
then our main operations, as I mentioned just now, are reading the data at first. If it is a valid expression.
If we read data from stack, we should pop two in the same time.
Then comes the calculation. When meet operator, we read the data to calculate, then put result back to stack.
Let us look at the process of calculation.
Reading operation numbers is very easy, but we should note that
which one is left operation number and the other is right operation number.
Remember that the latter one is left operation number, and the former one is right.
Then, our process of calculation is to work out the value, that is, if we meet
an operator, we pop two elements. Then plus, minus, multiply, or divide,
according to the operator.
When we calculate, note that dividing zero is a special case to be handled.
In fact, the whole process of calculating expression is that
we read the values in standard input one by one.
We uniformly read them into a char variable.
If we meet sign of equality, calculating ends.
Otherwise, we examine whether the char is an operator.
If it is operator, we pop two numbers from stack,
then calculate. After that,
we put it back.
If it is not an operator, it must be a number.
In the case of number, because another number has been read, note that
put the former read number back. The complete number will be read next time.
Otherwise, the former number would be eaten, so you get a wrong number.
Finally, we leave some thinking questions.
Stack is usually implemented by single linked list.
Can we use double linked list to implemented it? Which one is better?
Another question is about the example we mentioned just now.
Relative to postfix expression, we can also have prefix expression.
You can study on prefix expressions to find their features and the process of calculation.
Thank you!