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).
Table of contents:
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:
0 | t | N-1 | |||||||||
A | B | C | D | E | F | G | H |
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.)
push 1, push 2, pop, push 3, pop, pop, push 4, pop,
prints the sequence 2, 3, 1, 4. Which of the 24 permutations of 1, 2, 3, 4 can be obtained in this manner?
if (stackisempty ()) push ('B'); else { if (peek () != 'A') push ('B'); else { while (!stackisempty () && peek () == 'A') pop (); push ('B'); } }
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.)
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:
infix | postfix |
---|---|
(A+B*C) | ABC*+ |
(A*(B+C)/D-E) | ABC+*D/E- |
(A+B*(C-D*(E-F)-G*H)-I*3) | ABCDEF-*-GH*-*+I3*- |
(A+B*C/D*E-F) | ABC*D/E*+F- |
(A+B+C*D-E*F*G) | AB+CD*+EF*G*- |
(A+(B-(C+(D-(E+F))))) | ABCDEF+-+-+ |
(A*(B+(C*(D+(E*(F+G)))))) | ABCDEFG+*+*+* |
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 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:
inf[0..i-1] | stk[0..t-1] | post[0..j-1] |
---|---|---|
( | ( | |
(A | ( | A |
(A* | (* | A |
(A*( | (*( | A |
(A*(B | (*( | AB |
(A*(B* | (*(* | AB |
(A*(B*C | (*(* | ABC |
(A*(B*C+ | (*(+ | ABC* |
(A*(B*C+D | (*(+ | ABC*D |
(A*(B*C+D) | (* | ABC*D+ |
(A*(B*C+D)) | ABC*D+* |
val[0] is the value of variable A,
val[1] is the value of variable B, etc.
Write a function to compute the value of post. Be careful with divisions by zero!
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.
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.)
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:
x = 333;.
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.
int TTT (int x[], int n) { if (n == 0) return 0; if (x[n] > 0) return x[n] + TTT (x, n-1); else return TTT (x, n-1); }
0 #4 aaa #2 1 bbb 2 CC #4 DDD #1 ee 3 FF #2 #4 4 GG hhh
(The numbers on the left margin serve only as a reference and are not part of the file.) Then the output file will contain
GG hhh aaa CC GG hhh DDD bbb ee
As the example suggests,
the special words are
replaced by the line of the input file
whose number is given after #
,
and this is done recursively.
To make the exercise more interesting,
do not write recursive functions.