Data Structures
Array Stack
A stack stores new values at the top and removes the newest value first.
top index
The `top` index points one past the newest value in the stack.
last in first out
Decrementing `top` before reading removes the most recently pushed value.
Array Stack
array_stack.c
Replay: real traced execution (multi-file project)
#include <stdio.h>
int main(void) {
int limit = 3;
int stack[4] = {0, 0, 0, 0};
int top = 0;
for (int i = 0; i < limit; i++) {
stack[top] = i + 1;
top = top + 1;
}
top = top - 1;
int popped = stack[top];
printf("top=%d popped=%d\n", top, popped);
return 0;
}
#include <stdio.h>
int main(void) {
int limit = 2;
int stack[4] = {0, 0, 0, 0};
int top = 0;
for (int i = 0; i < limit; i++) {
stack[top] = i + 1;
top = top + 1;
}
top = top - 1;
int popped = stack[top];
printf("top=%d popped=%d\n", top, popped);
return 0;
}
#include <stdio.h>
int main(void) {
int limit = 4;
int stack[4] = {0, 0, 0, 0};
int top = 0;
for (int i = 0; i < limit; i++) {
stack[top] = i + 1;
top = top + 1;
}
top = top - 1;
int popped = stack[top];
printf("top=%d popped=%d\n", top, popped);
return 0;
}
limit ← 3, stack ← ⟨addr A⟩, top ← 0
3int main(void) {4 int limit→ 3 = 3; //@limit=2, 45 int stack→ ⟨addr A⟩[4] = {0, 0, 0, 0};6 int top→ 0 = 0;stack[top] ← 1, top ← 1
pass 1 of 38for (int i0 = 0; i < limit3; i++) {9 stack[top]→ 1 = i0 + 1;10 top→ 1 = top + 1;11}All 3 passes — pass 1 is the card above pass istack[top]top1 0 0 → 1 0 → 1 2 1 0 → 2 1 → 2 3 2 0 → 3 2 → 3 top ← 2, popped ← 3
13 top→ 2 = top - 1;14 int popped→ 3 = stack[top]3;1516 printf("top=%d popped=%d\n", top2, popped3);17 return 0;18}outputtop=2 popped=3
limit ← 2, stack ← ⟨addr A⟩, top ← 0
3int main(void) {4 int limit→ 2 = 2;5 int stack→ ⟨addr A⟩[4] = {0, 0, 0, 0};6 int top→ 0 = 0;stack[top] ← 1, top ← 1
pass 1 of 28for (int i0 = 0; i < limit2; i++) {9 stack[top]→ 1 = i0 + 1;10 top→ 1 = top + 1;11}stack[top] ← 2, top ← 2
pass 2 of 28for (int i1 = 0; i < limit2; i++) {9 stack[top]→ 2 = i1 + 1;10 top→ 2 = top + 1;11}top ← 1, popped ← 2
13 top→ 1 = top - 1;14 int popped→ 2 = stack[top]2;1516 printf("top=%d popped=%d\n", top1, popped2);17 return 0;18}outputtop=1 popped=2
limit ← 4, stack ← ⟨addr A⟩, top ← 0
3int main(void) {4 int limit→ 4 = 4;5 int stack→ ⟨addr A⟩[4] = {0, 0, 0, 0};6 int top→ 0 = 0;stack[top] ← 1, top ← 1
pass 1 of 48for (int i0 = 0; i < limit4; i++) {9 stack[top]→ 1 = i0 + 1;10 top→ 1 = top + 1;11}All 4 passes — pass 1 is the card above pass istack[top]top1 0 0 → 1 0 → 1 2 1 0 → 2 1 → 2 3 2 0 → 3 2 → 3 4 3 0 → 4 3 → 4 top ← 3, popped ← 4
13 top→ 3 = top - 1;14 int popped→ 4 = stack[top]4;1516 printf("top=%d popped=%d\n", top3, popped4);17 return 0;18}outputtop=3 popped=4