Algorithms Design   |   C language   |   Index

Stacks

A stack is a data structure that allows deletion of elements and insertion of new elements.  More specifically, a  stack  is a structure subject to the following rule: every deletion operation deletes the youngest element of the stack, i.e., the element that has been in the structure for less time.

In other words, the first object to be inserted in the stack is the last one to be deleted. This policy is known by the acronym LIFO (= Last In First Out).

Implementation in an array

Let's assume that our stack is stored in an array  stk[0..N-1].  (The nature of the elements of the array is irrelevant: they may be integers, bytes, pointers, etc.)  Let's say that the part of the array occupied by the stack is

stk[0..t-1] .

The index t indicates the first free position in the array and t-1 is the top of the stack.  The stack is empty if t is 0 and full if t is N.  In the figure below, the characters A, B, … , H were inserted into the stack in this order:

To delete an element from the stack — this operation is known as a pop — do

   x = stk[--t];

This is equivalent to the pair of instructions  t -= 1;  x = stk[t];.  Of course you should never attempt to pop an empty stack.

To insert an object y into the stack — the operation is kown as a push — do

   stk[t++] = y;  

This is equivalent to the pair of instructions  stk[t] = y;  t += 1;.  Of course you shoud never attempt to push onto a full stack.

To make the code easier to read, it is convenient to wrap these operations into two small functions. If the elements of the stack are of type char, these functions are

char pop (void) {
   return stk[--t];
}

void push (char y) {
   stk[t++] = y;
}

(These two functions have the additional benefit of isolating the user of the stack from the particular names of variables and design decisions, like stk[0..t-1] instead of stk[0..t], for example.)

We are assuming here that the variables stk and t are global, that is, they were defined outside the code of the functions.  To complete the package, we would need three more functions: one to create a stack, one to check whether the stack is empty, and one to check whether the stack is full. (See the exercise below.)

Exercises 1

Application: parentheses and brackets

Consider the problem of deciding whether a given sequence of parentheses and brackets is well formed (that is, whether the parentheses and brackets are closed in the order contrary to that in which they were opened).  For example, the sequence

is well formed, while   ( [ ) ]   is malformed.  Suppose that the sequence of parentheses and brackets is stored in an ASCII string  s.  (As usual, the last character of the string is \0.)

We use a stack to solve the problem.  The algorithm is simple: examine the string from left to right and push the left parentheses and left brackets onto the stack where they will wait for the corresponding right parentheses and right brackets. (See pseudocode.)

To simplify, the variables stk and t will be global.  We also assume that the size N of the array is greater than the size of the string and therefore the stack will never overflow.

#define N 100
char stk[N];
int t;

// This function returns 1 if the ASCII
// string s contains a well-formed sequence
// of parentheses and brackets; it returns
// 0 if the sequence is malformed.

int wellformed (char s[]) 
{
   createstack ();
   for (int i = 0; s[i] != '\0'; ++i) {
      char c;
      switch (s[i]) {
         case ')': if (stackisempty ()) return 0;
                   c = pop ();
                   if (c != '(') return 0;
                   break;
         case ']': if (stackisempty ()) return 0;
                   c = pop ();
                   if (c != '[') return 0;
                   break;
         default:  push (s[i]);
      }
   }
   return stackisempty ();
}

void createstack (void) {
   t = 0;
}

void push (char y) {
   stk[t++] = y;
}

char pop (void) {
   return stk[--t];
} 

int stackisempty (void) {
   return t <= 0;
}

(We could embed the code of the stack manipulation functions in the code of wellformed. The result would be shorter and more compact, but a little more difficult to read.)

Exercises 2

Another application: Polish notation

The usual notation of arithmetic expressions is infix, that is, the operators are written between the operands.  In the postfix (also known as Polish) notation, the operators are written after the operands.  Here are some examples of infix and the corresponding postfix expressions:

Notice that the operands (A, B, C, etc.) appear in the same order in the infix and the corresponding postfix expressions.  Also notice that the postfix notation does not need parentheses and precedence rules between operators (like the precedence of * over + for example), both of which are indispensable in the infix notation.

Our problem:  translate into postfix notation the infix expression stored in a string inf.  To simplify, we shall assume that

• the expression inf is valid and contains just ASCII letters, parentheses, and the symbols for the four arithmetic operations,
• the names of the variables have one letter each,
• all the operations (em particular - and +) have two operands,
• the expression inf is wrapped in a pair of parentheses (that is, the first character of the string is '(' and the last two are ')' and '\0').

The algorithm reads the expression inf one character at a time and uses a stack to do the translation.  Every left parenthesis is pushed onto the stack. When a right parenthesis is found, the algorithm pops characters from the stack until it finds a left parenthesis and pops that too. When a + or a - is found, the algorithm pops characters from the stack until it finds a left parenthesis, which is not popped. When a * or a / is found, the algorithm pops the stack until it finds a left parenthesis or a + or a - .  Constants and variables are transferred directly from inf to the postfix expression.  (See a draft in pseudocode.)

The variables stk and t are global.  We assume that N is greater than the size of the string inf, and therefore we need not worry about the stack becoming full. Since the expression inf is wrapped in parentheses, we need not worry about an empty stack.

#define N 100
char stk[N];
int t;

// This function receives an infix expression inf
// and returns the corresponding postfix expression.

char *infixToPostfix (char *inf) {
   int n = strlen (inf);
   char *post; 
   post = malloc ((n+1) * sizeof (char));
   createstack ();
   push (inf[0]);       // push '('

   int j = 0;
   for (int i = 1; inf[i] != '\0'; ++i) {
      switch (inf[i]) {
         char x;
         case '(': push (inf[i]);
                   break;
         case ')': x = pop ();
                   while (x != '(') {
                      post[j++] = x;
                      x = pop ();
                   }
                   break;
         case '+': 
         case '-': x = pop ();
                   while (x != '(') {
                      post[j++] = x;
                      x = pop ();
                   }
                   push (x);
                   push (inf[i])
                   break;
         case '*':
         case '/': x = pop ();
                   while (x != '(' && x != '+' && x != '-') {
                      post[j++] = x;
                      x = pop ();
                   }
                   push (x);
                   push (inf[i]);
                   break;
         default:  post[j++] = inf[i];
      }
   }
   post[j] = '\0';      
   return post;
}  

(We could operate the stack directly, by inserting the code of the stack manipulation functions into the code of the calling function. The result would be shorter and more compact, but somewhat less readable.)

Here is the result of the application of function infixToPostfix to the infix expression  (A*(B*C+D)). The table shows the values of the variables at the beginning of each iteration:

Exercises 3

Resizing array implementation

It is not always possible the predict the amount of space a stack will need. If the stack is implemented in an array, we could resize the array every time the stack becomes full, as we already did when implementing a queue.

Exercises 4

Linked list implementation of a stack

How to implement a stack in a linked list?  Let's say that the elements of the stack are ASCII characters and the cells of the list are of type cell (see The structure of a linked list):

typedef struct cell {
   char         contents; 
   struct cell *next;
} cell;

We make the following design decisions. 1. Our list will have a head cell (whence the first cell of the list will not be part of the stack).  2. The top of the stack will stay in the second cell rather than the last one (why?).  3. A global variable st will point to the head of the list.

The functions that manipulate the stack can then be written like this:

cell *st;

void createstack (void) {
   st = malloc (sizeof (cell)); // head
   st->next = NULL; 
}

void push (char y) { 
   cell *new;
   new = malloc (sizeof (cell));
   new->contents = y;
   new->next  = st->next;
   st->next = new; 
}

char pop (void) {
   cell *p;
   p = st->next;
   char x = p->contents;
   st->next = p->next;
   free (p);
   return x; 
}

(As usual, we assume that the function pop will never be called on an empty stack.)

Exercises 5

Appendix: The execution stack of a program

Every C program consists of one or more functions (and main is the first function to be executed). To manage the calls to the various functions, the operating system of the computer uses an execution stack.  (See the Call stack entry in Wikipedia.)  The operation can be described conceptually as follows.

When it encounters a function call, the computer creates a new workspace that contains all the parameters and all the local variables of the function.  This workspace is pushed onto the execution stack (on top of the workspace that called the function) and the execution of the function begins (confined to its workspace).  When the execution of the function ends, its workspace is popped from the stack and discarded.  The workspace that is now at the top of the stack is reactivated and the execution is restarted from the point at which it had been interrupted.  (See What's the stack? in Julia's drawings.)

Consider the following example:

   int G (int a, int b) {
      int x;
      x = a + b;
      return x;
   }

   int F (int i, j, k) {
      int x; 
      x = /*2*/ G (i, j) /*3*/;
      x = x + k;
      return x;
   }

   int main (void) {
      int i, j, k, y;
      i = 111; j = 222; k = 444;
      y = /*1*/ F (i, j, k) /*4*/;
      printf ("%d\n", y);
      return EXIT_SUCCESS;
   }

The execution of the program proceeds as follows:

• A workspace is created for the function main and pushed onto the execution stack.  The space contains the local variables i, j, k, and y.  The execution of main begins.
• At the point 1, the execution of main is temporarily interrupted and a workspace for the function F is pushed onto the stack.  This space contains the parameters i, j, k of the function, with values 111, 222, and 444 respectively, and the local variable x.  The execution of F begins.
• At the point 2, the execution of F is interrupted and a workspace for function G is pushed onto the stack.  This space contains the parameters a and b of the function, having values 111 and 222 respectively, and the local variable x.  Now the execution of G begins.
• When the execution of G ends, the function returns 333.  The workspace of G is popped from the stack and discarded.  The workspace of F (which is now at the top of the execution stack) is reactivated and the execution is restarted at point 3 in the code.  The first instruction to be executed is x = 333;.
• When the execution of F ends, the function returns 777. The workspace of F is popped from the stack.  The workspace of main (now at the top of the stack) is reactivated and the execution is restarted at point 4 in the code.  The first instruction executed is y = 777;.

In our example, F and G are distinct functions. But all would work the same way if F and G were identical, that is, if F were a recursive function.

Exercises 6