Another way of storing data is in a stack. A stack is generally implemented with only two principle operations (apart from a constructor and destructor methods):
| push | adds an item to a stack |
| pop | extracts the most recently pushed item from the stack |
| top | returns the item at the top without removing it |
| isempty | determines whether the stack has anything in it |
 | A common model of a stack is a plate or coin stacker. Plates are "pushed" onto to the top and "popped" off the top. Stacks form Last-In-First-Out (LIFO) queues and have many applications from the parsing of algebraic expressions to ... |
A formal specification of a stack class would look like:
typedef struct t_stack *stack;
stack ConsStack( int max_items, int item_size );/* Construct a new stack
Pre-condition: (max_items > 0) && (item_size > 0)
Post-condition: returns a pointer to an empty stack
*/
void Push( stack s, void *item );
/* Push an item onto a stack
Pre-condition: (s is a stack created by a call to ConsStack) &&
(existing item count < max_items) &&
(item != NULL)
Post-condition: item has been added to the top of s
*/
void *Pop( stack s );
/* Pop an item of a stack
Pre-condition: (s is a stack created by a call to
ConsStack) &&
(existing item count >= 1)
Post-condition: top item has been removed from s
*/ Points to note: - A stack is simply another collection of data items and thus it would be possible to use exactly the same specification as the one used for our general collection. However, collections with the LIFO semantics of stacks are so important in computer science that it is appropriate to set up a limited specification appropriate to stacks only.
- Although a linked list implementation of a stack is possible (adding and deleting from the head of a linked list produces exactly the LIFO semantics of a stack), the most common applications for stacks have a space restraint so that using an array implementation is a natural and efficient one (In most operating systems, allocation and de-allocation of memory is a relatively expensive operation, there is a penalty for the flexibility of linked list implementations.).
3.3.1 Stack Frames
Almost invariably, programs compiled from modern high level languages (even C!) make use of a stack frame for the working memory of each procedure or function invocation. When any procedure or function is called, a number of words - the stack frame - is pushed onto a program stack. When the procedure or function returns, this frame of data is popped off the stack. As a function calls another function, first its arguments, then the return address and finally space for local variables is pushed onto the stack. Since each function runs in its own "environment" or context, it becomes possible for a function to call itself - a technique known as recursion. This capability is extremely useful and extensively used - because many problems are elegantly specified or solved in a recursive way.
 | Program stack after executing a pair of mutually recursive functions: function f(int x, int y) {
int a;
if ( term_cond ) return ...;
a = .....;
return g(a);
}
function g(int z) {
int p,q;
p = ...; q = ...;
return f(p,q);
} Note how all of function f and g's environment (their parameters and local variables) are found in the stack frame. When f is called a second time from g, a new frame for the second invocation of f is created. |
Key terms |
- push, pop
- Generic terms for adding something to, or removing something from a stack
- context
- The environment in which a function executes: includes argument values, local variables and global variables. All the context except the global variables is stored in a stack frame.
- stack frames
- The data structure containing all the data (arguments, local variables, return address, etc) needed each time a procedure or function is called.
Example (general)
The calculation: 1 + 2 * 4 + 3 can be written down like this in postfix notation with the advantage of no precedence rules and parentheses needed:
1 2 4 * + 3 +The expression is evaluated from the left to right using a stack:
- when encountering an operand: push it
- when encountering an operator (+,-,*,/,...etc): pop two operands, evaluate the result and push it.
Like the following way (the Stack is displayed after Operation has taken place):
| Inpu | Operation | Stack (after op) |
|---|---|---|
| 1 | Push operand | 1 |
| 2 | Push operand | 2, 1 |
| 4 | Push operand | 4, 2, 1 |
| * | Multiply | 8, 1 |
| + | Add | 9 |
| 3 | Push operand | 3, 9 |
| + | Add | 12 |
The final result, 12, lies on the top of the stack at the end of the calculation.
Example in C
#include<stdio.h>
int main()
{
int a[100], i;
printf("To pop enter -1\n");
for(i = 0;;)
{
printf("Push ");
scanf("%d", &a[i]);
if(a[i] == -1)
{
if(i == 0)
{
printf("Underflow\n");
}
else
{
printf("pop = %d\n", a[--i]);
}
}
else
{
i++;
}
}
} Stacks:
C, C++, and Java
Side-by-side
| C Stack | C++ Stack | Java Stack |
|---|---|---|
/* stack.h: header file */
void push( char );
char pop();
int empty();
int full();
-----------------------------
/* stack.c: stack implem */
#include "stack.h"
#define MAXSTACK 10
#define EMPTYSTACK -1
int top = EMPTYSTACK;
char items[MAXSTACK];
void push(char c) {
items[++top] = c;
}
char pop() {
return items[top--];
}
int full() {
return top+1 == MAXSTACK;
}
int empty() {
return top == EMPTYSTACK;
}
-----------------------------
/* stackmain.c: use stack */
#include <stdio.h>
#include "stack.h"
int main() {
char ch;
while ((ch = getchar())
!= '\n')
if (!full()) push(ch);
while (!empty())
printf("%c", pop());
printf("\n");
return 0;
} |
// stack.h: header file
class Stack {
int MaxStack;
int EmptyStack;
int top;
char* items;
public:
Stack(int);
~Stack();
void push(char);
char pop();
int empty();
int full();
};
-------------------------------
// stack.cpp: stack functions
#include "stack.h"
Stack::Stack(int size) {
MaxStack = size;
EmptyStack = -1;
top = EmptyStack;
items = new char[MaxStack];
}
Stack::~Stack() {delete[] items;}
void Stack::push(char c) {
items[++top] = c;
}
char Stack::pop() {
return items[top--];
}
int Stack::full() {
return top + 1 == MaxStack;
}
int Stack::empty() {
return top == EmptyStack;
}
-------------------------------
// stackmain.cpp: use stack
#include <iostream.h>
#include "stack.h"
int main() {
Stack s(10); // 10 chars
char ch;
while ((ch = cin.get())
!= '\n')
if (!s.full()) s.push(ch);
while (!s.empty())
cout << s.pop();
cout << endl;
return 0;
} |
// Stack.java: stack implementation
public class Stack {
private int maxStack;
private int emptyStack;
private int top;
private char[] items;
public Stack(int size) {
maxStack= size;
emptyStack = -1;
top = emptyStack;
items = new char[maxStack];
}
public void push(char c) {
items[++top] = c;
}
public char pop() {
return items[top--];
}
public boolean full() {
return top + 1 == maxStack;
}
public boolean empty() {
return top == emptyStack;
}
}
---------------------------------------
// Stackmain.java: use the stack
import java.io.*;
public class Stackmain {
public static void main(String[] args)
throws IOException {
Stack s = new Stack(10); // 10 chars
char ch;
while ((ch = (char)System.in.read())
!= '\n')
if (!s.full()) s.push(ch);
while (!s.empty())
System.out.print(s.pop());
System.out.println();
}
} |
| Execution of each program | ||
% cc -o stack stack.c stackmain.c % stack mississippi ppississim | % CC -o stack stack.cpp stackmain.cpp stack.cpp: stackmain.cpp: % stack mississippi ppississim | % javac Stack.java % javac Stackmain.java % java Stackmain mississippi ppississim |
