codescracker


c

C Stack



« Previous Tutorial Next Tutorial »


A stack is just the opposite of a queue. Since Stack uses last-in, first-out accessing, that is also known as LIFO.

To visualize a stack, just imagine a stack of plates. The first plate on the table is the last to be used, and the last plate placed on the stack is the first to be used. Stacks are used frequently in system software, including compilers and interpreters.

When working with stacks, the two basic operations i.e., store and review are traditionally called as push and pop respectively. Therefore, to implement a stack, you need two functions (one responsible for storing and the other one responsible for reviewing) i.e., the push() function (places a value on the stack) and the pop() function (retrieves a value from the stack). You also need a region of memory to use as stack. You can use an array for this purpose or allocate a region of memory using dynamic allocation functions of C. As with the queue, the retrieval function takes a value off the list and destroys it if it is not stored elsewhere. The general form of push() and pop() that use an integer array follow. You can maintain the stacks of other data types by changing the base type of array on which the push() and the pop() function operate.

push() and pop() general form

Here is the general form of the functions push() and pop().

int stack[MAX];
int top = 0;

void push(int i)
{
	if(top>=MAX)
	{
		printf("Stack Overflow..!!\n");
		return;
	}
	stack[top] = i;
	top++;
}
int pop(void)
{
	top--;
	if(top<0)
	{
		printf("Stack Underflow..!!\n");
		return 0;
	}
	return stack[top];
}

Here, the variable top is the index of the top of stack. When implementing these functions, you must remember to prevent the overflow and underflow of stack. In these routines, an empty stack is signalled by top being zero and a full stack by top being greater than last storage location.

Working of Stack

Here this table shows that how a stack works:

Action Stack Contents
push(A) A
push(B) B A
push(C) C B A
pop() retrieves C B A
push(F) F B A
pop() retrieves F B A
pop() retrieves B A
pop() retrieves A empty

Above table shows the stack in action. i.e., how stack works.

C Stack Example

Here is a four-function calculator shows how the stack works.

/* C Stack - Example Program
 * This is a simple four-function calculator
 */

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>

#define MAX 100

int *p;       // point to a region of free memory
int *top;     // points to top of stack
int *bot;     // points to bottom of stack

void push(int);
int pop(void);

void main()
{
	int x, y;
	char str[80];

	p = (int *) malloc(MAX*sizeof(int));   // get stack memory
	if(!p)
	{
		printf("Allocation Failure..!!\n");
		exit(1);
	}
	top = p;
	bot = p + MAX-1;

	printf("Four Function Calculator\n");
	printf("Enter 'q' to quit\n");

	do
	{
		printf(": ");
		gets(str);
		switch(*str)
		{
			case '+' :
				x = pop();
				y = pop();
				printf("Result = %d\n", x+y);
				push(x+y);
				break;
			case '-' :
				x = pop();
				y = pop();
				printf("Result = %d\n", x-y);
				push(x-y);
				break;
			case '*' :
				x = pop();
				y = pop();
				printf("Result = %d\n", x*y);
				push(x*y);
				break;
			case '/' :
				x = pop();
				y = pop();
				if(x==0)
				{
					printf("Divide by zero..!!\n");
					break;
				}
				printf("Result = %d\n", y/x);
				push(y/x);
				break;
			case '.' :  // in this case, show contents of top of stack
				x = pop();
				push(x);
				printf("Current value on top of stack: %d\n", x);
				break;
			default :
				push(atoi(str));
		}
	}while(*str != 'q');

	getch();
}

// put an element on the stack
void push(int i)
{
	if(p>bot)
	{
		printf("Stack Overflow..!!\n");
		return;
	}
	*p = i;
	p++;
}

// retrieve the top element from the stack
int pop(void)
{
	p--;
	if(p<top)
	{
		printf("Stack Underflow..!!\n");
		return 0;
	}
	return *p;
}

After running this C stack example program, you have to just enter the two number and operator to check the result. Below are some sample runs of this C program:

c stack

c stack example

c stack push pop

After the first two sample run, when you press q, then the output will close and will go back to the code window.


« Previous Tutorial Next Tutorial »



Tools
Calculator

Quick Links
Signup - Login - Give Online Test