Data Structure
Stack and Queue
Stack
Definition: Lists with the restriction that insertions
and deletions can be performed in only one position, namely,
the end of the list. Access the list from the top.
- First in, last out (FILO) lists
- Or last in, first out (LIFO) lists.
Basic Concepts
Top: the end of the list, namely, the operation end.
Bottom: the head of the list
Push: Insert an element into the end of the list.
Pop: Delete an element from the end of the list.
$Bottom\rightarrow [a_1] [a_2]……[a_{n-1}] [a_n]\leftarrow Top$
$Operation$
$[a_1] [a_2]……[a_{n-1}] [a_n]^{\rightarrow Pop}_{\leftarrow Push}$
ADT
ADT Stack {
Data Object：D = {ai | ai∈ElementSet, (i=1,2,…,n, n≥1)}
Data Relationship：R = {＜ai-1,ai＞|ai-1,ai ∈ D, (i=2,3,…,n)}
assume an is top, a1 is bottom.
1
2
3
4
5
6
7
8
9
10
|
//Basic Operations:
InitStack(&S) //Create an empty Stack.
DestroyStack(&S) //If S exists, Destroy it.
ClearStack(&S) //If S exists, make the Stack empty.
StackEmpty(S) //if S is empty, return TRUE, otherwise return FALSE.
StackLength(S) //return the length of Stack.
GetTop(S,&e) // If S exists and non-empty, return the top element.
Push(&S,e) // Insert e as the top element.
Pop(&S,&e) // If Stack exists and non-empty, set the top element to e, then delete the top element.
StackTraverse(S,visit()) //visit all of elements in the Stack.
|
}
$!if\ input\ is {…a_i, … a_j, …a_k, …}, then\ the\ output\ is\ impossible {…a_k, …a_i, …a_j, …}$
Stack mixed wash
$if\ the\ stack.size()\ is\ n,then\ the\ size\ of\ Stack\ mixed\ wash\ sp(n)\ is\ Catalan(n)=\frac{(2n)!}{(n + 1)!n!}, and\ sp(n) = \sum_{k=1}^nsp(n - k)*sp(k - 1), base:\ sp(1) = 1$
Array implementation of stacks
1
2
3
4
5
6
7
|
constexpr std::size_t STACK_INIT_SIZE = 100;
constexpr std::size_t STACKINCREMENT = 10;
typedef struct {
SElemType *base; //Bottom pointer
SElemType *top; //Top pointer
int stacksize; //max capacity
} SqStack;
|
Bottom Pointer base,always points to the bottom;
Top pointer, is on the top of the Stack.
When top=M, Stack is full，If run push, then overflow.
When top=base, Stack is empty，If run Pop, then underflow;
Initialize Stack
1
2
3
4
5
6
7
8
9
10
|
Status InitStack (SqStack &S) {// Create an empty Stack
//Allocate memory
S.base=(SElemType*) malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
exit (OVERFLOW); //if allocate failed, then assignment failed.
//initialize top pointer(equal to base)
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;//initialize stack's max capacity
return OK;
}
|
Push an element into the stack:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
Status Push (SqStack &S, SElemType e) {
//Stack Full，Extend space of the stack
if (S.top - S.base >= S.stacksize) {
S.base = (SElemType *) realloc ( S.base,(S.stacksize + STACKINCREMENT) *sizeof (SElemType));
if (!S.base)
exit (OVERFLOW); //Assignment failed.
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
//push the element
*S.top++ = e;
return OK;
}
|
Pop the top of the stack
1
2
3
4
5
6
7
8
|
Status Pop (SqStack &S, SElemType &e) {
// If Stack is Non-empty，let top element to e，then delete
// the top element, return OK, otherwise return ERROR.
if (S.top == S.base)
return ERROR;
e = *--S.top;
return OK;
}
|
Linked List implementation of stacks
structure of node:
1
2
3
4
|
typedef struct Snode {
SElemType data;
struct Snode *next;
} Snode, *LinkStack;
|
Initialize Stack
1
2
3
|
void InitlinkStack(LinkStack &s) {
s = NULL;
} // InitlinkStack
|
memory structure
$top\rightarrow [a_n]\rightarrow [a_{n-1}]\rightarrow……\rightarrow[a_1]\rightarrow null$
push:
1
2
3
4
5
6
7
|
Status Push(LinkStack &s, SElemType e) {
p = (Snode *) malloc(sizeof(Snode));
p->data = e;
p->next = s;
s = p;
return OK;
} // Push;
|
pop:
1
2
3
4
5
6
7
8
|
Status Pop(LinkStack &s, SElemType & e) {
if (!s) return ERROR;
e = s->data;
p = s;
s = s->next;
free(p);
return OK;
} // Pop;
|
Application of Stack
Balancing Symbols
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
void algorithm(const std::string &exp) {
LinkedStack<char> stack{};
std::size_t length = exp.length();
for (std::size_t i = 0; i < length; i++) {
if (exp[i] == '(' || exp[i] == '[')
stack.push(exp[i]);
else if (!stack.empty()) {
if ((exp[i] == ')' && stack.top() == '(') || (exp[i] == ']' && stack.top() == '['))
stack.pop();
else {
std::cout << "Fail!" << std::endl;
return;
}
} else {
std::cout << "Fail!" << std::endl;
return;
}
}
std::cout << (stack.empty() ? "Success!" : "Fail!") << std::endl;
}
|
Conversion
Example: 10->8
1
2
3
4
5
6
7
8
9
10
11
12
|
void algorithm(int Number) {
LinkedStack<int> stack{};
do {
stack.push(Number & 0x07);
Number >>= 3;
} while (Number != 0);
while (!stack.empty())
std::cout << stack.pop();
std::cout << std::endl;
}
|
Evaluate postfix expression
Example:
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
26
27
28
29
|
double evaluate ( char* S, char* RPN ) { //对（已剔除白空格的）表达式S求值，并转换为逆波兰式RPN
Stack<double> opnd; Stack<char> optr; //运算数栈、运算符栈
optr.push ( '\0' ); //尾哨兵'\0'也作为头哨兵首先入栈
while ( !optr.empty() ) { //在运算符栈非空之前，逐个处理表达式中各字符
if ( isdigit ( *S ) ) { //若当前字符为操作数，则
readNumber ( S, opnd ); append ( RPN, opnd.top() ); //读入操作数，并将其接至RPN末尾
} else //若当前字符为运算符，则
switch ( priority ( optr.top(), *S ) ) { //视其与栈顶运算符之间优先级高低分别处理
case '<': //栈顶运算符优先级更低时
optr.push ( *S ); S++; //计算推迟，当前运算符进栈
break;
case '=': //优先级相等（当前运算符为右括号或者尾部哨兵'\0'）时
optr.pop(); S++; //脱括号并接收下一个字符
break;
case '>': { //栈顶运算符优先级更高时，可实施相应的计算，并将结果重新入栈
char op = optr.pop(); append ( RPN, op ); //栈顶运算符出栈并续接至RPN末尾
if ( '!' == op ) //若属于一元运算符
opnd.push ( calcu ( op, opnd.pop() ) ); //则取一个操作数，计算结果入栈
else { //对于其它（二元）运算符
double pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop(); //取出后、前操作数
opnd.push ( calcu ( pOpnd1, op, pOpnd2 ) ); //实施二元计算，结果入栈
}
break;
}
default : exit ( -1 ); //逢语法错误，不做处理直接退出
}//switch
}//while
return opnd.pop(); //弹出并返回最后的计算结果
}
|
infix to postfix
Precedence:
- ‘(’ and ‘)’ have the highest precedence
- ‘*’ and ‘/ ‘have lower precedence than ‘(’ and ‘)’
- ‘+’ and ‘-’ have lower precedence than ‘*’ and ‘/’
Converting infix expressions into postfix
$Infix: [A * B + C * D]$
$Postfix: [A B * C D * +]$
Example:
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
void algorithm(const std::string &string) {
std::array<std::array<bool, 100>, 100> matrix{};
matrix['+']['+'] = true;
matrix['+']['-'] = true;
matrix['+']['*'] = true;
matrix['+']['/'] = true;
matrix['+']['^'] = true;
matrix['-']['+'] = true;
matrix['-']['-'] = true;
matrix['-']['*'] = true;
matrix['-']['/'] = true;
matrix['-']['^'] = true;
matrix['*']['+'] = false;
matrix['*']['-'] = false;
matrix['*']['*'] = true;
matrix['*']['/'] = true;
matrix['*']['^'] = true;
matrix['/']['+'] = false;
matrix['/']['-'] = false;
matrix['/']['*'] = true;
matrix['/']['/'] = true;
matrix['/']['^'] = true;
matrix['^']['+'] = false;
matrix['^']['-'] = false;
matrix['^']['*'] = false;
matrix['^']['/'] = false;
matrix['^']['^'] = false;
std::size_t length = string.length();
LinkedStack<char> linkedStack{};
std::string iteration{};
for (std::size_t i = 0; i < length; i++) {
if (string[i] >= 'A' && string[i] <= 'F')
iteration += string[i];
else {
while (!linkedStack.empty()) {
if (matrix[string[i]][linkedStack.top()])
iteration += linkedStack.pop();
else
break;
}
linkedStack.push(string[i]);
}
std::cout << iteration << std::endl;
}
while (!linkedStack.empty()) {
iteration += linkedStack.pop();
std::cout << iteration << std::endl;
}
}
|
Function Calls
When a function is called
• Local variables and status should be saved
When the function returns
• Saved values needs to be restored
In what order?
Structure:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
void main() {
f();
}
void f() {
g();
h();
}
void g() {
}
void h() {
}
|
$bottom\rightarrow[main()]\rightarrow[f()]\rightarrow[g()]\rightarrow top$
$next:pop\ g(), push\ h()$
$bottom\rightarrow[main()]\rightarrow[f()]\rightarrow[h()]\rightarrow top$
Recursion
Definition: Recursion simply means a function that calls itself directly or indirectly.
Example: Find the last element of a list
1
2
3
4
5
6
|
void Find (LinkList L) {
if(L→next == nullptr)
printf(L→data);
else
Find(L→next);
}
|
The general form of a recursive algorithm
1
2
3
4
5
|
void p (parameters) {
if (stopping condition)
base case that is processed without recursion
else p(smaller parameters); //recursive case
}
|
Step to make a recursive algorithm:
- Find the key step. Begin by asking yourself, “How can this problem be divided into parts?” or “How will the key step in the middle be done?”
- Find a stopping rule. This stopping rule is usually the small,special case that is trivial or easy to handle without recursion.
- Outline your algorithm. Combine the stopping rule and the key step, using an if statement to select between them.
- Check termination. Verify that the recursion will always terminate. Be sure that your algorithm correctly handles extreme cases
Queue
Features
insertions at one end
deletions at another end
FIFO (First In First Out)
Operations
{
Enqueue(element):insert an element at the end of the list(rear)
Dequeue:delete the element at the start of the list (front)
IsEmpty:check whether the queue has an element or not
}
Implementation of Queue
Linked list implementation of queues
keep two pointers the front and the rear
• Front is the head of the linked list
• Rear is the tail of the linked list
Array implementation of queues
keep positions of the front and the rear. When one reaches to the end of the Array, it starts over from the beginning
• Array is used as a circular array
keep track of the size of queue
Linked Queue
1
2
3
4
5
6
7
8
9
|
typedef struct QNode{
QElemType data;
struct QNode *next;
}Qnode, *QueuePtr;
typedef struct {
QueuePtr front; // front pointer
QueuePtr rear; // rear pointer
}LinkQueue;
|
memory structure
$front\rightarrow [head]\rightarrow [X]\rightarrow [Y]^{\rightarrow null}_{\leftarrow rear}$
Initialization of a queue
1
2
3
4
5
6
7
8
|
Status InitQueue(LinkQueue &Q) {
Q.rear = (QueuePtr)malloc(sizeof(QNode));
Q.front = Q.rear;
if(!Q.front)
return(OVERFLOW);
Q.front -> next = NULL;
return OK;
} // InitQueue
|
Destroy a Queue
1
2
3
4
5
6
7
8
|
Status DestroyQueue(LinkQueue &Q) {
while(Q.front ) {
Q.rear = Q.front -> next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
} // DestroyQueue
|
push an element
1
2
3
4
5
6
7
8
9
10
|
Status EnQueue(LinkQueue &Q, QelemType e) {
p = ( QueuePtr )malloc(sizeof(QNode));
if(!p)
return(OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
} // EnQueue
|
pop an element
1
2
3
4
5
6
7
8
9
10
11
|
Status DeQueue(LinkQueue &Q, QelemType &e){
if(Q.front == Q.rear)
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return OK;
} // DeQueue
|
Array Queue
Avoid false overflow
- $move\ element$
- $use\ array\ as\ a\ circle, empty\rightarrow(r - l) == 0, and\ full\rightarrow (rear + 1) % maxlength == front$
Enqueue
Increment QueueSize
Queue [rear] = X
Increment rear
Dequeue
Decrement QueueSize
Increment front
return Queue[front-1]
Application:
Print jobs
Computer networks
OS
Real-life waiting lines