PowerPoint Presentation
Data Structures: A Pseudocode Approach with C
1
2
Last In First Out data structure.
Restricted linear list:
Insert/Delete are restricted to one end called top.
3
Last In First Out data structure.
Restricted linear list:
Insert/Delete are restricted to one end called top.
4
top
base
Last In First Out data structure.
Restricted linear list:
Insert/Delete are restricted to one end called top.
5
top
base
Last In First Out data structure.
Restricted linear list:
Insert/Delete are restricted to one end called top.
6
top
base
Last In First Out data structure.
Restricted linear list:
Insert/Delete are restricted to one end called top.
7
top
base
Last In First Out data structure.
Restricted linear list:
Insert/Delete are restricted to one end called top.
8
top
base
Last In First Out data structure.
Restricted linear list:
Insert/Delete are restricted to one end called top.
9
top
base
Last In First Out data structure.
Restricted linear list:
Insert/Delete are restricted to one end called top.
10
11
Basic Stack Operations
3.1 Basic Stack Operations
The stack concept is introduced and three basic stack operations are discussed.
3.2 Stack Linked List Implementation
In this section we present a linked-list design for a stack. After developing the data structures, we write pseudocode algorithms for the stack ADT.
3.3 C Language Implementations
This section presents a simple non-ADT implementation of a stack. We develop a simple program that inserts random characters into the stack and then prints them.
3.4 Stack ADT
We begin the discussion of the stack ADT with a discussion of the stack structure and its application interface. We then develop the required functions.
3.5 Stack Applications
Three basic application problems-parsing, postponement, and backtracking-are discussed and sample programs developed. In addition, several other stack applications are presented, including the classic Eight Queens problem.
3.6 How Recursion Works
This section discusses the concept of the stack frame and the use of stacks in writing recursive software
The stack concept is introduced and three basic stack operations are discussed.
Push
Pop
Stack Top
12
Memory
Executable program
Global
Variables
Local
variables
Parameters
Static
allocation
of memory
Dynamic
allocation
of memory
Data
Stack
Heap
13
main
funA
funB
funC
Computer Stack
14
m
main
funA
funB
funC
Computer Stack
15
m
A
main
funA
funB
funC
Computer Stack
16
m
A
C
main
funA
funB
funC
Computer Stack
17
m
A
main
funA
funB
funC
Computer Stack
18
m
main
funA
funB
funC
Computer Stack
19
m
B
main
funA
funB
funC
Computer Stack
20
m
main
funA
funB
funC
Computer Stack
21
main
funA
funB
funC
Computer Stack
22
m
m
m
m
A
m
A
C
m
A
m
B
main
funA
funB
funC
Computer Stack
23
Array
Stack Implementations
Linked List
24
Array Implementation of Stack
10
30
20
0
2
3
1
4
5
6
7
8
9
stack
25
top
10
30
20
0
2
3
1
4
5
6
7
8
9
stack
Array Implementation of Stack
26
Push 40
top
10
30
20
stack
0
2
3
1
4
5
6
7
8
9
Array Implementation of Stack
27
top
10
30
20
40
0
2
3
1
4
5
6
7
8
9
stack
Array Implementation of Stack
28
Push 25
top
10
30
20
40
stack
0
2
3
1
4
5
6
7
8
9
Array Implementation of Stack
29
Push 25
top
10
30
20
40
stack
top = top + 1
0
2
3
1
4
5
6
7
8
9
Array Implementation of Stack
30
Push 25
top
10
30
20
40
25
stack
top = top + 1
stack[top] = dataIn
0
2
3
1
4
5
6
7
8
9
Array Implementation of Stack
31
top
10
30
20
40
25
stack
if ( top < last )
top = top + 1
stack[top] = dataIn
else
stack is in OVERFLOW state
0
2
3
1
4
5
6
7
8
9
Array Implementation of Stack
32
top
10
30
20
40
25
Pop
stack
if ( top >= first )
dataOut = stack[top]
top = top – 1
else
stack is in UNDERFLOW state
end if
0
2
3
1
4
5
6
7
8
9
Array Implementation of Stack
33
top
10
30
20
40
stack
0
2
3
1
4
5
6
7
8
9
Array Implementation of Stack
Data Structures: A Pseudocode Approach with C
34
Data Structures: A Pseudocode Approach with C
35
Data Structures: A Pseudocode Approach with C
36
Data Structures: A Pseudocode Approach with C
37
Data Structures: A Pseudocode Approach with C
38
Data Structures: A Pseudocode Approach with C
39
Data Structures: A Pseudocode Approach with C
40
Data Structures: A Pseudocode Approach with C
41
Data Structures: A Pseudocode Approach with C
42
Data Structures: A Pseudocode Approach with C
43
Data Structures: A Pseudocode Approach with C
44
45
algorithm push( stack, data )
Insert (push) one item into the stack
Pre : stack – pointer to the stack head structure (passed by value)
data – contains data to be inserted into the stack (passed by value)
Post: data – have been pushed into the stack
Return: 1 if successful, 0 if memory overflow
end push
top
count
2
stack
9
8
PUSH
46
algorithm push( stack, data )
Insert (push) one item into the stack
Pre : stack – pointer to the stack head structure (passed by value)
data – contains data to be inserted into the stack (passed by value)
Post: data – have been pushed into the stack
Return: 1 if successful, 0 if memory overflow
success = false
return success
end push
top
count
2
stack
9
8
PUSH
47
algorithm push( stack, data )
Insert (push) one item into the stack
Pre : stack – pointer to the stack head structure (passed by value)
data – contains data to be inserted into the stack (passed by value)
Post: data – have been pushed into the stack
Return: 1 if successful, 0 if memory overflow
success = false
allocate( newPtr )
if( stack not full )
return success
end push
top
count
2
stack
9
8
PUSH
48
7
algorithm push( stack, data )
Insert (push) one item into the stack
Pre : stack – pointer to the stack head structure (passed by value)
data – contains data to be inserted into the stack (passed by value)
Post: data – have been pushed into the stack
Return: 1 if successful, 0 if memory overflow
success = false
allocate( newPtr )
if( stack not full )
newPtr->data = data
return success
end push
top
count
2
stack
9
8
PUSH
49
algorithm push( stack, data )
Insert (push) one item into the stack
Pre : stack – pointer to the stack head structure (passed by value)
data – contains data to be inserted into the stack (passed by value)
Post: data – have been pushed into the stack
Return: 1 if successful, 0 if memory overflow
success = false
allocate( newPtr )
if( stack not full )
newPtr->data = data
newPtr->next = stack->top
return success
end push
top
count
2
stack
9
8
7
PUSH
50
algorithm push( stack, data )
Insert (push) one item into the stack
Pre : stack – pointer to the stack head structure (passed by value)
data – contains data to be inserted into the stack (passed by value)
Post: data – have been pushed into the stack
Return: 1 if successful, 0 if memory overflow
success = false
allocate( newPtr )
if( stack not full )
newPtr->data = data
newPtr->next = stack->top
stack->top = newPtr
return success
end push
7
top
count
2
stack
9
8
PUSH
51
7
top
count
3
stack
9
8
algorithm push( stack, data )
Insert (push) one item into the stack
Pre : stack – pointer to the stack head structure (passed by value)
data – contains data to be inserted into the stack (passed by value)
Post: data – have been pushed into the stack
Return: 1 if successful, 0 if memory overflow
success = false
allocate( newPtr )
if( stack not full )
newPtr->data = data
newPtr->next = stack->top
stack->top = newPtr
stack->count = stack->count + 1
success = true
end if
return success
end push
PUSH
52
/* Insert one item into the stack
Pre : stack – pointer to the stack head structure
data – contains data to be inserted into the stack
Post: data – have been pushed into the stack
Return: 1 if successful, 0 if memory overflow
*/
int push( STACK *stack, int data )
{
NODE *newPtr;
int success = 0;
newPtr = (NODE *)malloc(sizeof(NODE));
if( newPtr != NULL )
{
success = 1;
newPtr->data = data;
newPtr->next = stack->top;
stack->top = newPtr;
stack->count++;
}
return success;
}
PUSH
7
top
count
3
stack
9
8
53
Stack Operations
1. Create stack
2. Push
3. Pop
4. Stack top
5. Empty stack
6. Full stack
7. Stack count
8. Destroy stack
54
Stack Operations
1. Create stack
2. Push
3. Pop
4. Stack top
5. Empty stack
6. Full stack
7. Stack count
8. Destroy stack
Basic stack operations (3):
55
Stack Operations
1. Create stack
2. Push
3. Pop
4. Stack top
5. Empty stack
6. Full stack
7. Stack count
8. Destroy stack
Basic Stack Operations
56
Stack Operations
1. Create stack
2. Push
3. Pop
4. Stack top
5. Empty stack
6. Full stack
7. Stack count
8. Destroy stack
Most often used stack operations (4):
57
Stack Operations
1. Create stack
2. Push
3. Pop
4. Stack top
5. Empty stack
6. Full stack
7. Stack count
8. Destroy stack
Most Often Used Stack Operations
58
Stack Operations
1. Create stack
2. Push
3. Pop
4. Stack top
5. Empty stack
6. Full stack
7. Stack count
8. Destroy stack
Why do we need “Empty stack”, “Full stack”, and
“Stack count”?
Data Structures: A Pseudocode Approach with C
59
60
createStack
pushStack
popStack
main
insertData
printData
A Simple Non-ADT Implementation of a Stack
Data Type: float
stack_demo_1_build_print_stack
Data Structures: A Pseudocode Approach with C
61
62
Stack ADT
top
count
3
stack
20
30
10
top
count
3
stack
20
30
10
63
Stack ADT
top
count
3
stack
20
30
10
64
top
count
3
stack
John
Alexander
Veronica
Stack ADT
/docProps/thumbnail.wmf