To simulate stack storage in a C program, you need to emulate the four basic parts of a stack:<\/p>\n
Further, you need to implement controls that prevent a stack overflow or underflow. And you can get real fancy, but those four items are the basics.
\n
\nIn my code, I assign an array as stack storage. Unlike a processor stack, which is just a chunk of memory, in C an array must be typed, such as an integer array. The stack pointer variable must match the array type. And you don’t need to use a pointer; you could use an index into the array, but I’m using a pointer because, well, it’s called a stack “pointer,” isn’t it?<\/p>\n
The two functions are traditionally named push()<\/em> and pop()<\/em>. The push()<\/em> function requires an argument, the value to push onto the stack. The pop()<\/em> function returns a value.<\/p>\n It’s easiest to code the stack emulation with the stack array and pointer as global variables. Otherwise, the stack array and pointer are required as arguments for both push()<\/em> and pop()<\/em> functions. For simplicity’s sake, I use global variables in my examples.<\/p>\n Here is how I’d declare the stack array and stack pointer as global variables:<\/p>\n Array The push()<\/em> function sends a value to the top of the stack. Further, it tests to ensure that a stack overflow doesn’t occur:<\/p>\n In this function, value The else<\/em> statements in the push()<\/em> function increment the In the push()<\/em> function, variable To fetch a value from the stack, the pop()<\/em> function is used. It requires no arguments in my example, because the The value at the top of the stack is saved in variable Without variable Both if<\/em> and else<\/em> need return<\/em> statements because the pop()<\/em> is an int<\/em> function. I return 0 on the stack empty condition, though in a real program you might just use exit()<\/em>; it’s dangerous to assume that 0 would be on the stack when the stack is empty.<\/p>\n The In next week’s Lesson<\/a>, I demonstrate how to use these four elements in a program to simulate stack storage.<\/p>\n","protected":false},"excerpt":{"rendered":" To simulate stack storage, your code needs four items. Continue reading \r\n#define STACK_SIZE 16\r\n\r\nint stack[STACK_SIZE];\r\nint *sp;<\/pre>\n
stack[]<\/code> represents 16 int<\/em> values. Integer pointer variable *sp<\/code> references the “top” of the stack.<\/p>\n\r\nvoid push(int v)\r\n{\r\n if(sp == stack+STACK_SIZE)\r\n {\r\n puts(\"Stack Overflow\");\r\n }\r\n else\r\n {\r\n sp++;\r\n *sp = v;\r\n }\r\n}<\/pre>\nv<\/code> is pushed to the top of the stack. Before that, however, an if<\/em> statement tests to ensure that the stack isn’t full. If so, the Stack Overflow message is displayed and the function returns. In the real world, the program would terminate at this point; memory overflows are serious business. In fact, you may have already coded programs that crash with a “Stack Overflow” message (especially when you do recursion).<\/p>\nsp<\/code> (stack pointer) variable and set value v<\/code> to that memory location.<\/p>\nsp<\/code> always points at the top the stack. It does not point to the location of the next value. This is exactly how the esp<\/code> register works in the processor.<\/p>\nstack[]<\/code> array and sp<\/code> pointer are global:<\/p>\n\r\nint pop(void)\r\n{\r\n int s;\r\n\r\n s = *sp;\r\n if( sp == stack)\r\n {\r\n puts(\"Stack Empty\");\r\n }\r\n else\r\n {\r\n sp--;\r\n }\r\n return(s);\r\n}<\/pre>\ns<\/code>. (It doesn’t have to be, but I wrote the function to be more readable.) The if<\/em> comparison confirms whether the stack isn’t empty. If it is, an underflow message is displayed and the function returns. Otherwise, the sp<\/code> variable is decremented and the value saved in variable s<\/code> is returned.<\/p>\ns<\/code>, the pop()<\/em> function looks like this:<\/p>\n\r\nint pop(void)\r\n{\r\n if( sp == stack)\r\n {\r\n puts(\"Stack Empty\");\r\n return(0);\r\n }\r\n else\r\n {\r\n return(*sp--);\r\n }\r\n}<\/pre>\n*sp--<\/code> thing in the second return<\/em> statement first fetches the value from the stack, then it decrements the sp<\/code> pointer.<\/p>\n