Stacks:
|
Even the C implementation achieves a key goal of an abstract data type: the method of implementation of the stack could be completely changed, say to a linked list form, without altering or even recompiling files that contain code making use of the stack. The C++ and Java stacks have this property also.
| 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 |
This C implementation gives a single instance of a stack of chars of size 10. If one wants a stack of a different size, or of a different type, one must hack the code and recompile. If one wants several instances of this stack (or similar ones), one must make another copy of the file with separate external function names.
This same stack code could be written with C "templates" in such a way that a stacks of any type, including user-defined types, could be easily created. For a program that converts this stack code to a templated version, see C++ Stack Template
The C++ implementation uses a separate "header" file as shown, similar to the C header file. This gives an "overview" of the stack without the complete implementation, and allows separate compilation of the file to implement the stack and any file that uses the stack. As in C, the header file allows the stack implementation file and any file using the stack to be separately compiled.
This C++ code needs a separate destructor to recover the storage for the stack after it is no longer in use. This is because the one portion of storage is a dynamically allocated array which would not be deleted by the default destructor. Java uses automatic garbage collection, and so it doesn't need destructors.
The Java implementation does not have a separate header file. In order to compile a file that uses this stack, the compiler must have access to the stack implementation file.
Java has the concept of an interface, which for a stack such as this would be a contract to implement the four given stack functions, by providing their prototypes in an interface declaration, and saying that the stack "implements" this interface.